clarke@csri.toronto.edu (Jim Clarke) (01/16/89)
NUMERICAL ANALYSIS SEMINAR - Friday, January 27, 10 a.m. in Room SF 4102
(SF = Sandford Fleming Building, 10 King's College Road)
Alex Pothen
Pennsylvania State University
"Large Ordering Sparse Matrices for Parallel Factorization"
We consider the problem of ordering sparse, symmetric, positive definite
matrices for efficient parallel Cholesky factorization on medium grained
parallel computers. Jess and Kees (1982) suggested a method in which a good
parallel ordering is computed in two steps. First, the matrix A is or-
dered by some fill-reducing ordering, which results in a chordal filled
graph. Second, a parallel ordering of A is computed from the filled
graph by a greedy method.
We present a fast linear algorithm that implements the parallel ordering
step by exploiting the clique tree representation of a chordal graph. We
succeed in reducing the cost of the parallel ordering step well below that
of the initial fill-reducing step. Our algorithm has time and space com-
plexity linear in the number of compressed subscripts for the Cholesky fac-
tor L, i.e., the sum of the sizes of the maximal cliques of the filled graph.
Computational results confirm that our algorithm is competitive with other
approaches to the ordering problem.
The concept of the clique tree is important in its own right, and is
relevant in several other sparse matrix problems, such as the use of vec-
torization in the numeric factorization. If time permits, I will also
describe these applications of the clique tree.
(Joint work with John Lewis (Boeing Computer Services) and Barry Peyton
(Oak Ridge National Lab))
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
BITNET,CSNET: clarke@csri.toronto.edu CDNNET: clarke@csri.toronto.cdn
UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke