next up previous
Next: Inner products Up: High performance computing Previous: High performance computing

Quotient graph computation


A matrix defines a graph by introducing an edge (i,j) for every nonzero element tex2html_wrap_inline1007. 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 tex2html_wrap_inline1009 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.

Victor Eijkhout
Mon Aug 25 17:46:10 PDT 1997