@device(postscript)
@libraryfile(Mathematics10)
@libraryfile(Accents)
@style(fontfamily=timesroman,fontscale=11)
@pagefooting(immediate, left "@c",
center "@c",
right "@c")
@heading(Combinatorial Preconditioners for Sparse,
Symmetric, Diagonally Dominant Linear Systems)
@heading(CMU-CS-96-123)
@center(@b(Keith D. Gremban))
@center(October 1996 - Ph.D. Thesis)
@center(FTP: CMU-CS-96-123.ps)
@blankspace(1)
@begin(text,spacing=.95)
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 @i(support 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 @i(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 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 that conventional 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.
@blankspace(2line)
@begin(transparent,size=10)
@b(Keywords:@ )@c
@end(transparent)
@blankspace(1line)
@end(text)
@flushright(@b[(144 pages)])