ANZIAM J. 49 (2007), no. 2, pp. 293–308.
Usage of the convergence test of the residual norm in the Tsuno–Nodera version of the GMRES algorithm
K. Moriya† T. Nodera
Ohi-Branch
Nikon System Inc.
Japan
kmoriya@nikon-sys.co.jp		 Department of Mathematics
Keio University
Japan
nodera@math.keio.ac.jp
Received 13 October, 2005; revised 15 January, 2007

Abstract

Tsuno and Nodera proposed a new variant of the GMRES(m) algorithm. Their algorithm is referred to as the GMRES(\leqslant \! m_{\max }) algorithm and performs the restart process adaptively, considering the distribution of the zeros of the residual polynomial. However, unless the zeros of the residual polynomial are distributed uniformly, m_{\max } is always chosen and their algorithm becomes almost the same as the GMRES(m) algorithm with m=m_{\max }.

In this paper, we include a convergence test for the residual norm in the GMRES(\leqslant \! m_{\max }) algorithm and propose a new restarting technique based on two criteria. Even if the distribution of zeros does not become uniform, the restart can be performed by using the convergence test of the residual norm. Numerical examples simulated on a Compaq Beowulf computer demonstrate that the proposed technique accelerates the convergence of the GMRES(\leqslant \! m_{\max }) algorithm.

Download the article in PDF format (size 200 Kb)

2000 Mathematics Subject Classification: primary 65F10; secondary 65M12
(Metadata: XML, RSS, BibTeX) MathSciNet: MR2376???
†indicates author for correspondence

References

  1. W. Arnoldi, “The principle of minimized iterations in the solution of the matrix eigenvalue problem”, Quart. Appl. Math. 9 (1951) 17–29. MR42792
  2. J. Baglama, D. Calvetti, G. H. Golub and L. Reichel, “Adaptively preconditioned GMRES algorithms”, SIAM J. Sci. Comput. 20 (1998) 373–390. MR1639130
  3. A. Chapman and Y. Saad, “Deflated and augment Krylov subspace techniques”, Numer. Lin. Algebra Appl. 4 (1997) 43–66. MR1442463
  4. M. Eiermann, O. G. Ernst and O. Schneider, “Analysis of acceleration strategies for restarted minimal residual methods”, J. Comput. Appl. Math. 123 (2000) 261–292. MR1798529
  5. R. W. Freund, “Quasi-kernel polynomials and their use in non-Hermitian matrix iterations”, J. Comp. Appl. Math. 43 (1992) 135–158. MR1193298
  6. W. Joubert, “Lanczos methods for the solution of nonsymmetric systems of linear equations”, SIAM J. Matrix. Anal. Appl. 13 (1992) 928–943. MR1168086
  7. MatrixMarket, http://math.nist.gov/matrixmarket/.
  8. R. B. Morgan, “A restarted GMRES method augmented with eigenvectors”, SIAM J. Matrix Anal. Appl. 16 (1995) 1154–1171. MR1351462
  9. R. B. Morgan, “Implicitly restarted GMRES and Arnoldi methods for nonsymmetric systems of equations”, SIAM J. Matrix Anal. Appl. 21 (2000) 1112–1135. MR1745522
  10. K. Moriya and T. Nodera, “The DEFLATED-GMRES(m,k) method with switching the restart frequency dynamically”, Numer. Lin. Algebra Appl. 7 (2000) 569–584. MR1802360
  11. N. M. Nachtigal, L. Reichel and L. N. Trefethen, “A hybrid GMRES algorithm for nonsymmetric linear systems”, SIAM J. Matrix. Anal. Appl. 13 (1992) 796–825. MR1168080
  12. Y. Saad and M. K. Schultz, “GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems”, SIAM J. Sci. Stat. Comput. 7 (1986) 856–869. MR848568
  13. N. Tsuno and T. Nodera, “The speedup of the GMRES(m) method using the early restarting procedure”, Trans. Inform. Process. Soc. Japan 40 (1999) 1760–1773, (in Japanese). MR1691849
  14. J. Zítko, “Using successive approximations for improving the convergence of GMRES method”, Appl. Math. 43 (1998) 321–350. MR1644136
  15. J. Zítko, “Convergence conditions for a restarted GMRES method augmented with eigenspaces”, Numer. Lin. Algebra Appl. 12 (2005) 373–390. MR2139532