Numerical study on incomplete orthogonal factorization preconditioners. (English) Zbl 1161.65036
Summary: We design, analyse and test a class of incomplete orthogonal factorization preconditioners constructed from Givens rotations, incorporating some dropping strategies and updating tricks, for the solution of large sparse systems of linear equations. Comprehensive accounts about how the preconditioners are coded, what storage is required and how the computation is executed for a given accuracy are presented. A number of numerical experiments show that these preconditioners are competitive with standard incomplete triangular factorization preconditioners when they are applied to accelerate Krylov subspace iteration methods such as generalized minimal residual (GMRES) and stabilized bi-conjugate gradient (BiCGSTAB) methods.
MSC:
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 65F10 | Iterative numerical methods for linear systems |
| 65F50 | Computational methods for sparse matrices |
Keywords:
preconditioning; Givens rotation; incomplete orthogonal factorization; nonsymmetric matrix; normal equations; comparison of methods; large sparse systems; numerical experiments; Krylov subspace iteration methods; generalized minimal residual (GMRES); stabilized bi-conjugate gradient (BiCGSTAB) methodsReferences:
| [1] | Arioli, M.; Loghin, D.; Wathen, A. J., Stopping criteria for iterations in finite element methods, Numer. Math., 99, 381-410 (2005) · Zbl 1069.65124 |
| [2] | Axelsson, O., Iterative Solution Methods (1997), Cambridge University Press: Cambridge University Press Cambridge |
| [3] | Bai, Z.-Z., Sharp error bounds of some Krylov subspace methods for non-Hermitian linear systems, Appl. Math. Comput., 109, 273-285 (2000) · Zbl 1026.65028 |
| [4] | Bai, Z.-Z., Splitting iteration methods for non-Hermitian positive definite systems of linear equations, Hokkaido Math. J., 36, 801-814 (2007) · Zbl 1138.65027 |
| [5] | Bai, Z.-Z.; Duff, I. S.; Wathen, A. J., A class of incomplete orthogonal factorization methods. I: Methods and theories, BIT Numer. Math., 41, 53-70 (2001) · Zbl 0990.65038 |
| [6] | Bai, Z.-Z.; Golub, G. H.; Lu, L.-Z.; Yin, J.-F., Block triangular and skew-Hermitian splitting methods for positive-definite linear systems, SIAM J. Sci. Comput., 26, 844-863 (2005) · Zbl 1079.65028 |
| [7] | Bai, Z.-Z.; Golub, G. H.; Ng, M. K., Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl., 24, 603-626 (2003) · Zbl 1036.65032 |
| [8] | Bai, Z.-Z.; Golub, G. H.; Ng, M. K., On successive-overrelaxation acceleration of the Hermitian and skew-Hermitian splitting iterations, Numer. Linear Algebra Appl., 14, 319-335 (2007) · Zbl 1199.65097 |
| [9] | Bai, Z.-Z.; Jin, C.-H., Column-decomposed relaxation methods for the overdetermined systems of linear equations, Int. J. Appl. Math., 13, 71-82 (2003) · Zbl 1049.65025 |
| [10] | Bai, Z.-Z.; Li, G.-Q.; Lu, L.-Z., Combinative preconditioners of modified incomplete Cholesky factorization and Sherman-Morrison-Woodbury update for self-adjoint elliptic Dirichlet-periodic boundary value problems, J. Comput. Math., 22, 833-856 (2004) · Zbl 1083.65098 |
| [11] | Bai, Z.-Z.; Yin, J.-F.; Su, Y.-F., A shift-splitting preconditioner for non-Hermitian positive definite matrices, J. Comput. Math., 24, 539-552 (2006) · Zbl 1120.65054 |
| [12] | Bai, Z.-Z.; Zhang, S.-L., A regularized conjugate gradient method for symmetric positive definite system of linear equations, J. Comput. Math., 20, 437-448 (2002) · Zbl 1002.65040 |
| [13] | Benzi, M.; Tůma, M., Ordering for factorized sparse approximate inverse preconditioners, SIAM J. Sci. Comput., 21, 1851-1868 (2000) · Zbl 0959.65047 |
| [14] | Benzi, M.; Tůma, M., A robust preconditioner with low memory requirements for large sparse least squares problems, SIAM J. Sci. Comput., 25, 499-512 (2003) · Zbl 1042.65030 |
| [15] | Björck, A., Numerical Methods for Least Squares Problems (1996), SIAM: SIAM Philadelphia · Zbl 0847.65023 |
| [16] | Duff, I. S.; Erisman, A. M.; Reid, J. K., Direct Methods for Sparse Matrices (1986), Oxford University Press: Oxford University Press London · Zbl 0604.65011 |
| [17] | Dupont, T.; Kendall, R.; Rachford, H. H., An approximate factorization procedure for solving selfadjoint elliptic difference equations, SIAM J. Numer. Anal., 5, 559-573 (1968) · Zbl 0174.47603 |
| [18] | Elman, H. C., Relaxed and stabilized incomplete factorizations for non-self-adjoint linear systems, BIT Numer. Math., 29, 890-915 (1989) · Zbl 0694.65011 |
| [19] | Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore, London · Zbl 0865.65009 |
| [20] | Gustafsson, I., A class of first order factorization methods, BIT Numer. Math., 18, 142-156 (1978) · Zbl 0386.65006 |
| [21] | Hayami, K.; Ito, T., Solutions of least squares problems using generalized minimal residual methods, Proc. Inst. Statist. Math., 53, 331-348 (2005), (in Japanese) |
| [22] | K. Hayami, J.-F. Yin, T. Ito, GMRES methods for least squares problems, NII Technical Report, NII-2007-009E, National Institute of Informatics, Tokyo, Japan, 2007; K. Hayami, J.-F. Yin, T. Ito, GMRES methods for least squares problems, NII Technical Report, NII-2007-009E, National Institute of Informatics, Tokyo, Japan, 2007 |
| [23] | Hestenes, M. R.; Stiefel, E. L., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., Section B, 49, 409-436 (1952) · Zbl 0048.09901 |
| [24] | Manteuffel, T. A., An incomplete factorization technique for positive definite linear systems, Math. Comp., 34, 473-497 (1980) · Zbl 0422.65018 |
| [25] | Matrix Market, Test matrices database maintained by NIST, Gaithersburg, MD. http://math.nist.gov/MatrixMarket/data/; Matrix Market, Test matrices database maintained by NIST, Gaithersburg, MD. http://math.nist.gov/MatrixMarket/data/ |
| [26] | 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. Comput., 31, 148-162 (1977) · Zbl 0349.65020 |
| [27] | 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, 134-155 (1981) · Zbl 0472.65028 |
| [28] | Saylor, P., Second order strongly implicit symmetric factorization methods for the solution of elliptic difference equations, SIAM J. Numer. Anal., 11, 894-908 (1974) · Zbl 0295.65059 |
| [29] | Stone, H. L., Iterative solution of implicit approximations of multidimensional partial differential equations, SIAM J. Numer. Anal., 5, 530-558 (1968) · Zbl 0197.13304 |
| [30] | Papadopoulos, A. T.; Duff, I. S.; Wathen, A. J., A class of incomplete orthogonal factorization methods. II: Implementation and results, BIT Numer. Math., 45, 159-179 (2005) · Zbl 1080.65028 |
| [31] | Saad, Y.; Schultz, M. H., GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7 (1986), 856-839 · Zbl 0599.65018 |
| [32] | Saad, Y., Preconditioning techniques for nonsymmetric and indefinite linear systems, J. Comput. Appl. Math., 24, 89-105 (1988) · Zbl 0662.65028 |
| [33] | Saad, Y., ILUT: A dual threshold incomplete ILU factorization, Numer. Linear Algebra Appl., 1, 387-402 (1994) · Zbl 0838.65026 |
| [34] | Saad, Y., Iterative Methods for Sparse Linear Systems (1996), PWS Publishing Company: PWS Publishing Company Boston · Zbl 1002.65042 |
| [35] | Van der Vorst, H. A., Iterative Krylov Methods for Large Linear Systems (2003), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1023.65027 |
| [36] | Varga, R. S., Matrix Iterative Analysis (1962), Prentice-Hall: Prentice-Hall Englewoods Cliffs, NJ · Zbl 0133.08602 |
| [37] | Wang, X.-G.; Gallivan, K. A.; Bramley, R., CIMGS: An incomplete orthogonal factorization preconditioner, SIAM J. Sci. Comput., 18, 516-536 (1997) · Zbl 0871.65033 |
| [38] | Washio, T.; Hayami, K., Parallel block preconditioning based on SSOR and MILU, Numer. Linear Algebra Appl., 1, 533-553 (1994) · Zbl 0838.65027 |
| [39] | Washio, T.; Hayami, K., Overlapped multicolor MILU preconditioning, SIAM J. Sci. Comput., 16, 636-650 (1995) · Zbl 0925.65059 |
| [40] | Yin, J.-F.; Bai, Z.-Z., The restrictively preconditioned conjugate gradient methods on normal residual for block two-by-two linear systems, J. Comput. Math., 26, 240-249 (2008) · Zbl 1174.65014 |
| [41] | Young, D. M., Iterative Solution of Large Linear Systems (1971), Academic Press: Academic Press New York · Zbl 0204.48102 |
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.
