Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Iterative methods for linear systems : theory and applications
Olshanskii M., Tyrtyshnikov E., SIAM, Philadelphia, PA, 2014. 263 pp.  Type: Book (978-1-611973-45-7)
Date Reviewed: Feb 25 2015

The term “linear systems” in the title refers to equations of the form Ax = b, where x and b are elements of a Euclidean space and A is a nonsingular matrix. Iterative methods for solving these systems have been used since well before the advent of computers. They are especially efficient for large systems where restrictions on time or space make direct solution methods impractical. Each iteration of these procedures requires not much more computation than one matrix-vector product, and storage is required only for the matrix and a few vectors. Although convergence is only linear, an acceptable approximation to the solution can be obtained faster than direct methods provided the iterative method is well matched to the problem.

According to the preface, this text grew out of material previously used in numerical linear algebra courses. The topics include basic iterative methods such as Jacobi and Gauss-Seidel, as well as the more complex multigrid and domain decomposition methods. The authors introduce preconditioners and iteration matrices early on and use them in describing and analyzing the methods. An entire chapter is devoted to Toeplitz systems and their solution with circulant matrices as preconditioners. The final chapter describes particular boundary-value problems and their approximation by linear algebraic systems.

In its focus on Krylov subspace sequences, this work differs from other textbooks on iterative methods [1]. A Krylov sequence (K0, K1, …) of nested subspaces is determined by a matrix B and a single vector f. Specifically, if K0=span(f) then Ki+1= span(f, Ki, BKi). The matrix B is often A, the matrix of the system or some combination of A with the preconditioner. The vector f is usually an element of the range space of A, such as b. The authors use these sequences to describe and analyze iterative methods. As an example, for the minimum residual method (MNRES), the matrix for the Krylov spaces is A, the vector Ax0-b for some initial estimate x0. The ith iterate of MNRES is found by minimizing the norm of Ax-b for x in Ki.

They also give a result from Chou [2], which shows that Krylov sequences are optimal in a certain sense. That is, if you define another nested sequence of subspaces (L0, L1, …) and propose an algorithm where each iterate zi minimizes the norm of the residual over Li, and if the new algorithm takes k iterations to achieve |Azk-b| < ε, then there is a version of MNRES using the Krylov sequence that will achieve the same accuracy in at least 2k+1 iterations. The new algorithm may be faster, but not by orders of magnitude.

Although the authors have tried to achieve a textbook style of exposition rather than that of a research paper, they present these iterative methods and convergence results as a sequence of topics without much motivation or connecting exposition. In the chapter on Toeplitz matrices, there should be a paragraph or two explaining why Toeplitz matrices form a very important class of matrices. Also, there is no need for a proof of the optimality result for Krylov sequences. It is more important to explain the significance of the result.

I did like the historical note in the preface, where I discovered that Krylov’s first use of the subspace sequence was in a 1931 paper on a method to determine the characteristic polynomial of a matrix.

Reviewer:  Charles R. Crawford Review #: CR143204 (1506-0449)
1) Saad, Y. Iterative methods for sparse linear systems (2nd ed.). SIAM, Philadelphia, PA, 2003.
2) Chou, A. W. On the optimality of Krylov information. Journal of Complexity 3 (1987), 26–40.
Bookmark and Share
  Reviewer Selected
Linear Systems (Direct And Iterative Methods) (G.1.3 ... )
Numerical Algorithms (G.1.0 ... )
Numerical Algorithms And Problems (F.2.1 )
Would you recommend this review?
Other reviews under "Linear Systems (Direct And Iterative Methods)": Date
Cyber-physical systems: a model-based approach
Taha W., Taha A., Thunberg J.,  Springer International Publishing, Cham, Switzerland, 2021. 187 pp. Type: Book (978-3-030360-73-3)
Aug 4 2022
A fast direct solver for the biharmonic problem in a rectangular grid
Ben-Artzi M., Croisille J., Fishelov D.  SIAM Journal on Scientific Computing 31(1): 303-333, 2008. Type: Article
Mar 26 2009
 Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate
Chen Y., Davis T., Hager W., Rajamanickam S.  ACM Transactions on Mathematical Software 35(3): 1-14, 2008. Type: Article
Dec 2 2008

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2022 ThinkLoud, Inc.
Terms of Use
| Privacy Policy