Parallel Symbolic Factorization for Sparse LU with Static Pivoting
Authors:
- Laura GrigoriLGLaura Grigori
- James W. DemmelJDJames W. Demmel
- Xiaoye S. LiXLXiaoye S. Li
- 1 January 2007
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 29 (3) , 1289-1314
Abstract
This paper presents the design and implementation of a memory scalable parallel symbolic factorization algorithm for general sparse unsymmetric matrices. Our parallel algorithm uses a graph partitioning approach, applied to the graph of $|A|+|A|^T$, to partition the matrix in such a way that is good for sparsity preservation as well as for parallel factorization. The partitioning yields a so-called separator tree which represents the dependencies among the computations. We use the separator tree to distribute the input matrix over the processors using a block cyclic approach and a subtree to subprocessor mapping. The parallel algorithm performs a bottom-up traversal of the separator tree. With a combination of right-looking and left-looking partial factorizations, the algorithm obtains one column structure of L and one row structure of U at each step. The algorithm is implemented in C and MPI. From a performance study on large matrices, we show that the parallel algorithm significantly reduces the memory requirement of the symbolic factorization step, as well as the overall memory requirement of the parallel solver. It also often reduces the runtime of the sequential algorithm, which is already relatively small. In general, the parallel algorithm prevents the symbolic factorization step from being a time or memory bottleneck of the parallel solver.
Keywords
This publication has 14 references indexed in Scilit:
- SuperLU_DISTACM Transactions on Mathematical Software, 2003
- Improved Symbolic and Numerical Factorization Algorithms for Unsymmetric Sparse MatricesSIAM Journal on Matrix Analysis and Applications, 2002
- On Algorithms For Permuting Large Entries to the Diagonal of a Sparse MatrixSIAM Journal on Matrix Analysis and Applications, 2001
- A Supernodal Approach to Sparse Partial PivotingSIAM Journal on Matrix Analysis and Applications, 1999
- A Parallel Algorithm for Multilevel Graph Partitioning and Sparse Matrix OrderingJournal of Parallel and Distributed Computing, 1998
- Highly scalable parallel algorithms for sparse matrix factorizationIEEE Transactions on Parallel and Distributed Systems, 1997
- An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel ComputationsSIAM Journal on Scientific Computing, 1995
- Elimination Structures for Unsymmetric Sparse $LU$ FactorsSIAM Journal on Matrix Analysis and Applications, 1993
- Exploiting Structural Symmetry in Unsymmetric Sparse Symbolic FactorizationSIAM Journal on Matrix Analysis and Applications, 1992
- Communication results for parallel sparse Cholesky factorization on a hypercubeParallel Computing, 1989