Restarted GMRES Method Augmented with the Combination of Harmonic Ritz Vectors and Error Approximations

Authors: Qiang Niu, Linzhang Lu

Abstract:

Restarted GMRES methods augmented with approximate eigenvectors are widely used for solving large sparse linear systems. Recently a new scheme of augmenting with error approximations is proposed. The main aim of this paper is to develop a restarted GMRES method augmented with the combination of harmonic Ritz vectors and error approximations. We demonstrate that the resulted combination method can gain the advantages of two approaches: (i) effectively deflate the small eigenvalues in magnitude that may hamper the convergence of the method and (ii) partially recover the global optimality lost due to restarting. The effectiveness and efficiency of the new method are demonstrated through various numerical examples.

Keywords: Arnoldi process, GMRES, Krylov subspace, systems of linear equations.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1061114

References:

[1] K. Baglama, D. Calvetti, G.H. Golub, and L. Reichel, Adaptively preconditioned GMRES algorithms, SIAM J. Sci. Comput., 20 (1998) 243-269.
[2] A. Baker, L. Jessup, and T. Manteuffel, A technique for accelerating the convergence of restarted GMRES, SIAM J. Matrix Anal. Appl., 26 (2005) 962-984.
[3] K. Burrage and J. Erhel, On the performance of various adaptive preconditioned GMRES strategies, Numer. Linear Algebra Appl., 5 (1998) 101-121.
[4] C. Le Calvez and B. Molina, Implicitly restarted and deflated GMRES, Numer. Algo., 21 (1999) 261-285.
[5] Z.-H. Cao, A note on the convergence behavior of GMRES, Appl. Numer. Math., 25 (1997) 13-20.
[6] B. Carpentieri, I.S. Duff, L. Giraud, A class of spectral two-level preconditioners, SIAM Journal on Scientific Computing, 25 (2003) 749- 765.
[7] T. Davis, University of Florida sparse matrix collection, http://www.cise.ufl.edu/research/ sparse/matrices, 2002.
[8] A. Chapman and Y. Saad, Deflated and augmented Krylov subspace techniques, Numer. Linear Algebra Appl., 4 (1997) 43-66.
[9] D. Darnell, R. B. Morgan, and W. Wilcox, Deflation of eigenvalues for iterative methods in lattice QCD, Nucl. Phys. B (Proc. Suppl.), 129 (2004) 856-858.
[10] E. De Sturler, Nested Krylov methods based on GCR, J. Comput. Appl. Math., 67 (1996) 15-41.
[11] E. De Sturler, Truncation strategy for optimal Krylov subspace methods, SIAM J. Numer. Anal., 36 (1999) 864-889.
[12] I. S. Duff, R. G. Grimes, and J. G. Lewis, Sparse matrix test problems, ACM Trans. Math. Soft., 15 (1989) 1-14.
[13] M. Eiermann, O. G. Ernst, and O. Schneider, Analysis of Acceleration Stategies for Restarted Minimal Residual Methods, J. Comput. Appl. Math., 123 (2000) 261-292.
[14] S. C.Eisenstat, H. C. Elman, and M. H. Schultz, Variational iterative methods for nonsymmetric systems of linear , SIAM J. Numer. Anal., 20 (1983) 345-357
[15] J. Erhel, K. Burrage, and B. Pohl, Restarted GMRES preconditioned by deflation, J. Comput. Appl. Math., 69 (1996) 303-318.
[16] J. Erhel and F. GuyomarcÔÇÿh, An Augmented Conjugate Gradient Method for solving consecutive symmetric positive definite systems, SIAM. J. Matrix Anal. Appl., 21 (2000) 1279-1299.
[17] L. Giraud, S. Gratton, E. Martin, Incremental spectral preconditioners for sequences of linear systems, Applied Numerical Mathematics, In Press.
[18] S.A. Kharchenko, A. Yeramin, Eigenvalue translation based preconditioners for the GMRES(k) method, Numer. Linear Algebra Appl. 2, (1995) 51-77.
[19] R. B. Morgan, A restarted GMRES method augmented with eigenvectors, SIAM J. Matrix Anal. Appl., 16 (1995) 1154-1171.
[20] R. B. Morgan, Implicitly restarted GMRES and Arnoldi methods for nonsymmetric systems of equations, SIAM J. Matrix Anal. Appl., 21 (2000) 1112-1135.
[21] R. B. Morgan, GMRES with deflated restarting, SIAM J. Sci. Comput., 24 (2002) 20-37.
[22] National Institute of Standards and Technology, Mathematical and Computatinal Sciences Division, Matrix Market, Available at http://math.nist.gov/MatrixMarket/
[23] S. Rollin and W. Fichtner, Improving the accurancy of GMRES with deflated restarting, SIAM J. Sci. Comput., 30 (2007) 232-245.
[24] Y. Saad and M. H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7 (1986) 856-869.
[25] Y. Saad, Iterative Methods for Sparse Linear Systems, PWS Publishing Company: Boston, MA, 1996.
[26] Y. Saad, A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Comput., 14 (1993) 461-469.
[27] Y. Saad, Analysis of augmented Krylov subspace methods, SIAM J. Matrix Anal. Appl., 18 (1997) 435-449.
[28] Y. Saad, A deflated version of the conjugate gradient algorithm, SIAM J. Sci. Comput., 21 (2000) 1909-1926.
[29] V. Simoncini, On the convergence of restarted Krylov subspace methods, SIAM J. Matrix Anal. Appl., 22 (2000) 430-452.
[30] V. Simoncini and D. B. Szyld, On the occurrence of superlinear convergence of exact and inexact Krylov subspace methods, SIAM Review., 47 (2005) 247-272.
[31] V. Simoncini and D. B. Szyld. Recent computational developments in Krylov subspace methods for linear systems, Numer. Linear Algebra Appl., 14 (2007) 1-59.
[32] H. A. van der Vorst and C. Vuik, The superlinear convergence behaviour of GMRES, J. Comput. Appl. Math., 48 (1993) 327-341.
[33] H. A. van der Vorst and C. Vuik, GMRESR: A family of nested GMRES methods, Numer. Linear Algebra Appl., 1 (1994) 369-386.
[34] J. R. Wallis, R. P. Kendall and T. E. Little Constraint residual acceleration of conjugate residual methods, presented at the SPE 1985 Reservoir Simulation Symmposium held in Dallas, Texas, 1985.