Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Krylov subspace methods for solving large unsymmetric linear systems
HTML articles powered by AMS MathViewer

by Y. Saad PDF
Math. Comp. 37 (1981), 105-126 Request permission

Abstract:

Some algorithms based upon a projection process onto the Krylov subspace ${K_m} = \operatorname {Span}({r_0},A{r_0}, \ldots ,{A^{m - 1}}{r_0})$ are developed, generalizing the method of Conjugate gradients to unsymmetric systems. These methods are extensions of Arnoldi’s algorithm for solving eigenvalue problems. The convergence is analyzed in terms of the distance of the solution to the subspace ${K_m}$ and some error bounds are established showing, in particular, a similarity with the conjugate gradient method (for symmetric matrices) when the eigenvalues are real. Several numerical experiments are described and discussed.
References
  • W. E. Arnoldi, The principle of minimized iteration in the solution of the matrix eigenvalue problem, Quart. Appl. Math. 9 (1951), 17–29. MR 42792, DOI 10.1090/S0033-569X-1951-42792-9
  • Owe Axelsson, Solution of linear systems of equations: iterative methods, Sparse matrix techniques (Adv. Course, Technical Univ. Denmark, Copenhagen, 1976) Lecture Notes in Math., Vol. 572, Springer, Berlin, 1977, pp. 1–51. MR 0448834
  • Ȧke Björck and Tommy Elfving, Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations, BIT 19 (1979), no. 2, 145–163. MR 537775, DOI 10.1007/BF01930845
  • A. Clayton, Further Results on Polynomials Having Least Maximum Modules Over an Ellipse in the Complex Plane, UKAEA Report AEEW-7348, 1963. P. Concus & G. H. Golub, A Generalized Conjugate Gradient Method for Non-Symmetric Systems of Linear Equations, Report STAN-CS-75-535, Computer Science Dept., Stanford University, 1976.
  • D. K. Faddeev and V. N. Faddeeva, Computational methods of linear algebra, W. H. Freeman and Co., San Francisco-London, 1963. Translated by Robert C. Williams. MR 0158519
  • Alston S. Householder, The theory of matrices in numerical analysis, Blaisdell Publishing Co. [Ginn and Co.], New York-Toronto-London, 1964. MR 0175290
  • M. A. Krasnosel′skiĭ, G. M. Vaĭnikko, P. P. Zabreĭko, Ya. B. Rutitskii, and V. Ya. Stetsenko, Approximate solution of operator equations, Wolters-Noordhoff Publishing, Groningen, 1972. Translated from the Russian by D. Louvish. MR 0385655
  • Cornelius Lanczos, Solution of systems of linear equations by minimized-iterations, J. Research Nat. Bur. Standards 49 (1952), 33–53. MR 0051583
  • V. I. Lebedev, Iterative methods of solving operator equations with spectrum located on several segments, Ž. Vyčisl. Mat i Mat. Fiz. 9 (1969), 1247–1252 (Russian). MR 272171
  • G. G. Lorentz, Approximation of functions, Holt, Rinehart and Winston, New York-Chicago, Ill.-Toronto, Ont., 1966. MR 0213785
  • T. A. Manteuffel, An Iterative Method for Solving Nonsymmetric Linear Systems With Dynamic Estimation of Parameters, Report UIUCDCS-R-75-758, Dept. of Computer Science, Univ. of Illinois at Urbana-Champaign; Ph.D. thesis, 1975.
  • C. C. Paige, Bidiagonalization of matrices and solutions of the linear equations, SIAM J. Numer. Anal. 11 (1974), 197–209. MR 341842, DOI 10.1137/0711019
  • C. C. Paige and M. A. Saunders, Solutions of sparse indefinite systems of linear equations, SIAM J. Numer. Anal. 12 (1975), no. 4, 617–629. MR 383715, DOI 10.1137/0712047
  • B. N. Parlett, A new look at the Lanczos algorithm for solving symmetric systems of linear equations, Linear Algebra Appl. 29 (1980), 323–346. MR 562767, DOI 10.1016/0024-3795(80)90248-7
  • J. K. Reid, On the method of conjugate gradients for the solution of large sparse systems of linear equations, Large sparse sets of linear equations (Proc. Conf., St. Catherine’s Coll., Oxford, 1970) Academic Press, London, 1971, pp. 231–254. MR 0341836
  • Theodore J. Rivlin, The Chebyshev polynomials, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 0450850
  • Y. Saad, Variations on Arnoldi’s method for computing eigenelements of large unsymmetric matrices, Linear Algebra Appl. 34 (1980), 269–295. MR 591435, DOI 10.1016/0024-3795(80)90169-X
  • P. E. Saylor, Richardson’s Iteration With Dynamic Parameters and the SIP Approximate Factorization for the Solution of the Pressure Equation, Society of Petroleum Engineers of AIME Fifth Symposium on Reservoir Simulation, Denver, Colorado, 1979, SPE 7688.
  • G. W. Stewart, Introduction to matrix computations, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1973. MR 0458818
  • Herbert L. Stone, Iterative solution of implicit approximations of multidimensional partial differential equations, SIAM J. Numer. Anal. 5 (1968), 530–558. MR 238504, DOI 10.1137/0705044
  • Richard S. Varga, A comparison of the successive overrelaxation method and semi-iterative methods using Chebyshev polynomials, J. Soc. Indust. Appl. Math. 5 (1957), 39–46. MR 90129
  • H. E. Wrigley, Accelerating the Jacobi method for solving simultaneous equations by Chebyshev extrapolation when the eigenvalues of the iteration matrix are complex, Comput. J. 6 (1963/64), 169–176. MR 152115, DOI 10.1093/comjnl/6.2.169
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC: 65F10
  • Retrieve articles in all journals with MSC: 65F10
Additional Information
  • © Copyright 1981 American Mathematical Society
  • Journal: Math. Comp. 37 (1981), 105-126
  • MSC: Primary 65F10
  • DOI: https://doi.org/10.1090/S0025-5718-1981-0616364-6
  • MathSciNet review: 616364