Keith D. Gremban

Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems Degree Type: Ph.D. in Computer Science
Advisor(s): Gary Miller
Graduated: December 1996

Abstract:

Solution of large, sparse linear systems is an important problem in science and engineering. Such systems arise in many applications, such as electrical networks, stress analysis, and more generally, in the numerical solution of partial differential equations. When the coefficient matrices associated with these linear systems are symmetric and positive definite, the systems are often solved iteratively using the preconditioned conjugate gradient method. We have developed a new class of preconditioners, which we call sup- port tree preconditioners, that are based on the combinatorial properties of the graphs corresponding to the coefficient matrices of the linear systems. We call the resulting iterative method support tree conjugate gradient, or STCG. These new preconditioners are applicable to the class of symmetric and diagonally dominant matrices, and have the advantage of being well-structured for parallel implementation, both in construction and in evaluation. In this thesis, we present the intuition, construction, implementation, and analysis of STCG.

STCG is based upon an interesting isomorphism between a certain class of matrices (which we call Laplacian matrices), edge-weighted undirected graphs, and resistive networks. Using this isomorphism, we show that an iterative method can be interpreted in terms of these discrete structures. Based on this interpretation, the STCG method for accelerating convergence is developed, which involves constructing other, more efficient discrete structures called support trees, and using their interpretation as matrices to apply them as preconditioners. Interestingly, the matrix preconditioners used in STCG are larger, but sparser than conventional preconditioners. Additionally, the construction of support trees is basically an application of recursive divide-and-conquer. Support trees have very regular structures and are very well-suited for parallel implementation.

Through theoretical analysis and numerical experiments, we show that STCG is practical and efficient for the parallel solution of large sparse linear systems with Laplacian coefficient matrices. STCG is an interesting example of combinatorial techniques being applied to solve an algebraic problem. These techniques have wider applicability than the acceleration of iterative techniques. We also demonstrate an application of these techniques to the more general problem of bounding eigenvalues.

Thesis Committee:
Gary Miller (Chair)
Guy Blelloch
Paul Heckbert
Bruce Maggs
Omar Ghattas
Mike Heroux (Cray Research)

James Morris, Head, Computer Science Department
Raj Reddy Dean, School of Computer Science

Keywords:
linear systems, iterative methods, preconditioners, sparse and very large systems, parallel algorithms