Improved Symbolic and Numerical Factorization Algorithms for Unsymmetric Sparse Matrices
Author:
- Anshul GuptaAGAnshul Gupta
- 1 January 2002
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 24 (2) , 529-552
Abstract
We present algorithms for the symbolic and numerical factorization phases in the direct solution of sparse unsymmetric systems of linear equations. We have modified a classical symbolic factorization algorithm for unsymmetric matrices to inexpensively compute minimal elimination structures. We give an efficient algorithm to compute a near-minimal data-dependency graph for unsymmetric multifrontal factorization that is valid irrespective of the amount of dynamic pivoting performed during factorization. Finally, we describe an unsymmetric-pattern multifrontal algorithm for Gaussian elimination with partial pivoting that uses the task- and data-dependency graphs computed during the symbolic phase. These algorithms have been implemented in WSMP---an industrial strength sparse solver package---and have enabled WSMP to significantly outperform other similar solvers. We present experimental results to demonstrate the merits of the new algorithms.Keywords
This publication has 18 references indexed in Scilit:
- Analysis and comparison of two general sparse solvers for distributed memory computersACM Transactions on Mathematical Software, 2001
- A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic SchedulingSIAM Journal on Matrix Analysis and Applications, 2001
- On Algorithms For Permuting Large Entries to the Diagonal of a Sparse MatrixSIAM Journal on Matrix Analysis and Applications, 2001
- Multifrontal parallel distributed symmetric and unsymmetric solversComputer Methods in Applied Mechanics and Engineering, 2000
- A Supernodal Approach to Sparse Partial PivotingSIAM Journal on Matrix Analysis and Applications, 1999
- An Unsymmetric-Pattern Multifrontal Method for Sparse LU FactorizationSIAM Journal on Matrix Analysis and Applications, 1997
- An Approximate Minimum Degree Ordering AlgorithmSIAM Journal on Matrix Analysis and Applications, 1996
- Memory Management Issues in Sparse Multifrontal Methods On MultiprocessorsThe International Journal of Supercomputing Applications, 1993
- The influence of relaxed supernode partitions on the multifrontal methodACM Transactions on Mathematical Software, 1989
- Vectorization of a Multiprocessor Multifrontal CodeThe International Journal of Supercomputing Applications, 1989