A matrix defines a graph by introducing an edge (i,j) for
every nonzero element . A dense matrix in this manner
defines a graph in which each node is connected to every other
node. This is also called a `clique'.
Sparse matrices, on the other hand, induce a graph where,
no matter the number of nodes, each node is connected to only
a small number of other nodes.
However, sparse matrices from problems with multiple physical
variables will have dense subblocks, for instance corresponding
to the variables on any given node. It is possible to increase
the efficiency of linear algebra operations by imposing on the
matrix the block structure induced by these small dense subblocks.
For instance, the scalar multiplication/division
that appears in Gaussian elimination now becomes a matrix inversion
and a matrix-matrix multiplication, in other words, BLAS3 kernels.
Identifying cliques in the matrix graph, and deriving a quotient graph by `factoring them out', is the approach taken in the BlockSolve package; section 3.2.
The PCG package (section 3.9) takes the opposite approach in its Regular Grid Stencil data format. To get dense subblocks, the degrees of freedom have to be numbered first in regular storage, but in PCG they are numbered last. This approach is more geared towards vector architectures.