×

zbMATH — the first resource for mathematics

The importance of structure in incomplete factorization preconditioners. (English) Zbl 1221.65090
Summary: We consider level-based preconditioning, which is one of the basic approaches to incomplete factorization preconditioning of iterative methods. It is well-known that while structure-based preconditioners can be very useful, excessive memory demands can limit their usefulness.
Here we present an improved strategy that considers the individual entries of the system matrix and restricts small entries to contributing to fewer levels of fill than the largest entries. Using symmetric positive-definite problems arising from a wide range of practical applications, we show that the use of variable levels of fill can yield incomplete Cholesky factorization preconditioners that are more efficient than those resulting from the standard level-based approach.
The concept of level-based preconditioning, which is based on the structural properties of the system matrix, is then transferred to the numerical incomplete decomposition. In particular, the structure of the incomplete factorization determined in the symbolic factorization phase is explicitly used in the numerical factorization phase. Further numerical results demonstrate that our level-based approach can lead to much sparser but efficient incomplete factorization preconditioners.
MSC:
65F08 Preconditioners for iterative methods
65F50 Computational methods for sparse matrices
65F10 Iterative numerical methods for linear systems
Software:
HSL; ILUT; SparseMatrix; YSMP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ajiz, M.A., Jennings, A.: A robust incomplete Choleski-conjugate gradient algorithm. Int. J. Numer. Methods Engrg. 20(5), 949–966 (1984) · Zbl 0541.65019 · doi:10.1002/nme.1620200511
[2] Axelsson, O., Munksgaard, N.: Analysis of incomplete factorizations with fixed storage allocation. In: Preconditioning Methods: Analysis and Applications. Topics in Comput. Math., vol. 1, pp. 219–241. Gordon & Breach, New York (1983) · Zbl 0765.65030
[3] Baker, G. Jr., Oliphant, T.: An implicit, numerical method for solving the two-dimensional heat equation. Quart. Appl. Math. 17, 361–373 (1960) · Zbl 0092.32901
[4] Benzi, M., Haws, J.C., Tuma, M.: Preconditioning highly indefinite and nonsymmetric matrices. SIAM J. Sci. Comput. 22(4), 1333–1353 (2000) · Zbl 0985.65036 · doi:10.1137/S1064827599361308
[5] Benzi, M., Kouhia, R., Tuma, M.: Stabilized and block approximate inverse preconditioners for problems in solid and structural mechanics. Comput. Methods Appl. Mech. Engrg. 190(49–50), 6533–6554 (2001) · Zbl 1021.74041 · doi:10.1016/S0045-7825(01)00235-3
[6] Blanco, M., Zingg, D.: A Newton-Krylov algorithm with a loosely coupled turbulence model for aerodynamic flows. AIAA J. 45, 980–987 (2007) · doi:10.2514/1.22972
[7] Bollhöfer, M.: A robust ILU with pivoting based on monitoring the growth of the inverse factors. Linear Algebra Appl. 338, 201–218 (2001) · Zbl 0991.65028 · doi:10.1016/S0024-3795(01)00385-8
[8] Bollhöfer, M.: A robust and efficient ILU that incorporates the growth of the inverse triangular factors. SIAM J. Sci. Comput. 25(1), 86–103 (2003) · Zbl 1038.65021 · doi:10.1137/S1064827502403411
[9] Bollhöfer, M., Saad, Y.: On the relations between ILUs and factored approximate inverses. SIAM J. Matrix Anal. Appl. 24(1), 219–237 (2002) · Zbl 1017.65019 · doi:10.1137/S0895479800372110
[10] Bru, R., Marín, J., Mas, J., Tuma, M.: Balanced incomplete factorization. SIAM J. Sci. Comput. 30(5), 2302–2318 (2008) · Zbl 1187.65029 · doi:10.1137/070696088
[11] Bru, R., Marín, J., Mas, J., Tuma, M.: Improved balanced incomplete factorization. SIAM J. Matrix Anal. Appl. 31(5), 2431–2452 (2010) · Zbl 1210.65076 · doi:10.1137/090747804
[12] Buleev, N.I.: A numerical method for solving two-dimensional diffusion equations. Atomnaja Energija 6, 338–340 (1959)
[13] Buleev, N.I.: A numerical method for solving two-dimensional and three-dimensional diffusion equations. Mat. Sb. 51, 227–238 (1960) · Zbl 0105.10401
[14] Davis, T.A.: The university of Florida sparse matrix collection. Technical Report, University of Florida (2007). http://www.cise.ufl.edu/\(\sim\)davis/techreports/matrices.pdf · Zbl 1365.65123
[15] D’Azevedo, E., Forsyth, P., Tang, W.: Drop tolerance preconditioning for incompressible viscous flow. Int. J. Comput. Math. 44, 301–312 (1992) · Zbl 0757.76034 · doi:10.1080/00207169208804110
[16] Dolan, E., Moré, J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[17] Duff, I.S., Meurant, G.A.: The effect of ordering on preconditioned conjugate gradients. BIT 29, 635–657 (1989) · Zbl 0687.65037 · doi:10.1007/BF01932738
[18] Eisenstat, S.C., Gursky, M.C., Schultz, M.H., Sherman, A.H.: The Yale sparse matrix package (YSMP)–II: The non-symmetric codes. Tech. Rep. No. 114, Department of Computer Science, Yale University (1977) · Zbl 0492.65012
[19] Eisenstat, S.C., Gursky, M.C., Schultz, M.H., Sherman, A.H.: Yale Sparse Matrix Package (YSMP)–I: The symmetric codes. Int. J. Numer. Methods Engrg. 18, 1145–1151 (1982) · Zbl 0492.65012 · doi:10.1002/nme.1620180804
[20] Freund, R.W., Nachtigal, N.M.: An implementation of the look-ahead Lanczos algorithm for non-hermitian matrices, Part II. Technical Report TR 90-46, RIACS, NASA Ames Research Center (1990) · Zbl 0770.65022
[21] Gustafsson, I.: A class of first order factorization methods. BIT 18(2), 142–156 (1978) · Zbl 0386.65006 · doi:10.1007/BF01931691
[22] Hénon, P., Ramet, P., Roman, J.: On finding approximate supernodes for an efficient block-ILU(k) factorization. Parallel Comput. 34(6–8), 345–362 (2008) · doi:10.1016/j.parco.2007.12.003
[23] HSL: A collection of Fortran codes for large-scale scientific computation (2007). See http://www.cse.scitech.ac.uk/nag/hsl/
[24] Hysom, D., Pothen, A.: A scalable parallel algorithm for incomplete factor preconditioning. SIAM J. Sci. Comput. 22, 2194–2215 (2001) · Zbl 0986.65048 · doi:10.1137/S1064827500376193
[25] Hysom, D., Pothen, A.: Level-based incomplete LU factorization: Graph model and algorithms. Technical Report UCRL-JC-150789, Lawrence Livermore National Labs (November 2002) · Zbl 0986.65048
[26] Il’in, Y.M.: Difference Methods for Solving Elliptic Equations (in Russian). Novosibirskij Gosudarstvennyj Universitet, Novosibirsk (1970)
[27] Il’in, Y.M.: Iterative Incomplete Factorization Methods. World Scientific, Singapore (1992)
[28] Jones, M.T., Plassmann, P.E.: An improved incomplete Cholesky factorization. ACM Trans. Math. Softw. 21(1), 5–17 (1995) · Zbl 0886.65024 · doi:10.1145/200979.200981
[29] Kershaw, D.S.: The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations. J. Comput. Phys. 26, 43–65 (1978) · Zbl 0367.65018 · doi:10.1016/0021-9991(78)90098-0
[30] Lin, C.J., Moré, J.J.: Incomplete Cholesky factorizations with limited memory. SIAM J. Sci. Comput. 21(1), 24–45 (1999) · Zbl 0941.65033 · doi:10.1137/S1064827597327334
[31] Meijerink, J.A., van der Vorst, H.A.: An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix. Math. Comp. 31, 148–162 (1977) · Zbl 0349.65020
[32] Meijerink, J.A., van der Vorst, H.A.: Guidelines for the usage of incomplete decompositions in solving sets of linear equations as they occur in practical problems. J. Comput. Phys. 44(1), 134–155 (1981) · Zbl 0472.65028 · doi:10.1016/0021-9991(81)90041-3
[33] Munksgaard, N.: Solving sparse symmetric sets of linear equations by preconditioned conjugate gradients. ACM Trans. Math. Softw. 6(2), 206–219 (1980) · Zbl 0438.65035 · doi:10.1145/355887.355893
[34] Oliphant, T.A.: An extrapolation process for solving linear systems. Quart. Appl. Math. 20, 257–265 (1962) · Zbl 0109.34601
[35] Østerby, O., Zlatev, Z.: Direct Methods for Sparse Matrices. Lecture Notes in Computer Science, vol. 157. Springer, Berlin (1983) · Zbl 0663.65021
[36] Pueyo, A., Zingg, D.: Efficient Newton-Krylov solver for aerodynamic computations. AIAA J. 36, 1991–1997 (1998) · doi:10.2514/2.326
[37] Rose, D.J., Tarjan, R.E.: Algorithm aspects of vertex elimination on directed graphs. SIAM J. Appl. Math. 34(1), 176–197 (1978) · Zbl 0377.65013 · doi:10.1137/0134014
[38] Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithm aspects of vertex elimination on graphs. SIAM J. Comput. 5, 266–283 (1976) · Zbl 0353.65019 · doi:10.1137/0205021
[39] Saad, Y.: ILUT: a dual threshold incomplete LU factorization. Numer. Linear Algebra Appl. 1(4), 387–402 (1994) · Zbl 0838.65026 · doi:10.1002/nla.1680010405
[40] Saad, Y.: Iterative Methods for Sparse Linear Systems. PWS Publishing, Boston (1996) · Zbl 1031.65047
[41] Sabinin, V.I.: An algorithm of the incomplete factorization method. Chisl. Metody Mekh. Sploshn. Sredy 16(2), 103–117 (1985) · Zbl 0578.76082
[42] Varga, R.S.: Factorizations and normalized iterative methods. In: Boundary Problems in Differential Equations, pp. 121–142. University of Wisconsin Press, Madison (1960)
[43] Watts, J.W. III: A conjugate gradient truncated direct method for the iterative solution of the reservoir simulation pressure equation. Soc. Pet. Eng. J. 21, 345–353 (1981)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.