Restarted GMRES Method Augmented with the Combination of Harmonic Ritz Vectors and Error Approximations
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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:54566", author = "Qiang Niu and Linzhang Lu", title = "Restarted GMRES Method Augmented with the Combination of Harmonic Ritz Vectors and Error Approximations", 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.", volume = "6", number = "8", pages = "925-8", }
