A Nondeterministic Parallel Algorithm for General Unsymmetric Sparse LU Factorization
Authors:
- Timothy A. DavisTDTimothy A. Davis
- Pen-Chung YewPYPen-Chung Yew
- 1 July 1990
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 11 (3) , 383-402
Abstract
A parallel algorithm for the direct LU factorization of general unsymmetric sparse matrices is presented. The algorithm D2 is based on a new nondeterministic parallel pivot search that finds a compatible pivot set${\bf S}$ of size m, followed by a parallel rank-m update. These two steps alternate until switching to dense matrix code or until the matrix is factored. The algorithm is based on a shared-memory multiple-instruction-multiple-data (MIMD) model and takes advantage of both concurrency and (gather-scatter) vectorization. The detection of parallelism due to sparsity is based on Markowitz’s strategy, an unsymmetric ordering method. As a result, D2 finds more potential parallelism for matrices with highly asymmetric nonzero patterns than algorithms that construct an elimination tree using a symmetric ordering method (minimum degree or nested dissection, for example) applied to the symmetric pattern of ${\bf A} + {\bf A}^{\bf T} $ or ${\bf A}^{\bf T} {\bf A}$. The pivot search exploits more parallelism...
Keywords
This publication has 28 references indexed in Scilit:
- Multiprocessing a sparse matrix code on the Alliant FX/8Journal of Computational and Applied Mathematics, 1989
- Vectorization of a Multiprocessor Multifrontal CodeThe International Journal of Supercomputing Applications, 1989
- Sparse matrix test problemsACM Transactions on Mathematical Software, 1989
- Sparse Gaussian elimination with controlled fill-in on a shared memory multiprocessorIEEE Transactions on Computers, 1989
- Pairwise reduction for the direct, parallel solution of sparse, unsymmetric sets of linear equationsIEEE Transactions on Computers, 1988
- Parallel implementation of multifrontal schemesParallel Computing, 1986
- The Multifrontal Solution of Unsymmetric Sets of Linear EquationsSIAM Journal on Scientific and Statistical Computing, 1984
- The Multifrontal Solution of Indefinite Sparse Symmetric LinearACM Transactions on Mathematical Software, 1983
- Some Design Features of a Sparse Matrix CodeACM Transactions on Mathematical Software, 1979
- On the Automatic Scaling of Matrices for Gaussian EliminationIMA Journal of Applied Mathematics, 1972