×

Minimum residual methods for augmented systems. (English) Zbl 0914.65026

From the authors’ abstract: For large systems of linear equations, iterative methods provide attractive solution techniques. We describe the applicability and convergence of iterative methods of Krylov subspace type for an important class of symmetric and indefinite matrix problems, namely augmented (or KKT) systems. Specifically, we consider preconditioned minimum residual methods and discuss indefinite versus positive definite preconditioning. For the natural choice of starting vector we prove that when the definite and indefinite preconditioners are related in the obvious way, MINRES and full GMRES give residual vectors with identical Euclidean norm at each iteration. Moreover, we show that the convergence of both methods is related to a system of normal equations for which the LSQR algorithm can be employed. As a side result, we give a rare example of a non-trivial normal(1) matrix where the corresponding inner product is explicitly known: a conjugate gradient method therefore exists and can be employed in this case.

MSC:

65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
65F50 Computational methods for sparse matrices

Software:

LSQR
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] W. Arnoldi,The principle of minimized iterations in the solution of the matrix eigenvalue problem, Quart. Appl. Math., 9 (1951), pp. 17–29. · Zbl 0042.12801
[2] Å. Björck,Iterative refinement of linear least squares solutions, BIT, 7 (1967), pp. 257–278. · Zbl 0159.20404
[3] R. Chandra,Conjugate Gradient Methods for Partial Differential Equations, PhD thesis, Yale University Res. Rep. 129, 1978.
[4] I. S. Duff,The solution of augmented systems, in Numerical Analysis 1993, D.F. Griffiths and G.A. Watson, eds., Longman, London, 1994, pp. 40–55. · Zbl 0796.65023
[5] S. Eisenstat,Some observations on the generalized conjugate gradient method, in Numerical Methods, V. Pereyra and A. Reinoza, eds., Lecture Notes in Mathematics, Volume 1005, Springer-Verlag, Berlin, 1983, pp. 99–107.
[6] H. C. Elman and D. J. Silvester,Fast nonsymmetric iterations and preconditioning for Navier-Stokes equations, SIAM J. Sci. Comput., 17 (1996), pp. 33–46. · Zbl 0843.65080
[7] V. Faber and T. Manteuffel,Necessary and sufficient conditions for the existence of a conjugate gradient method, SIAM J. Numer. Anal. 21 (1984), pp. 352–362. · Zbl 0546.65010
[8] B. Fischer,Polynomial Based Iteration Methods for Symmetric Linear Systems, Wiley-Teubner Series in Advances in Numerical Mathematics, Wiley-Teubner, Chichester, 1996. · Zbl 0852.65031
[9] M. Fortin and F. Brezzi,Mixed and Hybrid Finite Elements Methods, Springer-Verlag, Berlin, 1991. · Zbl 0788.73002
[10] R. W. Freund and N. M. Nachtigal,QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. Math., 60 (1991), pp. 315–339. · Zbl 0754.65034
[11] R. W. Freund and N. M. Nachtigal,A new Krylov-subspace method for symmetric indefinite linear systems, in Proceedings of the 14th IMACS World Congress on Computational and Applied Mathematics, W. F. Ames, ed., IMACS, 1994, pp. 1253–1256.
[12] G. H. Golub and C. F., Van Loan,Matrix Computations, 2nd ed., Johns Hopkins University Press, London, 1989. · Zbl 0733.65016
[13] C. Lanczos,An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Nat. Bur. Stand., 45 (1950), pp. 255–282.
[14] N. M. Nachtigal, S. C. Reddy and L. N. Trefethen,How fast are nonsymmetric matrix iterations?, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 778–795. · Zbl 0754.65036
[15] C. C. Paige and M. A. Saunders,Solution of sparse indefinite, systems of linear equations, SIAM J. Numer. Anal., 12 (1975), pp. 617–629. · Zbl 0319.65025
[16] C. C. Paige and M. A. Saunders,LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software 8 (1982), pp. 43–71. · Zbl 0478.65016
[17] Y. Saad and M. H. Schultz,GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856–869. · Zbl 0599.65018
[18] M. A. Saunders,Solution of sparse rectangular systems using LSQR and Craig, BIT, 35 (1995), pp. 588–604. · Zbl 0844.65029
[19] D. J. Silvester and A. J. Wathen,Fast iterative solution of stabilised Stokes systems part II: using general block preconditioners, SIAM J. Numer. Anal., 31 (1994), pp. 1352–1367. · Zbl 0810.76044
[20] G. Szegö,Orthogonal Polynomials, AMS Colloquium Publications XXIII (revised ed.), AMS, New York, 1959.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.