×

Approximate inverse preconditioners for the conjugate gradient method. (English) Zbl 0996.65049

Summary: The method of conjugate gradients is known to converge for symmetric positive definite systems of equations. This paper applies it to nonsymmetric and ill-conditioned matrices. In order to facilitate convergence, an approximate inverse is used to precondition the conjugate gradient method. This is achieved by applying Newton’s method. Three versions of Newton’s method are introduced to compute the approximate inverse. Convergence of each version is compared. Numerical experimentation is done for some known “ill-conditioned” problems.

MSC:

65F35 Numerical computation of matrix norms, conditioning, scaling
65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] DOI: 10.1016/0024-3795(80)90226-8 · Zbl 0439.65020 · doi:10.1016/0024-3795(80)90226-8
[2] Barren R., ”Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (1994)
[3] DOI: 10.1137/0703035 · Zbl 0143.37402 · doi:10.1137/0703035
[4] DOI: 10.1137/S1064827594271421 · Zbl 0856.65019 · doi:10.1137/S1064827594271421
[5] DOI: 10.1137/S1064827595294691 · Zbl 0930.65027 · doi:10.1137/S1064827595294691
[6] DOI: 10.1007/BF01930845 · Zbl 0409.65022 · doi:10.1007/BF01930845
[7] Bruaset A. M., Pitman Research Notes 328, in: ”A Survey of Preconditioned Iterative Methods” (1995)
[8] Buchanan, J. L. and Turner, P. R. 1992.”Numerical Methods and Analysis”, 371–388. McGraw-Hill Book Company.
[9] DOI: 10.1137/S0036144594276474 · Zbl 0863.65013 · doi:10.1137/S0036144594276474
[10] DOI: 10.1002/fld.1650120503 · Zbl 0722.76043 · doi:10.1002/fld.1650120503
[11] Chow E., ”Approximate Inverse Preconditioners for General Sparse Matrices (1994)
[12] DOI: 10.1080/00207169208804097 · Zbl 0762.65025 · doi:10.1080/00207169208804097
[13] Drako N., ”Iterative Methods” (1997)
[14] DOI: 10.1007/BF02243566 · Zbl 0438.65037 · doi:10.1007/BF02243566
[15] DOI: 10.1007/BF01385614 · Zbl 0714.65056 · doi:10.1007/BF01385614
[16] DOI: 10.1137/1036057 · Zbl 0814.65046 · doi:10.1137/1036057
[17] DOI: 10.1137/S1064827594276552 · Zbl 0872.65031 · doi:10.1137/S1064827594276552
[18] Hanke M., Pitman Research Notes 327, in: ”Conjugate Gradient Type Methods for ill-posed Problems” (1995)
[19] DOI: 10.1088/0266-5611/12/2/004 · Zbl 0859.65141 · doi:10.1088/0266-5611/12/2/004
[20] DOI: 10.1093/imamat/20.1.61 · Zbl 0364.65028 · doi:10.1093/imamat/20.1.61
[21] DOI: 10.1137/0614004 · Zbl 0767.65037 · doi:10.1137/0614004
[22] Mitchell, A. R. and Griffiths, D. F. 1987.”The Finite Difference Method in Partial Differential Equations”, 154–159. John Wiley & Sons.
[23] DOI: 10.1137/0912058 · Zbl 0733.65023 · doi:10.1137/0912058
[24] DOI: 10.1016/0377-0427(88)90345-7 · Zbl 0662.65028 · doi:10.1016/0377-0427(88)90345-7
[25] Shewchuk J. R., CMU-CS-94-125, in: ”An Introduction to die Conjugate Gradient Method Without the Agonizing Pain” (1994)
[26] Smith G. D., Oxford Applied Mathematics and Computing Science Series, in: ”Numerical Solution of Partial Differential Equations: Finite Difference Methods” (1993)
[27] Strakos, Z. 1991.”On the Real Convergence Rate of die Conjugate Gradient Method, Linear Algebra and its Applications”154–156. 535–549.
[28] DOI: 10.1007/BF01389450 · Zbl 0596.65015 · doi:10.1007/BF01389450
[29] Van Der Vorst H. A., Iterative Methods in Linear Algebra pp 67– (1992)
[30] Vassilenvski P. S., J. Numer. Linear Algebra 1 pp 59– (1992)
[31] Honma C., ”Approximate Inverse Preconditioners for the Conjugate Gradient Method, Thesis” (1999)
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.