QMR: a quasi-minimal residual method for non-Hermitian linear systems
Tóm tắt
The biconjugate gradient (BCG) method is the “natural” generalization of the classical conjugate gradient algorithm for Hermitian positive definite matrices to general non-Hermitian linear systems. Unfortunately, the original BCG algorithm is susceptible to possible breakdowns and numerical instabilities. In this paper, we present a novel BCG-like approach, the quasi-minimal residual (QMR) method, which overcomes the problems of BCG. An implementation of QMR based on a look-ahead version of the nonsymmetric Lanczos algorithm is proposed. It is shown how BCG iterates can be recovered stably from the QMR process. Some further properties of the QMR approach are given and an error bound is presented. Finally, numerical experiments are reported.
Tài liệu tham khảo
Duff, I.S., Grimes, R.G., Lewis, J.G. (1989): Sparse matrix test problems. ACM Trans. Math. Softw.15, 1–14
Faber, V., Manteuffel, T. (1984): Necessary and sufficient conditions for the existence of a conjugate gradient method. SIAM J. Numer. Anal.21, 352–362
Fischer, B., Freund, R.W. (1990): On the constrained Chebyshev approximation problem on ellipses. J. Approx. Theory62, 297–315
Fletcher, R. (1976): Conjugate gradient methods for indefinite systems. In: G. A. Watson, ed., Numerical Analysis Dundee 1975, pp. 73–89. Lecture Notes in Mathematics 506. Springer, Berlin Heidelberg New York
Freund, R.W. (1989): Conjugate gradient type methods for linear systems with complex symmetric coefficient matrices. Technical Report 89.54, RIACS, NASA Ames Research Center
Freund, R.W., Gutknecht, M.H., Nachtigal, N.M. (1990): An implementation of the lookahead Lanczos algorithm for non-Hermitian matrices, Part. I. Technical Report 90.45, RIACS, NASA Ames Research Center
Freund, R.W., Nachtigal, N.M. (1990): An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices, Part II. Technical Report 90.46, RIACS, NASA Ames Research Center
Golub, G.H., Van Loan, C.F. (1983): Matrix computations. The Johns Hopkins University Press, Baltimore
Gutknecht, M.H. (1990): A completed theory of the unsymmetric Lanczos process and related algorithms, Part II. IPS Research Report No. 90-16, Zürich
Gutknecht, M.H. (1990): A completed theory of the unsymmetric Lanczos process and related algorithms, Part II. IPS Research Report No. 90-16, Zürich
Hestenes, M.R., Stiefel, E. (1952): Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand.49, 409–436
Lanczos, C. (1950): An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Natl. Bur. Stand.45, 255–282
Lanczos, C. (1952): Solution of systems of linear equations by minimized iterations. J. Res. Natl. Bur. Stand.49, 33–53
Manteuffel, T.A. (1977): The Tchebychev iteration for nonsymmetric linear systems. Numer. Math.28, 307–327
Meijerink, J.A., van der Vorst, H.A. (1977): An interative solution for linear systems of which the coefficient matrix is a symmetricM-matrix. Math. Comp.31, 148–162
Paige, C.C., Saunders, M.A. (1975): Solution of sparse indefinite systems of linear equations. SIAM J. Numer. Anal.12, 617–629
Parlett, B.N. (1990): Reduction to tridiagonal form and minimal realizations. Preprint, Berkeley
Parlett, B.N., Taylor, D.R., Liu, Z.A. (1985): A look-ahead Lanczos algorithm for unsymmetric matrices. Math. Comp.44, 105–124
Saad, Y. (1982): The Lanczos biorthogonalization algorithm and other oblique projection methods for solving large unsymmetric systems. SIAM J. Numer. Anal.19, 485–506
Saad, Y. (1990): SPARSKIT: a basic tool kit for sparse matrix computations. Technical Report 90.20, RIACS, NASA Ames Research Center
Saad, Y., Schultz, M.H. (1986): GMRES a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput.7, 856–869
Sonneveld, P. (1989): CGS, a fast Lanczos-type solver for nonsymmetric linear systems. SIAM J. Sci. Stat. Comput.10, 36–52
Taylor, D.R. (1982): Analysis of the look ahead Lanczos algorithm. Ph.D. Dissertation, University of California Berkeley
van der Vorst, H.A. (1990): Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. Preprint, Utrecht
Wilkinson, J.H. (1965): The Algebraic Eigenvalue Problem. Oxford University Press, Oxford