Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Krylov subspace methods for solving large unsymmetric linear systems

Author: Y. Saad
Journal: Math. Comp. 37 (1981), 105-126
MSC: Primary 65F10
MathSciNet review: 616364
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] W. E. Arnoldi, "The principle of minimized iterations in the solution of the matrix eigenvalue problem," Quart. Appl. Math., v. 9, 1951, pp. 17-29. MR 0042792 (13:163e)
  • [2] O. Axelsson, Solution of Linear Systems of Equations: Iterative Methods, Lecture Notes in Math., vol. 572 (V. A. Barker, Ed.), Springer-Verlag, Berlin and New York, 1977, pp. 1-51. MR 0448834 (56:7139)
  • [3] A. Björk & T. Elfving, "Accelerated projection methods for computing pseudo inverse solutions of systems of linear equations," BIT, v. 19, 1979, pp. 145-163. MR 537775 (80e:65048)
  • [4] A. Clayton, Further Results on Polynomials Having Least Maximum Modules Over an Ellipse in the Complex Plane, UKAEA Report AEEW-7348, 1963.
  • [5] 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.
  • [6] D. K. Faddeev & V. N. Faddeeva, Computational Methods of Linear Algebra, Freeman, San Francisco, Calif., 1963. MR 0158519 (28:1742)
  • [7] A. S. Householder, The Theory of Matrices in Numerical Analysis, Blaisdell, New York, 1964. MR 0175290 (30:5475)
  • [8] M. A. Krasnoselskii et al., Approximate Solutions of Operator Equations, Wolters-Noordhoff, Groningen, 1972. MR 0385655 (52:6515)
  • [9] C. C. Lanczos, "Solution of systems of linear equations by minimized iterations," J. Res. Nat. Bur. Standards, v. 49, 1952, pp. 33-53. MR 0051583 (14:501g)
  • [10] V. I. Lebedev, "Iterative methods for solution of operator equations with their spectrum on several intervals," Ž. Vyčisl. Mat. i Mat. Fiz., v. 9, 1969, pp. 1247-1252. MR 0272171 (42:7052)
  • [11] G. G. Lorentz, Approximation of Functions, Holt, Rinehart & Winston, New York, 1966. MR 0213785 (35:4642)
  • [12] 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.
  • [13] C. C. Paige, "Bidiagonalization of matrices and solution of linear equations," SIAM J. Numer. Anal., v. 11, 1974, pp. 197-209. MR 0341842 (49:6588)
  • [14] C. C. Paige & M. A. Saunders, "Solution of sparse indefinite systems of linear equations," SIAM J. Numer. Anal., v. 12, 1975, pp. 617-629. MR 0383715 (52:4595)
  • [15] B. N. Parlett, "A new look at the Lanczos algorithm for solving symmetric systems of linear equations," Linear Algebra Appl., v. 29, 1980, pp. 323-346. MR 562767 (83e:65064)
  • [16] J. K. Reid, "On the method of conjugate gradients for the solution of large sparse systems of linear equations," in Large Sparse Sets of Linear Equations (J. K. Reid, Ed.), Academic Press, New York, 1971. MR 0341836 (49:6582)
  • [17] T. J. Rivlin, The Chebyshev Polynomials, Wiley, New York, 1976. MR 0450850 (56:9142)
  • [18] Y. Saad, "Variations on Arnoldi's method for computing eigenelements of large unsymmetric matrices," Linear Algebra Appl., v. 34, 1980, pp. 269-295. MR 591435 (81m:65055)
  • [19] 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.
  • [20] G. W. Stewart, Introduction to Matrix Computation, Academic Press, New York, 1973. MR 0458818 (56:17018)
  • [21] H. L. Stone, "Iterative solution of implicit approximations of multidimensional partial differential equations," SIAM J. Numer. Anal., v. 5, 1968, pp. 530-558. MR 0238504 (38:6780)
  • [22] R. S. Varga "A comparison of the successive overrelaxation method and semi-iterative methods using Chebyshev polynomials," J. Soc. Indust. Appl. Math., v. 5, 1957, pp. 39-46. MR 0090129 (19:772d)
  • [23] H. E. Wrigley, "Accelerating the Jacobi method for solving simultaneous equations by Chebyshev extrapolation when the eigenvalues of the iteration matrtix are complex," Comput. J., v. 6, 1963, pp. 169-176. MR 0152115 (27:2095)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F10

Retrieve articles in all journals with MSC: 65F10

Additional Information

Article copyright: © Copyright 1981 American Mathematical Society

American Mathematical Society