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.

Mon Aug 25 17:46:10 PDT 1997