doc/html/test_match_supernodes.html

 // ========================================================================= //
 // This file is part of MyraMath, copyright (c) 2014-2019 by Ryan A Chilton  //
 // and distributed by MyraCore, LLC. See LICENSE.txt for license terms.      //
 // ========================================================================= //

 // Containers.
 #include <myramath/sparse/Pattern.h>
 #include <myramath/sparse/PatternRange.h>
 #include <myramath/sparse/PatternBuilder.h>
 #include <myramath/sparse/Permutation.h>
 #include <myramath/multifrontal/symbolic/detail/Match.h>

 // Algorithms.
 #include <myramath/utility/cumsum.h>
 #include <myramath/utility/random.h>
 #include <myramath/sparse/laplacian2.h>
 #include <myramath/sparse/permute.h>
 #include <myramath/multifrontal/symbolic/detail/match_supernodes.h>

 // Reporting.
 #include <tests/myratest.h>
 #include <myramath/utility/stlprint.h>

 // For random_shuffle()
 #include <algorithm>

 using namespace myra;

 namespace {

 // Helper function to repeat a Pattern, making supernodes to find later.
 Pattern repeat(const Pattern& A, const std::vector<int>& counts)
   {
   std::vector<int> strides = cumsum(counts);
   PatternBuilder B(strides.back(), strides.back() );
   for (auto iterator = A.begin(); iterator != A.end(); ++iterator)
     {
     int i = iterator.i();
     int j = iterator.j();
     for (int ii = strides[i]; ii != strides[i+1]; ++ii)
       for (int jj = strides[j]; jj != strides[j+1]; ++jj)
         B.insert(ii,jj);
     }
   return B.make_Pattern();
   }

 // Helper function to shuffle a Pattern, makes supernodes nonobvious.
 Pattern shuffle(const Pattern& A)
   {
   int N = A.size().first;
   auto P = Permutation::random(N);
   return permute(P,A);
   }

 }

 ADD_TEST("match_supernodes","[symbolic]")
   {
   // Construct the Pattern A and
   Pattern A = stencil2(4,4);
   myra::out() << "A = " << A << std::endl;
   std::vector<int> counts(16,1);
   // .. 3 supernodes of size 2
   counts[4] = 2;
   counts[8] = 2;
   counts[13] = 2;
   // .. 3 supernodes of size 3
   counts[5] = 3;
   counts[7] = 3;
   counts[9] = 3;
   // .. 2 supernodes of size 4
   counts[10] = 4;
   counts[12] = 4;
   // .. the rest (16-3-3-2=8) are size 1

   // Perform a number of randomized trials ..
   int T = 100;
   for (int t = 0; t < T; ++t)
     {
     // Expand A into a supernodal Pattern B, apply a shuffle.
     Pattern B = shuffle(repeat(A,counts));
     myra::out() << "B[" << t << "] = " << B << std::endl;

     // Extract supernodes.
     Match match = match_supernodes(B);
     int F = match.F; // fine unknowns
     int C = match.C; // coarse unknowns, ie supernodes

     // Count up size of each supernode.
     std::vector<int> sizes(C,0);
     for (int f = 0; f < F; ++f)
       sizes[match.f2c[f] ]++;
     std::map<int,int> sizemap;
     for (int c = 0; c < C; ++c)
       sizemap[ sizes[c] ]++;

     // .. should be 16 supernodes total
     REQUIRE(C == 16);
     // .. 3 supernodes of size 2
     REQUIRE(sizemap.at(2) == 3);
     // .. 3 supernodes of size 3
     REQUIRE(sizemap.at(3) == 3);
     // .. 2 supernodes of size 4
     REQUIRE(sizemap.at(4) == 2);
     // .. the rest (16-3-3-2=8) are size 1
     REQUIRE(sizemap.at(1) == 8);
     }

   }

myra::cumsum
std::vector< T > cumsum(const std::vector< T > &v)
Returns cumulative sum. For example, cumsum({4,8,9,13}) = {0,4,12,21,34}.
Definition: cumsum.h:19

PatternBuilder.h
Convenience type for building Pattern&#39;s, uses coordinate/couplet format. Note that PatternBuilder may...

myra
Definition: syntax.dox:1

stlprint.h
Routines for printing the contents of various std::container&#39;s to a std::ostream using operator <<...

myra::Pattern::size
std::pair< int, int > size() const
Size inspector.
Definition: Pattern.cpp:134

myra::PatternBuilder::insert
void insert(int i, int j)
Inserts a single structural nonzero.
Definition: PatternBuilder.cpp:97

PatternRange.h
Range/Iterator types associated with Pattern.

permute.h
Given a SparseMatrix A and permutations P and Q, returns P&#39;*A*Q.

myra::Pattern::begin
PatternIterator begin() const
Returns iterators over all of A(:,:)
Definition: Pattern.cpp:163

myra::Pattern
Holds the nonzero pattern of a sparse matrix.
Definition: Pattern.h:55

myra::PatternBuilder
Like Pattern, but easier to populate via insert()/erase() methods.
Definition: PatternBuilder.h:51

Pattern.h
Container class for a sparse nonzero pattern, used in reordering/symbolic analysis.

Permutation.h
Aggregates a (perm, iperm, swaps) triple into a vocabulary type.

cumsum.h
Returns cumulative sum of a std::vector<T>. Reversible by diff()

random.h
Simplistic random number functions.

myra::Permutation::random
static Permutation random(int N)
Generates a random Matrix of specified size.
Definition: Permutation.cpp:188

laplacian2.h
Helper routines for reordering/filling 2D structured grids. Used by many unit tests.