Global GMRES with Deflated Restarting for Families of Shifted Linear Systems

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.

• Jing Meng
• Peiyong Zhu
• Houbiao Li

• Shifted linear systems
• global Krylov subspace
• GLGMRESIR
• GLGMRESIRsh
• harmonic Ritz matrix
• harmonic Ritz vector.

[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.