Affordable Access

Publisher Website

A parallel algorithm for elimination tree computation and symbolic factorization

Authors
Journal
Parallel Computing
0167-8191
Publisher
Elsevier
Publication Date
Volume
18
Issue
8
Identifiers
DOI: 10.1016/0167-8191(92)90031-2
Keywords
  • Sparse Cholesky Decomposition
  • Symbolic Factorization
  • Elimination Tree
  • Local Memory Multiprocessor
Disciplines
  • Computer Science

Abstract

Abstract The notion of an elimination tree plays a very important role in the parallel algorithms for sparse Cholesky decomposition, symbolic factorization and in determining the mapping of columns of the matrix to processors. In this paper, we present a parallel algorithm to compute the elimination tree and simultaneously carry out symbolic factorization on a local memory multiprocessor. An existing parallel algorithm for symbolic factorization [5] requires the computation of elimination tree separately. In our algorithm, we use a tree defined on the given matrix, called false elimination tree, and convert it into the actual elimination tree. In the process, we also compute the structure of the columns of the factor matrix. Using the new parallel algorithm on grid problems, we found that it performs 2 to 3 times faster compared to the total time taken for sequential computation of the elimination tree and the parallel computation of symbolic factorization using [5]. Also, our algorithm is the first parallel algorithm for elimination tree computation that gives a speed-up.

There are no comments yet on this publication. Be the first to share your thoughts.