A Supernodal Approach to Incomplete LU Factorization with Partial Pivoting
Authors:
Open Access
- 1 February 2011
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 37 (4) , 1-20
Abstract
We present a new supernode-based incomplete LU factorization method to construct a preconditioner for solving sparse linear systems with iterative methods. The new algorithm is primarily based on the ILUTP approach by Saad, and we incorporate a number of techniques to improve the robustness and performance of the traditional ILUTP method. These include new dropping strategies that accommodate the use of supernodal structures in the factored matrix and an area-based fill control heuristic for the secondary dropping strategy. We present numerical experiments to demonstrate that our new method is competitive with the other ILU approaches and is well suited for modern architectures with memory hierarchy.Keywords
Funding Information
- Special Funds for Major State Basic Research Projects (2005CB321700)
- Advanced Scientific Computing Research (D-AC02-05CH11231)
This publication has 20 references indexed in Scilit:
- Multilevel Preconditioners Constructed From Inverse-Based ILUsSIAM Journal on Scientific Computing, 2006
- A column approximate minimum degree ordering algorithmACM Transactions on Mathematical Software, 2004
- Benchmarking optimization software with performance profilesMathematical Programming, 2002
- SuperLU users' guide1999
- The Design and Use of Algorithms for Permuting Large Entries to the Diagonal of Sparse MatricesSIAM Journal on Matrix Analysis and Applications, 1999
- A Supernodal Approach to Sparse Partial PivotingSIAM Journal on Matrix Analysis and Applications, 1999
- An object-oriented framework for block preconditioningACM Transactions on Mathematical Software, 1998
- An Approximate Minimum Degree Ordering AlgorithmSIAM Journal on Matrix Analysis and Applications, 1996
- Performance Issues for Iterative Solvers in Device SimulationSIAM Journal on Scientific Computing, 1996
- An Approximate Factorization Procedure for Solving Self-Adjoint Elliptic Difference EquationsSIAM Journal on Numerical Analysis, 1968