An Unsymmetrized Multifrontal LU Factorization
- 1 January 2002
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 24 (2) , 553-569
- https://doi.org/10.1137/s0895479800375370
Abstract
A well-known approach to computing the LU factorization of a general unsymmetric matrix A is to build the elimination tree associated with the pattern of the symmetric matrix A + AT and use it as a computational graph to drive the numerical factorization. This approach, although very efficient on a large range of unsymmetric matrices, does not capture the unsymmetric structure of the matrices. We introduce a new algorithm which detects and exploits the structural asymmetry of the submatrices involved during the processing of the elimination tree. We show that with the new algorithm, significant gains, both in memory and in time, to perform the factorization can be obtained.Keywords
This publication has 17 references indexed in Scilit:
- 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 combined unifrontal/multifrontal method for unsymmetric sparse matricesACM Transactions on Mathematical Software, 1999
- 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
- Vectorization of a Multiprocessor Multifrontal CodeThe International Journal of Supercomputing Applications, 1989
- The Multifrontal Solution of Indefinite Sparse Symmetric LinearACM Transactions on Mathematical Software, 1983