New convergence results and preconditioning strategies for the conjugate gradient method.(English)Zbl 0837.65027
Summary: Instead of the standard estimate in terms of the spectral condition number we develop a new conjugate gradient (CG) iteration number estimate depending on the quantity \[\text{B}= {1\over n}\text{ tr } M/(\text{det } M)^{1/n},\] where \(M\) is an \(n\times n\) preconditioned matrix. A new family of iterative methods for solving symmetric positive definite systems based on B-reducing strategies is described. Numerical results are presented for the new algorithms and compared with several well-known preconditioned CG methods.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
Keywords:
conjugate gradients;iteration number estimates;explicit preconditionings;numerical results;iterative methods;symmetric positive definite systems;B-reducing strategies;algorithmsSoftware:
symrcmCite
Full Text:DOI
References:
| [1] | Axelsson, BIT 13 pp 443– (1972) |
| [2] | On preconditioning and convergence acceleration in sparse matrix problems. CERN Rep. 74-10, May 1974, Geneva, 21 pp. |
| [3] | Axelsson, Computer Meth. Appl. Mech. Engng. 9 pp 123– (1976) |
| [4] | Private communication. 1992. |
| [5] | Axelsson, Numer. Math. 48 pp 479– (1986) |
| [6] | Axelsson, Numer. Math. 48 pp 499– (1986) |
| [7] | Axelsson, Int. J. Numer. Meth. Engng. 27 pp 637– (1989) |
| [8] | Axelsson, SIAM J. Sci. Statist. Comput. 12 pp 1373– (1991) |
| [9] | Benson, Int. J. Computer Math. 16 pp 245– (1984) |
| [10] | Berryman, J. Parall. Distr. Comput. 8 pp 186– (1990) |
| [11] | Bjorstad, SIAM J. Sci. Statist. Comput. 10 pp 1053– (1989) |
| [12] | Bramble, Math. Comput. 5 pp 1– (1990) ·doi:10.1090/S0025-5718-1990-1023042-6 |
| [13] | A class of parallel iterative methods implemented on multiprocessors. Rep. UIUCDCS-R-86-1267, Dept. Comp. Sci., University of Illinois at Urbana-Champaign, Urbana, Illinois, 1986. |
| [14] | and . A generalized conjugate gradient method for numerical solution of elliptic partial differential equations. Sparse Matrix Computations pages 309-332. Academic Press, 1976. ·doi:10.1016/B978-0-12-141050-6.50023-4 |
| [15] | Dennis, SIAM J. Numer. Anal. 10 pp 1291– (1993) |
| [16] | and . Approximate inversion of positive matrices with applications to modelling. In NATO ASI Series, v. F34, Modelling, Robustness and Sensivity Reduction in Control Systems pages 211-238. editor. Springer Verlag, Berlin, 1987. ·doi:10.1007/978-3-642-87516-8_14 |
| [17] | Eisenstat, SIAM J. Sci. Statist. Comput. 2 pp 1– (1981) |
| [18] | Forsythe, Proc. Amer. Math. Soc. 6 pp 340– (1955) |
| [19] | Gadjokov, Computer Phys. Commun. 36 pp 19– (1985) |
| [20] | and . Computer Solution of Large Sparse Positive Definite Systems. Prentice Hall, Englewood Cliffs, NJ, 1981. ·Zbl 0516.65010 |
| [21] | Greenbaum, Numer. Math. 33 pp 181– (1979) |
| [22] | Greenbaum, BIT 29 pp 610– (1989) |
| [23] | Greenbaum, Numer. Math. 56 pp 529– (1989) |
| [24] | Gustafson, SIAM J. Sci. Statist. Comput. 9 pp 609– (1988) |
| [25] | and . Matrix Computations. North Oxford Academic Press, Oxford, 1983. ·Zbl 0559.65011 |
| [26] | and . Applied Iterative Methods. Academic Press, New York, 1981. ·Zbl 0459.65014 |
| [27] | Jennings, IMA J. Numer. Anal. 20 pp 61– (1977) |
| [28] | Johnson, SIAM J. Numer. Anal. 20 pp 362– (1983) |
| [29] | An alternative approach to estimating the iteration number of the conjugate gradient method. Numerical Methods and Software, pages 53-72. editor. Dept. Comput. Math., Academy of Sciences of the USSR, Moscow, 1990. (In Russian.) |
| [30] | Kaporin, Differential Equations 26 pp 897– (1990) |
| [31] | Kaporin, Computational Mathematics and Modeling (1992) |
| [32] | Kaporin, Int. J. Computer Math. 40 pp 169– (1992) |
| [33] | Kaporin, Differential Equations 28 pp 280– (1992) |
| [34] | Kaporin, Computational Mathematics and Modeling (1993) |
| [35] | Kolotilina, Soviet J. Numer. Anal. Math. Model. 1 pp 293– (1986) |
| [36] | Kratzer, Comp. Fluids 11 pp 255– (1983) |
| [37] | Kuo, SIAM J. Matrix Anal. Appl. 11 pp 403– (1990) |
| [38] | Manteuffel, Math. Comput. 34 pp 473– (1980) |
| [39] | and . A Survey of Matrix Theory and Matrix Inequalities. Allyn & Bacon, Boston, MA, 1964. |
| [40] | and . Inequalities: Theory of Majorization and Its Applications. Academic Press, New York, 1979. ·Zbl 0437.26007 |
| [41] | Meinardus, Numer. Math. 5 pp 14– (1963) |
| [42] | Introduction to Parallel and Vector Solution of Linear Systems. Plenum Press, New York, 1988. ·doi:10.1007/978-1-4899-2112-3 |
| [43] | di Brozolo, Parallel Computing 11 pp 223– (1989) ·Zbl 0678.65017 |
| [44] | Krylov, SIAM J. Sci. Statist. Comput. 10 pp 1200– (1989) |
| [45] | Saltz, J. Parall. Distr. Comput. 8 pp 303– (1990) |
| [46] | van der Vorst, SIAM J. Sci. Statist. Comput. 10 pp 1174– (1989) |
| [47] | van der Sluis, Numer. Math. 48 pp 543– (1986) |
| [48] | Sobh, Computer Phys. Commun. 65 pp 253– (1991) |
| [49] | Winther, SIAM J. Numer. Anal. 17 pp 14– (1980) |
| [50] | Wolkowicz, Linear Algebra Appls. 29 pp 471– (1980) |
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.
