×

Robust dropping criteria for F-norm minimization based sparse approximate inverse preconditioning. (English) Zbl 1284.65048

The authors study how drop tolerances affect the quality and effectiveness of a preconditioner. They focus on the mathematical theory on robust selection criteria for drop tolerances. To develop a robust preconditioning procedure, the authors analyze the effects of drop tolerances on the non-singularity, quality and effectiveness of preconditioners. They establish some relationships between these factors. They propose adaptive robust selection criteria for drop tolerances that can make the preconditioner as sparse as possible and of comparable quality to those obtained by currently known preconditioners, so that it is possible to lower the cost of setup and application. Numerical experiments are given to show that their criteria work well.

MSC:

65F08 Preconditioners for iterative methods
65F50 Computational methods for sparse matrices

Software:

ILUT; BFSAI-IC
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Barrett, R., Berry, M., Chan, T., Demmel, J., Donato, J., Dongarra, J., Eijkhout, V., Romine, R., Van der Vorst, H.: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM, Philadelphia (1994) · Zbl 0814.65030 · doi:10.1137/1.9781611971538
[2] Benson, M., Frederickson, P.: Iterative solution of large sparse linear systems arising in certain multidimensional approximation problems. Util. Math. 22, 154-155 (1982)
[3] Benzi, M.: Preconditioning techniques for large linear systems: a survey. J. Comput. Phys. 182, 418-477 (2002) · Zbl 1015.65018 · doi:10.1006/jcph.2002.7176
[4] Benzi, M., Tůma, M.: A sparse approximate inverse preconditioner for nonsymmetric linear systems. SIAM J. Sci. Comput. 19, 968-994 (1998) · Zbl 0930.65027 · doi:10.1137/S1064827595294691
[5] Benzi, M., Tůma, M.: Numerical experiments with two inverse preconditioners. BIT Numer. Math. 38, 234-241 (1998) · Zbl 0909.65027 · doi:10.1007/BF02512364
[6] Benzi, M., Tůma, M.: A comparative study of sparse approximate inverse preconditioners. Appl. Numer. Math. 30, 305-340 (1999) · Zbl 0949.65043 · doi:10.1016/S0168-9274(98)00118-4
[7] Benzi, M., Meyer, C., Tůma, M., et al.: A sparse approximate inverse preconditioner for the conjugate gradient method. SIAM J. Sci. Comput. 17, 1135-1149 (1996) · Zbl 0856.65019 · doi:10.1137/S1064827594271421
[8] Bergamaschi, L., Martínez, Á., Pini, G.: Parallel preconditioned conjugate gradient optimization of the Rayleigh quotient for the solution of sparse eigenproblems. Appl. Math. Comput. 175, 1694-1715 (2006) · Zbl 1093.65036 · doi:10.1016/j.amc.2005.09.015
[9] Bergamaschi, L., Gambolati, G., Pini, G.: A numerical experimental study of inverse preconditioning for the parallel iterative solution to 3d finite element flow equations. J. Comput. Appl. Math. 210, 64-70 (2007) · Zbl 1134.65023 · doi:10.1016/j.cam.2006.10.056
[10] Bollhöfer, M.: A robust and efficient ILU that incorporates the growth of the inverse triangular factors. SIAM J. Sci. Comput. 25, 86-103 (2003) · Zbl 1038.65021 · doi:10.1137/S1064827502403411
[11] Bröker, O., Grote, M.J.: Sparse approximate inverse smoothers for geometric and algebraic multigrid. Appl. Numer. Math. 41, 61-80 (2002) · Zbl 0995.65129 · doi:10.1016/S0168-9274(01)00110-6
[12] Bröker, O., Grote, M.J., Mayer, C., Reusken, A.: Robust parallel smoothing for multigrid via sparse approximate inverses. SIAM J. Sci. Comput. 23, 1396-1417 (2001) · Zbl 1004.65043 · doi:10.1137/S1064827500380623
[13] Carpentieri, B., Duff, I., Giraud, L.: Some sparse pattern selection strategies for robust Frobenius norm minimization preconditioners in electromagnetism. Numer. Linear Algebra Appl. 7, 667-685 (2000) · Zbl 1051.65050 · doi:10.1002/1099-1506(200010/12)7:7/8<667::AID-NLA218>3.0.CO;2-X
[14] Chow, E.: A priori sparsity patterns for parallel sparse approximate inverse preconditioners. SIAM J. Sci. Comput. 21, 1804-1822 (2000) · Zbl 0957.65023 · doi:10.1137/S106482759833913X
[15] Chow, E., Saad, Y.: Experimental study of ILU preconditioners for indefinite matrices. J. Comput. Appl. Math. 86, 387-414 (1997) · Zbl 0891.65028 · doi:10.1016/S0377-0427(97)00171-4
[16] Chow, E., Saad, Y.: Approximate inverse preconditioners via sparse-sparse iterations. SIAM J. Sci. Comput. 19, 995-1023 (1998) · Zbl 0922.65034 · doi:10.1137/S1064827594270415
[17] Cosgrove, J., Diaz, J., Griewank, A.: Approximate inverse preconditionings for sparse linear systems. Int. J. Comput. Math. 44, 91-110 (1992) · Zbl 0762.65025 · doi:10.1080/00207169208804097
[18] Ferronato, M., Janna, C., Pini, G.: Parallel solution to ill-conditioned FE geomechanical problems. Int. J. Numer. Anal. Methods Geomech. 36, 422-437 (2012) · doi:10.1002/nag.1012
[19] Gould, N., Scott, J.: Sparse approximate-inverse preconditioners using norm-minimization techniques. SIAM J. Sci. Comput. 19, 605-625 (1998) · Zbl 0911.65037 · doi:10.1137/S1064827595288425
[20] Grote, M., Huckle, T.: Parallel preconditioning with sparse approximate inverses. SIAM J. Sci. Comput. 18, 838-853 (1997) · Zbl 0872.65031 · doi:10.1137/S1064827594276552
[21] Gupta, A., George, T.: Adaptive techniques for improving the performance of incomplete factorization preconditioning. SIAM J. Sci. Comput. 32, 84-110 (2010) · Zbl 1209.65036 · doi:10.1137/080727695
[22] Holland, R., Watten, A., Shaw, G.: Sparse approximate inverses and target matrices. SIAM J. Sci. Comput. 26, 1000-1011 (2005) · Zbl 1077.65044 · doi:10.1137/030601132
[23] Huckle, T.: Approximate sparsity patterns for the inverse of a matrix and preconditioning. Appl. Numer. Math. 30, 291-304 (1999) · Zbl 0927.65045 · doi:10.1016/S0168-9274(98)00117-2
[24] Janna, C., Ferronato, M.: Adaptive pattern research for Block FSAI preconditioning. SIAM J. Sci. Comput. 33, 3357-3380 (2011) · Zbl 1273.65045 · doi:10.1137/100810368
[25] Janna, C., Ferronato, M., Gambolati, G.: A block FSAI-ILU parallel preconditioner for symmetric positive definite linear systems. SIAM J. Sci. Comput. 32, 2468-2484 (2010) · Zbl 1220.65037 · doi:10.1137/090779760
[26] Jia, Z., Zhang, Q.: An approach to making SPAI and PSAI preconditioning effective for large irregular sparse linear systems. SIAM J. Sci. Comput. (2012, to appear). arXiv:1203.2325v2 [math] · Zbl 1362.65035
[27] Jia, Z., Zhu, B.: A power sparse approximate inverse preconditioning procedure for large sparse linear systems. Numer. Linear Algebra Appl. 16, 259-299 (2009) · Zbl 1224.65088 · doi:10.1002/nla.614
[28] Kaporin, I.: A preconditioned conjugate gradient method for solving discrete analogs of differential problems. Differ. Equ. 26, 897-906 (1990) · Zbl 0712.65022
[29] Kolotilina, L.: Explicit preconditioning of systems of linear algebraic equations with dense matrices. J. Math. Sci. 43, 2566-2573 (1988) · Zbl 0664.65042 · doi:10.1007/BF01374987
[30] Kolotilina, L., Yeremin, A.: Factorized sparse approximate inverse preconditionings I. Theory. SIAM J. Matrix Anal. Appl. 14, 45-58 (1993) · Zbl 0767.65037 · doi:10.1137/0614004
[31] Kolotilina, L., Nikishin, A., Yeremin, A.: Factorized sparse approximate inverse preconditionings. IV: Simple approaches to rising efficiency. Numer. Linear Algebra Appl. 6, 515-531 (1999) · Zbl 0983.65062 · doi:10.1002/(SICI)1099-1506(199910/11)6:7<515::AID-NLA176>3.0.CO;2-0
[32] Mayer, J.: Alternative weighted dropping strategies for ILUTP. SIAM J. Sci. Comput. 27, 1424-1437 (2006) · Zbl 1095.65026 · doi:10.1137/030602022
[33] Saad, Y.: ILUT: A dual threshold incomplete LU factorization. Numer. Linear Algebra Appl. 1, 387-402 (1994) · Zbl 0838.65026 · doi:10.1002/nla.1680010405
[34] Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM, Philadelphia (2003) · Zbl 1031.65046 · doi:10.1137/1.9780898718003
[35] Sedlacek, M.: Approximate inverses for preconditioning, smoothing and regularization. Ph.D. Thesis, Technical University of Munich, Germany (2012) · Zbl 0891.65028
[36] Tang, W.: Toward an effective sparse approximate inverse preconditioner. SIAM J. Matrix Anal. Appl. 20, 970-986 (1999) · Zbl 0937.65056 · doi:10.1137/S0895479897320071
[37] Tang, W., Wan, W.: Sparse approximate inverse smoother for multigrid. SIAM J. Matrix Anal. Appl. 21, 1236-1252 (2000) · Zbl 1049.65146 · doi:10.1137/S0895479899339342
[38] Wang, K., Zhang, J.: Msp: a class of parallel multistep successive sparse approximate inverse preconditioning strategies. SIAM J. Sci. Comput. 24, 1141-1156 (2003) · Zbl 1034.65022 · doi:10.1137/S1064827502400832
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.