ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

In minisymposium: Advances in Krylov Subspace Methods

Tue 11:30–12:00, Auditorium Jean Monnet
Flexible inner-outer Krylov subspace methods based on the Hessenberg procedure for shifted linear systems
Xianming Gu (University of Groningen)
Joint work with Ting-Zhu Huang (Univ. of Electron. Sci. & Techn. of China); Bruno Carpentieri (Nottingham Trent Univ., Clifton Campus).

Many computational science applications require to solve simultaneously a sequence of shifted linear systems of the form

\begin{equation} (A - \sigma_k I)x^{(k)} = b,\quad \sigma_k \in \mathbb{C},\quad k = 1,2,\ldots,s, \label{eq1.1} \end{equation}

where $A\in \mathbb{C}^{n\times n}$ is a non-Hermitian matrix, $x^{(k)}$ is the unknown vector and $b$ is the right-hand side. Such a sequence can be solved simultaneously at the cost of a single solve by using shifted Krylov subspace methods (KSMs), exploiting the shift-invariance property of Krylov subspaces

\begin{equation} \mathcal{K}_m(A, b) = \mathcal{K}_m(A - \sigma I, b),\quad \forall m \in \mathbb{N}^+,\quad \forall \sigma \in \mathbb{C}. \label{eq1.2} \end{equation}

The restarted GMRES method is a widely popular choice for solving (\ref{eq1.1}), see [1]. One problem, however, is that the computed GMRES shifted residuals are not collinear in general after the first restart. Additionally, the Arnoldi procedure employed in GMRES tends to be expensive when the restart parameter becomes large. To alleviate these difficulties, we extend the restarted CMRH [2] method, which is similar to the restarted shifted GMRES method but is much cheaper, for solving (\ref{eq1.1}).

In practice, preconditioning shifted systems (\ref{eq1.1}) is necessary and this remains an open question, because standard preconditioning techniques may destroy the shift-invariance property. In this work, we build a flexible inner-outer scheme, where the inner solver is a multi-shift KSM that acts as a preconditioner for an outer flexible CMRH (FCMRH) method. Numerical results show that the new nested scheme based on the Hessenberg procedure is very competitive, compared to the early established FOM-FGMRES in [3] in terms of CPU time.

  1. A. Frommer, U. Glässner, Restarted GMRES for shifted linear systems, SIAM J. Sci. Comput., 19 (1998), pp. 15-26.
  2. H. Sadok, CMRH: A new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm, Numer. Algorithms, 20 (1999), pp. 303-321.
  3. M. Baumann, M. B. van Gijzen, Nested Krylov methods for shifted linear systems, SIAM J. Sci. Comput., 37 (2015), pp. S90-S112.