×

On the eigenvalue distribution of a class of preconditioning methods. (English) Zbl 0564.65016

A class of preconditioning methods depending on a relaxation parameter is presented for the solution of large linear systems of equations \(Ax=b\), where A is a symmetric positive definite matrix. The methods are based on an incomplete factorization of the matrix A and include both pointwise and blockwise factorizations. We study the dependence of the rate of convergence of the preconditioned conjugate gradient method on the distribution of eigenvalues of \(C^{-1}A\), where C is the preconditioning matrix. We also show graphic representations of the eigenvalues and present numerical tests of the methods.

MSC:

65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Andersson, L.: SSOR preconditioning of Toeplitz matrices. Thesis, Chalmers University of Technology, Göteborg, Sweden, 1976 · Zbl 0766.65023
[2] Axelsson, O.: A class of iterative methods for finite element equations. Comput. Methods Appl. Mech. Eng.9, 123-137 (1976) · Zbl 0334.65028 · doi:10.1016/0045-7825(76)90056-6
[3] Axelsson, O.: A general incomplete block-matrix factorization method. Linear Algebra Appl. (To appear) · Zbl 0622.65023
[4] Axelsson, O., Barker, V.A.: Finite Element Solutions of Boundary Value Problems. Theory and Computation. New York: Academic Press 1984 · Zbl 0537.65072
[5] Axelsson, O., Brinkkemper, S., Il’in, V.P.: On some versions of incomplete block-matrix factorization iterative methods. Linear Algebra Appl.58, 3-15 (1984) · Zbl 0548.65016 · doi:10.1016/0024-3795(84)90200-3
[6] Axelsson, O., Gustafsson, I.: Preconditioning and Two-Level Multigrid Methods of Arbitrary Degree of Approximation. Math. Comput.40, 219-242 (1983) · Zbl 0511.65079 · doi:10.1090/S0025-5718-1983-0679442-3
[7] Axelsson, O., lindskog, G.: On the rate of convergence of the preconditioned conjugate gradient method. Numer. Math. (To appear) · Zbl 0564.65017
[8] Axelsson, O., Munksgaard, N.: A class of preconditioned conjugate gradient methods for the solution of a mixed finite element discretization of the biharmonic operator. Internat. J. Numer. Methods Eng.14, 1001-1019 (1979) · Zbl 0416.65069 · doi:10.1002/nme.1620140705
[9] Beauwens, R.: On Axelssons perturbations. Linear Algebra Appl.68, 221-242 (1985) · Zbl 0599.65023 · doi:10.1016/0024-3795(85)90214-9
[10] Concus, P., Golub, G.H., Meurant, G.: Block preconditioning for the conjugate gradient method. SIAM J. Sci. Stat. Comput.6, 220-252 (1985) · Zbl 0556.65022 · doi:10.1137/0906018
[11] Greenbaum, A.: Comparison of splittings used with the conjugate gradient algorithm. Numer. Math.33, 181-194 (1979) · Zbl 0414.65020 · doi:10.1007/BF01399553
[12] Gustafsson, I.: Modified Incomplete Cholesky (MIC) Methods. In: Preconditioning Methods, Theory and Applications. (Evans, D.J., ed.), pp. 265-293. New York, London, Paris: Gordon and Breach Science 1983 · Zbl 0767.65017
[13] Jennings, A.: Influence of the Eigenvalue, Spectrum on the Convergence Rate of the Conjugate Gradient Method. J. Inst. Math. Appl.20, 61-72 (1977) · Zbl 0364.65028 · doi:10.1093/imamat/20.1.61
[14] Meijerink, J.A., van der Vorst, H.A.: An iterative solution method for linear systems of which the coefficient matrix is a symmetricM-matrix. Math. Comput.31, 148-152 (1977) · Zbl 0349.65020
[15] Varga, R.S.: Factorization and normalized iterative methods. In: Boundary problems in differential equations. (R.E. Langer, ed.), pp. 121-142. Madison: Madison University of Wisconsin Press 1960
[16] van der Vorst, H.A., van der Sluis, A.: The rate of convergence of conjugate gradients. (Preprint Nr. 354, November 1984, Department of Mathematics University of Utrecht) · Zbl 0596.65015
[17] Winther, R.: Some superlinear convergence results for the conjugate gradient method. SIAM J. Numer. Anal.17, 14-17 (1980) · Zbl 0447.65021 · doi:10.1137/0717002
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.