Eugene Vecharynski
The convergence of restarted GMRES for normal matrices is sublinear.

University of Colorado Denver
Yaugen.Vecharynski@cudenver.edu
Julien Langou

While a lot of efforts have been put in the characterization of the convergence of full GMRES, we have noticed that very few efforts have been made in characterizing the convergence of restarted GMRES despite the fact that this latter is the most practically used. Our current research aimed to better understand restarted GMRES.

Our main result proves that the convergence of restarted GMRES for normal matrices is sublinear. That is to say if after one GMRES cycle we have observed a given residual decrease, then the next GMRES cycle will necessarily have a smaller decrease. This writes:

$$\Vert r_k \Vert _2^2 \leq \Vert r_{k-1} \Vert _2 \Vert r_{k+1} \Vert _2.$$

The proof relies on the observation that GMRES($A$,$m$,$r_0$) and GMRES($A^H$,$m$,$r_0$) both provide the same residual norm after one cycle.

From this main theorem flow two corollaries. First, we can characterize the convergence of GMRES($n-1$) for normal matrices. In this case, the convergence is:

$$\Vert r_k \Vert = \Vert r_1 \Vert \left( \frac{ \Vert r_1\Vert } { \Vert r_0 \Vert } \right)^{k-1} .$$

Second, we can rederive a result from Baker, Jessup and Manteuffel (2005) about alternating residuals for GMRES(n-1) applied to Hermitian or Skew-Hermitian matrices. The result of Baker, Jessup and Manteuffel (2005) is

$$r_{k+1} = r_{k-1} \alpha_k,$$

where $\alpha_k$ is a scalar. Our contribution is to present another proof and to fully characterize $\alpha_k$ in term of $r_0$ and $r_1$. This means that, in the Hermitian/Skew-Hermitian case, not only $\Vert r_{k+1} \Vert$ is known from $\Vert r_0\Vert$ and $\Vert r_1\Vert$ (as in the normal case) but indeed $r_{k+1}$ is known from $r_0$ and $r_1$.

We note that when the matrix is nonnormal, the main statement is false. (The convergence of restarted GMRES is not necessarily sublinear.)

These results are new to our knowledge.