A numerical evaluation of preprocessing and ILU-type preconditioners for the solution of unsymmetric sparse linear systems using iterative methods

ABSTRACT

Recent advances in multilevel LU factorizations and novel preprocessing techniques have led to an extremely large number of possibilities for preconditioning sparse, unsymmetric linear systems for solving with iterative methods. However, not all combinations work well for all systems, so making the right choices is essential for obtaining an efficient solver. The numerical results for 256 matrices presented in this article give an indication of which approaches are suitable for which matrices (based on different criteria, such as total computation time or fill-in) and of the differences between the methods.

REFERENCES

• 1: Michele Benzi , John C. Haws , Miroslav Tuma, Preconditioning Highly Indefinite and Nonsymmetric Matrices, SIAM Journal on Scientific Computing, v.22 n.4, p.1333-1353, 2000 [doi>10.1137/S1064827599361308]
• 2: Bollhöfer, M. 2001. A robust ILU with pivoting based on monitoring the growth of inverse factors. Lin. Alg. Appl. 338, 201--218.
• 3: Matthias Bollhöfer, A Robust and Efficient ILU that Incorporates the Growth of the Inverse Triangular Factors, SIAM Journal on Scientific Computing, v.25 n.1, p.86-103, 2003 [doi>10.1137/S1064827502403411]
• 4: Bollhöfer, M. and Saad, Y. 2003. Multilevel preconditioners constructed from inverse-based ILUs. SIAM J. Sci. Comput. 25, 2, 715--728.
• 5: Bollhöfer, M. and Saad, Y. 2008. ILUPACK. http://www.math.tu-berlin.de/ilupack/.
• 6: Na Li , Yousef Saad , Edmond Chow, Crout Versions of ILU for General Sparse Matrices, SIAM Journal on Scientific Computing, v.25 n.2, p.716-728, 2003 [doi>10.1137/S1064827502405094]
• 7: Edmond Chow , Yousef Saad, Experimental study of ILU preconditioners for indefinite matrices, Journal of Computational and Applied Mathematics, v.86 n.2, p.387-414, Dec. 10, 1997 [doi>10.1016/S0377-0427(97)00171-4]
• 8: Davis, T. 2008. University of Florida Sparse Matrix Collection. http://www.cise.ufl.edu/research/sparse/matrices.
• 9: Dolan, E. and Moré, J. J. 2002. Benchmarking optimization software with performance profiles. Math. Program. 91, 2, 201--213.
• 10: Iain S. Duff , Jacko Koster, The Design and Use of Algorithms for Permuting Large Entries to the Diagonal of Sparse Matrices, SIAM Journal on Matrix Analysis and Applications, v.20 n.4, p.889-901, Oct. 1999 [doi>10.1137/S0895479897317661]
• 11: I. S. Duff , J. Koster, On Algorithms For Permuting Large Entries to the Diagonal of a Sparse Matrix, SIAM Journal on Matrix Analysis and Applications, v.22 n.4, p.973-996, 2000 [doi>10.1137/S0895479899358443]
• 12: Iain S. Duff , Stéphane Pralet, Strategies for Scaling and Pivoting for Sparse Symmetric Indefinite Problems, SIAM Journal on Matrix Analysis and Applications, v.27 n.2, p.313-340, 2005 [doi>10.1137/04061043X]
• 13: Nicholas I. M. Gould , Jennifer A. Scott , Yifan Hu, A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations, ACM Transactions on Mathematical Software (TOMS), v.33 n.2, p.10-es, June 2007 [doi>10.1145/1236463.1236465]
• 14: Michael Hagemann , Olaf Schenk, Weighted Matchings for Preconditioning Symmetric Indefinite Linear Systems, SIAM Journal on Scientific Computing, v.28 n.2, p.403-420, 2006 [doi>10.1137/040615614]
• 15: Karypis, G. 2008. METIS. http://glaros.dtc.umn.edu/gkhome/views/metis/.
• 16: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 17: Mayer, J. 2005. ILUCP: A Crout ILU preconditioner with pivoting. Numer. Linear Algebra Appl. 12, 9, 941--955.
• 18: Jan Mayer, Alternative Weighted Dropping Strategies for ILUTP, SIAM Journal on Scientific Computing, v.27 n.4, p.1424-1437, 2006 [doi>10.1137/030602022]
• 19: Mayer, J. 2007. A multilevel Crout ILU preconditioner with pivoting and row permutation. Numer. Linear Algebra Appl. 14, 10, 771--789.
• 20: Mayer, J. 2008a. ILU++. http://www.iluplusplus.de.
• 21: Jan Mayer, Symmetric Permutations for I-matrices to Delay and Avoid Small Pivots During Factorization, SIAM Journal on Scientific Computing, v.30 n.2, p.982-996, March 2008 [doi>10.1137/060669176]
• 22: Olschowska, M. and Neumaier, A. 1996. A new pivoting strategy for Gaussian elimination. Lin. Alg. Appl. 220, 131--151.
• 23: Saad, Y. 1994. ILUT: A dual threshold incomplete LU factorization. Numer. Linear Algebra Appl. 1, 387--402.
• 24: Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
• 25: Yousef Saad, Multilevel ILU With Reorderings for Diagonal Dominance, SIAM Journal on Scientific Computing, v.27 n.3, p.1032-1057, 2005 [doi>10.1137/030602733]
• 26: Olaf Schenk , Klaus Gärtner, Solving unsymmetric sparse systems of linear equations with PARDISO, Future Generation Computer Systems, v.20 n.3, p.475-487, April 2004 [doi>10.1016/j.future.2003.07.011]
• 27: Schenk, O. and Gärtner, K. 2006. On fast factorization pivoting methods for sparse symmetric indefinite systems. Elec. Trans. Numer. Anal. 23, 158--179.
• 28: Schenk, O. and Gärtner, K. 2008. PARDISO. http://www.pardiso-project.org.
• 29: Schenk, O., Gärtner, K., and Fichtner, W. 2000. Efficient sparse LU factorization with left-looking strategy on shared memory multiprocessors. BIT 40, 1, 158--176.
• 30: Tismenetsky, M. 1991. A new preconditioning technique for solving large sparse linear systems. Linear Algebra Appl. 154-156, 331--353.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

General Terms:
Algorithms, Performance

Keywords:
Incomplete LU factorization, iterative methods, preconditioning, sparse linear systems