Parallel Cholesky Factorization of Sparse Matrices
Collections
Author
Gilbert, John R.
Hafsteinsson, Hjalmtyr
Abstract
We describe a parallel algorithm for finding the Cholesky factorization of a sparse symmetric positive definite matrix A. The algorithm runs in $O(h \log n)$ time with $m*$ processors, where $h$ is the height of A's elimination tree. We then show how to speed up that algorithm, so that it runs in $O(\log n \log^{2}h)$ time with increased number of processors. Also, we present corresponding parallel algorithms for forward solve and back solve with the same time bounds and similar processor bounds.
Date Issued
1987-12
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR87-893
Type
technical report