Support Tree Conjugate Gradient
Solution of partial differential equations by either the finite
element or the finite difference methods often requires the solution
of large, sparse linear systems. 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 support tree preconditioners,
that are based on the connectivity of the graphs corresponding to the
coefficient matrices of the linear systems. These new preconditioners
have the advantage of being well-structured for parallel
implementation, both in construction and in evaluation. We evaluated
the performance of support tree preconditioners by comparing them
against two common types of preconditioners: those arising from
diagonal scaling, and from the incomplete Cholesky decomposition. We
solved linear systems corresponding to both regular and irregular
meshes on the Cray C-90 using all three preconditioners and monitored
the number of iterations required to converge, and the total time
taken by the iterative processes. We show empirically that the
convergence properties of support tree preconditioners are similar,
and superior in many cases, to those of incomplete Cholesky
preconditioners, which in turn are superior to those of diagonal
scaling. Support tree preconditioners require less overall storage,
less work per iteration, and yield better parallel performance than
incomplete Cholesky preconditioners. In terms of total execution time,
support tree preconditioners outperform both diagonal scaling and
incomplete Cholesky preconditioners. Hence, support tree
preconditioners provide a powerful, practical tool for the solution of
large sparse systems of equations on vector and parallel machines.
For more information, see our tech report
Performance
Evaluation of a New Parallel Preconditioner, by Keith D. Gremban,
Gary L. Miller, and Marco Zagha, CMU-CS-94-205.
Up to the Irregular Algorithms page,
the NESL page, or
the Scandal page.
kdg@cs.cmu.edu and
marcoz@cs.cmu.edu.