Global GMRES with Deflated Restarting for Families of Shifted Linear Systems

Authors: Jing Meng, Peiyong Zhu, Houbiao Li

Abstract:

Many problems in science and engineering field require the solution of shifted linear systems with multiple right hand sides and multiple shifts. To solve such systems efficiently, the implicitly restarted global GMRES algorithm is extended in this paper. However, the shift invariant property could no longer hold over the augmented global Krylov subspace due to adding the harmonic Ritz matrices. To remedy this situation, we enforce the collinearity condition on the shifted system and propose shift implicitly restarted global GMRES. The new method not only improves the convergence but also has a potential to simultaneously compute approximate solution for the shifted systems using only as many matrix vector multiplications as the solution of the seed system requires. In addition, some numerical experiments also confirm the effectiveness of our method.

Keywords: Shifted linear systems, global Krylov subspace, GLGMRESIR, GLGMRESIRsh, harmonic Ritz matrix, harmonic Ritz vector.

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

References:

[1] Jacques Bloch and Tilo Wettig. Domain wall and overlap fermions at nonzero quark chemical potential. Physical Review D, 76(11):114511, 2007.
[2] Ronald F Boisvert, Roldan Pozo, Karin A Remington, Richard F Barrett, and Jack Dongarra. Matrix market: a web resource for test matrix collections. In Quality of Numerical Software, pages 125–137, 1996.
[3] Dean Darnell, Ronald B Morgan, and Walter Wilcox. Deflated gmres for systems with multiple shifts and multiple right hand sides. Linear Algebra and its Applications, 429(10):2415–2434, 2008.
[4] Biswa Nath Datta and Youcef Saad. Arnoldi methods for large sylvester like observer matrix equations, and an associated algorithm for partial spectrum assignment. Linear Algebra and its Applications, 154:225–244, 1991.
[5] Mark Embree. The tortoise and the hare restart gmres. SIAM review, 45(2):259–266, 2003.
[6] Roland W Freund. Solution of shifted linear systems by quasiminimal residual iterations. Numerical Linear Algebra, pages 101–121, 1993.
[7] Andreas Frommer. Bicgstab () for families of shifted linear systems. Computing, 70(2):87–109, 2003.
[8] Andreas Frommer and Uwe Gl¨assner. Restarted gmres for shifted linear systems. SIAM Journal on Scientific Computing, 19(1):15–26, 1998.
[9] Guiding Gu. Restarted gmres augmented with harmonic ritz vectors for shifted linear systems. International Journal of Computer Mathematics, 82(7):837–849, 2005.
[10] K Jbilou, A Messaoudi, and H Sadok. Global fom and gmres algorithms for matrix equations. Applied Numerical Mathematics, 31(1):49–63, 1999.
[11] Yiqin Lin. Implicitly restarted global fom and gmres for nonsymmetric matrix equations and sylvester equations. Applied mathematics and computation, 167(2):1004–1025, 2005.
[12] Ronald B Morgan. Gmres with deflated restarting. SIAM Journal on Scientific Computing, 24(1):20–37, 2002.
[13] Valeria Simoncini. On the convergence of restarted krylov subspace methods. SIAM Journal on Matrix Analysis and Applications, 22(2):430–452, 2000.
[14] Valeria Simoncini. Restarted full orthogonalization method for shifted linear systems. BIT Numerical Mathematics, 43(2):459–466, 2003.
[15] Peter Sonneveld and Martin B van Gijzen. Idr (s): A family of simple and fast algorithms for solving large nonsymmetric systems of linear equations. SIAM Journal on Scientific Computing, 31(2):1035–1062, 2008.
[16] Roland A Sweet. A parallel and vector variant of the cyclic reduction algorithm. SIAM journal on scientific and statistical computing, 9(4):761–765, 1988.
[17] Jasper van den Eshof and Gerard LG Sleijpen. Accurate conjugate gradient methods for families of shifted systems. Applied Numerical Mathematics, 49(1):17–37, 2004.