Keywords: Krylov subspace method, GMRES, weighted GMRES, left preconditioning, right preconditioning, weighted inner product, convergence analysis.

Mathematics Subject Classification: 65F10, 65F08, 65F35.

Communicated by Francoise Tisseur

Introduction↩︎

The GMRES algorithm [1], [2] is one of the most popular methods for solving general non-Hermitian linear systems. Yet, to this date, its convergence behaviour is not fully understood. While classical quantities such as the spectrum, the pseudo-spectrum, or the numerical range can provide insight in many situations, they do not offer a complete explanation of the observed residual decay. In particular, when standard sufficient conditions fail (for instance when the numerical range contains the origin), little can be concluded a priori about convergence.

A striking change of perspective was introduced by Greenbaum, Pták and Strakoš in [3]. Rather than attempting to deduce convergence from properties of a fixed matrix, they considered the inverse question: given a prescribed (non-increasing) residual convergence curve, does there exist a linear system whose GMRES residuals realize it? Their fundamental result shows that any admissible convergence curve can be realized by GMRES. Even more remarkably, this can be achieved while also prescribing the spectrum of the matrix arbitrarily, demonstrating that eigenvalues alone do not determine GMRES convergence.

In practice, GMRES is frequently modified either by changing the inner product (a method called weighted GMRES) or by introducing preconditioning. The purpose of this work is to analyze the convergence curves that can be achieved simultaneously either by weighted and unweighted GMRES, or by left and right preconditioned GMRES. It is shown that any two convergence curves can be simultaneously achieved as long as the exact solution is reached at the same iteration (1 and 7). This indicates that modifying the inner product or the position of the preconditioner can have a drastic impact on convergence. In 3, a linear system \(Ax = b\) and a preconditioner \(H\) are considered. It is proved that, if right preconditioned GMRES produces residuals \(\mathtt{r}_i := \| b - A x_i \|\) and left preconditioned GMRES produces residual \(\widetilde{\mathtt{r}}_i := \|H(b - A x_i)\|\), there exists another linear system \(\widetilde{A} \widetilde{x} = \widetilde{b}\) and preconditioner \(\widetilde{H}\) such that the convergence curves are reversed. What is meant by reversed is that right preconditioning \(\widetilde{A} \widetilde{x} = \widetilde{b}\) by \(\widetilde{H}\) produces the residual curve \(\| \widetilde{b} - \widetilde{A} \widetilde{x}_i \| = \widetilde{\mathtt{r}}_i\) while left preconditioning produces the residual curve \(\|\widetilde{H}(\widetilde{b} - \widetilde{A} \widetilde{x}_i ) \| = \mathtt r_i\).

The possibility for the efficiency of a preconditioner to depend on whether it is applied on the left or on the right has already been raised as early as in [4] (a main result of which can be found in [5]) and in [6]. See also the literature review in [7]. A key observation is that weighted GMRES provides a unifying framework for all preconditioned variants. This suggests extending the prescribed convergence curve analysis to the weighted setting first, and then deduce consequences for preconditioned GMRES. The viewpoint in [3] has already been refined and extended in several directions. Arioli, Pták and Strakoš [8] provided a complete parametrization of all systems generating a prescribed convergence curve (the APS parametrization), thereby making explicit the structure of the admissible pairs \((A,b)\). Meurant [9] further analyzed this parametrization and clarified its implications. In parallel, it was shown in [10] that not only the spectrum but also any prescribed set of harmonic Ritz values (i.e.the zeros of the GMRES residual polynomial) can be realized for a given convergence curve at any iteration, a result further developed in [11], [12]. Extensions to restarted and block variants of GMRES were established in [13] and [14], respectively. An analysis closely related to our work can be found in [15], where the residual and error convergence curves are prescribed simultaneously. Even though the norm of the error can also be viewed as a weighted norm of the residual, this setup is particular because the weight varies with the operator.

Understanding the convergence of weighted GMRES, an interesting question in itself, can also be viewed as a step toward understanding the convergence of standard GMRES. In recent work [16], Embree has extended the range of applicability of Elman’s convergence bound [17] by considering weighted GMRES. Indeed, as long as the eigenvalues are on one side of the origin, [16] proposes the construction of an inner product for which the field of values is also on one side of the origin, and hence the Elman bound applies. We view this as a very promising way of predicting the convergence of GMRES for a large class of problems, and we aim to provide some level of insight into the connection between the convergence of GMRES in the Euclidean norm and in the norm used for analysis.

Weighted GMRES is a term coined by Essai [18], who demonstrated that the convergence of restarted GMRES can be accelerated by incorporating a diagonal weight matrix into the inner product of the Arnoldi process at each restart. Receiving attention, Essai’s technique is analyzed from the angle of the Ritz values [19] and the eigenvectors [20], providing insights into use cases where this weighted method can be particularly beneficial. The abstract algorithm of GMRES using a non-standard inner product has been explored in [21], [22] and references therein. We also refer to [23] for a reflection about which norm should be considered to assess convergence. Earlier works on what is now called weighted GMRES include [24]–[28].

0.0.0.1 Outline

This manuscript starts with a preliminary section where we introduce GMRES and recall the original result from [3] about the prescription of convergence curves. The formalism for prescribed convergence curves is introduced, and in particular the notation \(g_i = \sqrt{\|r_{i-1}\|^2 - \|r_i\|^2}\) for the decrease in norm between two subsequent residuals (as in [3]). Prescribing a non-increasing convergence curve is the same as prescribing the quantities \(g_i\) stored in a vector \(g \in \mathbb{R}^n\). In 2, we present novel theoretical results about weighted GMRES and how it compares to GMRES in the Euclidean norm. Stemming from the fact that there are equivalences between weighted GMRES and preconditioned GMRES (under the right choices of linear systems, weights and preconditioners), we deduce in 3 some new results about prescribed convergence curves for left and right preconditioned GMRES. To complement our theoretical results, 4 provides numerical illustrations exploring the behavior of weighted and preconditioned GMRES in various circumstances. The MATLAB code reproducing the numerical experiments is openly available³. Moreover, as all the proofs are constructive, it also includes the implementation of examples that verify the theorems. Besides, we make available our MATLAB implementation of GMRES⁴, which accepts left/right preconditioners and change of inner product.

0.0.0.2 Flavour of our work

We present four results (in a simplified setting) that give a flavour of our work on weighted GMRES and on preconditioned GMRES.

0.0.0.3 Simultaneous prescription of convergence curves for weighted and unweighted GMRES.

The first result (2) is that, for any given system \(A x = b\) and prescribed convergence curve, there exists a Hermitian positive definite weight matrix \(M\) such that weighted GMRES applied to \(Ax=b\) realizes the prescribed convergence curve. The second result (4) considers two prescribed convergence curves (i.e. sequences of residual norm values) \((\mathtt{r}_i)_i\) and \((\widetilde{\mathtt{r}}_i)_i\): \[\mathtt{r}_0 > \mathtt{r}_1 > \mathtt{r}_2 > \dots \text{ for GMRES, and } \widetilde{\mathtt{r}}_0 > \widetilde{\mathtt{r}}_1 > \widetilde{\mathtt{r}}_2 > \dots \text{ for weighted GMRES.}\] We prove that, for a given Hermitian positive definite weight matrix \(M\), there exists a system \(Ax=b\) such that both convergence curves are realized if and only if there exists a non-singular upper triangular matrix \(T\) such that the singular values of \(T\) are the inverse square roots of the eigenvalues of \(M\), and \[\begin{pmatrix} \sqrt{\mathtt{r}_0^2 - \mathtt{r}_1^2}, & \sqrt{\mathtt{r}_1^2 - \mathtt{r}_2^2}, & \dots\end{pmatrix}^\top = T\, \begin{pmatrix} \sqrt{{\widetilde{\mathtt{r}}_0}^2 - {\widetilde{\mathtt{r}}_1}^2},& \sqrt{{\widetilde{\mathtt{r}}_1}^2 - {\widetilde{\mathtt{r}}_2}^2},& \dots\end{pmatrix}^\top.\] Additionally, the eigenvalues of \(A\) can be prescribed.

0.0.0.4 Simultaneous prescription of convergence curves for left and right preconditioned GMRES.

Consider two prescribed convergence curves \((\mathtt{r}_i)_i\) and \((\widetilde{\mathtt{r}}_i)_i\):

• \(\mathtt{r}_0 > \mathtt{r}_1 > \mathtt{r}_2 > \dots\) for right preconditioned GMRES,

• \(\widetilde{\mathtt{r}}_0 > \widetilde{\mathtt{r}}_1 > \widetilde{\mathtt{r}}_2 > \dots\) for left preconditioned GMRES.

The first result (7) is that there exists a system \(A x = b\) and a preconditioner \(H\) such that both convergence curves are realized. Additionally, the eigenvalues of \(AH\) (or \(HA\), which are the same since both matrices are similar) can be prescribed. The second result (9) is that, for a given preconditioner \(H\), there exists a system \(Ax=b\) such that both convergence curves are realized if and only if there exists a non-singular upper triangular matrix \(T\) such that the singular values of \(T\) are the inverse of those of \(H\) and \[\begin{pmatrix} \sqrt{\mathtt{r}_0^2 - \mathtt{r}_1^2}, & \sqrt{\mathtt{r}_1^2 - \mathtt{r}_2^2}, & \dots\end{pmatrix}^\top = T\, \begin{pmatrix} \sqrt{\widetilde{\mathtt{r}}_0^2 - {\widetilde{\mathtt{r}}_1}^2},& \sqrt{\widetilde{\mathtt{r}}_1^2 - \widetilde{\mathtt{r}}_2^2},& \dots\end{pmatrix}^\top.\] Additionally, the eigenvalues of \(AH\) (or, equivalently, of \(HA\)) can be prescribed.

0.0.0.5 Notation

We denote by \(\mathbb{R}_+\) the set of non-negative real values (including 0). Let \(n\in\mathbb{N}\). For any matrix \(A\in\mathbb{C}^{n\times n}\), \(A^*\) denotes its conjugate transpose and, if invertible, \(A^{-1}\) its inverse and \(A^{-*}\) the inverse of \(A^*\). We refer to \(A\) being “hpd” for Hermitian positive definite.

1 Preliminary on GMRES and convergence curve formalism↩︎

The objective of this section is to introduce GMRES as well as a framework for convergence analysis by prescribing convergence curves that is greatly inspired by [3].

We denote by \((A,b)\) the general linear system \[Ax = b,\] where \(A\in\mathbb{C}^{n\times n}\) is a non-singular matrix and \(b\in\mathbb{C}^n\) is a vector. Given an inner product \(\left\langle \cdot, \cdot\right\rangle\) and its associated norm \(\|\cdot\|\), we consider the application of the GMRES algorithm [1], [2] with a zero initial guess (\(x_0 = 0\)) to the system \((A, b)\). We refer to this procedure as GMRES(\(A,b\)). In this section, the inner product \(\left\langle \cdot, \cdot\right\rangle\) remains abstract. The method is associated with the Krylov subspaces \[\mathcal{K}_i(A, b) := \operatorname{span} \{b, Ab, A^2b, \dots, A^{i-1}b\} \qquad \forall i=1, \dots, n.\] At any iteration \(i=0,\dots,\dim \mathcal{K}_n(A, b)\), the approximate solution is denoted by \(x_i\) and the corresponding residual by \(r_i := b - A x_i\). By definition of GMRES, each residual is characterized by \[\label{eq:minim95pb} r_i \in b + A\mathcal{K}_i(A, b) \text{ and } \|r_i\| = \min_{x\in \mathcal{K}_i(A, b)} \|b-Ax\| = \min_{y\in A\mathcal{K}_i(A, b)} \|b-y\|.\tag{1}\]

The Krylov residual spaces \(A\mathcal{K}_i(A, b) = \operatorname{span}\{Ab, A^2b, \dots, A^ib\}\) play a key role in formalizing GMRES. These spaces are nested by definition, and we define the notion of nested residual basis:

The breakdown index of GMRES(\(A,b\)) is also the iteration at which GMRES finds the exact solution [2]. Since it does not depend on the choice of inner product, all weighted versions of GMRES(\(A,b\)) reach the exact solution at the same iteration.

Another interpretation of 1 is that \((b-r_i)\) is the orthogonal projection of \(b\) onto \(A\mathcal{K}_i(A, b)\). Consequently, \(r_i\) can also be expressed as \(r_i = b - \sum_{j=1}^i \left\langle b, w_j\right\rangle w_j\), in which \((w_j)_{j=1,\dots,m}\) is a nested, orthonormal basis of \(A\mathcal{K}_n(A, b)\). Since \(r_m = 0\), this implies that \(b = \sum_{j=1}^m \left\langle b, w_j\right\rangle w_j\), \(r_i = \sum_{j=i+1}^m \left\langle b, w_j\right\rangle w_j\), and that \[\label{eq:ip95b95wj} \abs{\left\langle b, w_j\right\rangle } = \sqrt{\|r_{j-1}\|^2 - \|r_j\|^2}.\tag{2}\] It turns out that the convergence of GMRES can be conveniently captured by these differences (as in [3]).

Many of the new results in this article are written in the residual decrease vector formalism. Next, we make explicit the meaning of prescribing a GMRES convergence curve through a residual decrease vector.

It can be observed from ?? at \(i=0\) that \(\| b \|\) is entirely defined by \(g\). Another key observation is that prescribing residuals through ?? restricts us to non-increasing convergence curves. This is a difference with [15] where error curves are prescribed that are not necessarily monotonic. For future reference, we recall in 1 the fundamental result of [3]. We do not recall the proof which is constructive and allows to explicitly define \((A,b)\).

While the original theorem is restricted to the case where no breakdown occurs before the last iteration, early termination of GMRES is considered in [11]. We next isolate a necessary and sufficient condition for GMRES\((A,b)\) to realize a given convergence curve. But first, we introduce two useful results about nested residual basis that are orthonormal.

In 2, it is assumed that the length \(m\) of \(g\) equals \(\dim \mathcal{K}_n(A, b)\). This is not strictly necessary because the equality could be recovered from ?? . However, we prefer to keep the assumption in order to emphasize that the breakdown index is fixed by the linear system.

We end this section with the relationship between two nested residual bases. This plays a fundamental role in subsequent results since we will be considering nested bases of the same space that are orthonormal with respect to different inner products. The following result is similar to [18] and [21] with the difference that we choose to consider bases for the whole of \(\mathbb{C}^n\).

Note that if \(m=n\) (no breakdown), then, in 3 , \(T\) is simply an upper triangular invertible matrix.

2 Weighted GMRES↩︎

Any Hermitian positive definite (hpd) matrix \(M\in\mathbb{C}^{n\times n}\) induces an inner product and a norm, respectively defined by \[\left\langle x, y\right\rangle _M := y^*Mx \qquad\text{ and }\qquad \|x\|_M := \sqrt{\left\langle x, x\right\rangle _M} \qquad\text{ for all } x,y\in\mathbb{C}^n.\] A matrix \(X\) is said to have \(M\)-orthonormal columns when \(X^*MX = I\) (the identity matrix). The notation \(^*\) invariably denotes the conjugate transpose of a vector or a matrix.

We call \(M\)-GMRES the GMRES algorithm resulting from the choice \(\left\langle \cdot, \cdot\right\rangle := \left\langle \cdot, \cdot\right\rangle _M\). In this formalism, \(I\)-GMRES refers to the Euclidean setting. Since the inner product \(\left\langle \cdot, \cdot\right\rangle\) remained abstract in the preceding section, all results presented before still hold for \(M\)-GMRES. Following 4, when stating that \(M\)-GMRES realizes the convergence curve induced by a residual decrease vector \(g\), the residuals are measured in the \(M\)-norm.

2.1 \(I\)-GMRES and \(M\)-GMRES↩︎

Let \(M\) be an hpd matrix. Let us begin with some natural relations between the \(k\)-th \(I\)-GMRES residual \(r_k\) and the \(k\)-th \(M\)-GMRES residual \(\widetilde{r}_k\). The initial guesses are still set to \(0\), so the only difference between both algorithms is the norm in which the minimization property is enforced. Denoting by \(\mu_{\min} (M)\) and \(\mu_{\max} (M)\), the extreme eigenvalues of \(M\), it follows that \[\label{eq:IM-GMRES-easy} \mu_{\min}(M)\|r_k\|_I^2 \leq \mu_{\min}(M)\| \widetilde{r}_k\|_I^2 \leq \| \widetilde{r}_k \|_M^2 \leq \| r_k\|_M^2 \leq \mu_{\max}(M) \| r_k \|_I^2,\tag{5}\] where the first and third inequalities come from the definition of GMRES, and the others are spectral estimates. In particular, with \(\kappa(M){ = \mu_{\max}(M) / \mu_{\min} (M)}\) the condition number of \(M\), we obtain \[\label{eq:IM-GMRES-easy2} \| r_k \|_I^2 \leq \| \widetilde{r}_k\|_I^2 \leq \kappa(M) \| r_k \|_I^2 \text{ and } \|\widetilde{r}_k\|_M^2 \leq \| r_k\|_M^2 \leq \kappa(M) \|\widetilde{r}_k\|_M^2.\tag{6}\] Additionally, \(r_0 = \widetilde{r_0}\) and the normalized residuals satisfy \[\label{eq:link95nomalized95residuals} \kappa(M)^{-1} \frac{\|\widetilde{r}_k\|_M^2}{\|\widetilde{r}_0\|_M^2} \leq \frac{ \| r_k \|_I^2}{\|r_0\|_I^2} \leq \kappa(M) \frac{\|\widetilde{r}_k\|_M^2}{\|\widetilde{r}_0\|_M^2}.\tag{7}\]

We next apply the formalism proposed by Ipsen in [29][Theorem 2.1 and Corollary 2.2] with some details of the proof from [30]. What is new here is that we extend (straightforwardly) the formalism to weighted GMRES and apply it to compare either the same residual in two norms, or the residuals of \(I\)- and \(M\)-GMRES.

Consider \(M\)-GMRES\((A,b)\) starting with \(\widetilde{r}_0 = b\). Up to convergence, the \(k\)-th residual is determined by \[\widetilde{r}_k = b - W_k\underbrace{(W_k^* M W_k)^{-1} W_k^* M b }_{:=y_0},\] for any matrix \(W_k \in \mathbb{C}^{n\times k}\) whose columns form a basis of \(A \mathcal{K}_k(A,b)\). Let \(B = (b \,\,\, W_k)\) be the concatenation of the right-hand-side and this basis. This gives a basis of the Krylov subspace \(\mathcal{K}_{k+1}(A,b)\). Moreover, \[B^* M B = \begin{pmatrix} b^* M b & b^*M W_k \\ W_k^* M b & W_k^* M W_k \end{pmatrix},\] and the first row in the inverse of this matrix is [31]: \[e_1^\top (B^* M B )^{-1} = (b^* M \widetilde{r}_k)^{-1} \begin{pmatrix}1 & -y_0^* \end{pmatrix}, \text{ where } e_1 = (1,0, \dots, 0)^\top \in \mathbb{C}^{k+1}.\] Multiplying on the right by \(B^*\) gives \(e_1^\top (B^* M B )^{-1} B^* = (b^* M \widetilde{r}_k)^{-1} \underbrace{(b^* -y_0^*W_k^* )}_{=\widetilde{r}_k^*} = \frac{\widetilde{r}_k^*}{ \|\widetilde{r}_k\|_M^2 }\), where the last equality is because \(b^* M \widetilde{r}_k = \|\widetilde{r}_k\|_M^2\) by \(\widetilde{r}_k^* M W_k = 0\). Taking the transpose, we get \[\frac{\widetilde{r}_k}{ \|\widetilde{r}_k\|_M^2 } = B (B^* M B )^{-1} e_1.\] Next, we take the \(M\)-norm and the \(I\)-norm of this estimate in order to get a formula for the \(k\)-th residual norm: \[\label{eq:ipsen} \|\widetilde{r}_k\|_M = \| B (B^* M B )^{-1} e_1\|_M^{-1} = \|e_1\|_{(B^* M B )^{-1}}^{-1},\tag{8}\] as well as for the ratio between the \(I\)- and \(M\)-norms of the \(k\)-th residual \[\frac{ \|\widetilde{r}_k\|_I}{ \|\widetilde{r}_k\|_M} = \frac{\| B (B^* M B )^{-1} e_1\|_I}{\| B (B^* M B )^{-1} e_1\|_M}.\]

Of course, the same results adapt to the residuals \(r_k\) of \(I\)-GMRES: \[\|r_k\|_I = \| B (B^* B )^{-1} e_1\|_I^{-1}=\|e_1\|_{(B^* B )^{-1}}^{-1} , \text{ and } \frac{\|r_k\|_M}{ \| r_k\|_I} = \frac{\| B (B^* B )^{-1} e_1\|_M }{\| B (B^* B )^{-1} e_1\|_I}.\] Finally, comparisons between the residual norms of unweighted and weighted GMRES can be drawn, e.g., \[\frac{\|r_k\|_I}{\|\widetilde{r}_k\|_M} = \frac{\|e_1\|_{(B^*MB )^{-1}}}{\|e_1\|_{(B^*B )^{-1}}}= \frac{\| B (B^* M B )^{-1} e_1\|_M }{\| B (B^*B )^{-1} e_1\|_I },\] where each residual is in its natural norm, \[\frac{\|\widetilde{r}_k\|_I }{\|r_k\|_I} = \frac{\| B (B^* M B )^{-1} e_1\|_I \| B (B^* B )^{-1} e_1\|_I }{\| B (B^* M B )^{-1} e_1\|_M^{2} },\] where both residuals are in the \(I\)-norm, and \[\label{eq:Ipsenfinal} \textcolor{black}{\frac{ \|\widetilde{r}_k\|_N}{ \| r_k\|_N} = \frac{\| B (B^* M B )^{-1} e_1\|_N}{ \| B (B^* B )^{-1} e_1\|_N }\frac{\| B (B^*B )^{-1} e_1\|_I^2}{\| B (B^* M B )^{-1} e_1\|_M^2}},\tag{9}\] where both residuals are measured in a third norm induced by some hpd matrix \(N\). A potential norm of interest could be the Euclidean norm of the error (\(\|x - x_k\|_I\)) which corresponds to the choice \(N = (A A^*)^{-1}\).

We do not pursue this analysis here, but we do wish to mention two contributions of [32] which could also be extended to weighted GMRES: the first is a discussion on the choice of basis \(W_k\), the second is the analysis of the effect on the bounds of adding a vector to \(W_k\) when performing iteration \(k\).

2.2 Prescribed convergence curves↩︎

We now turn back to the convergence curve formalism. We start by proposing the construction of an inner product for which weighted GMRES achieves some desired convergence curve.

In the proof above, if \(\widetilde{g}_i\) and \(g_i\) have no zeroes, i.e.,if \(M\)-GMRES and \(I\)-GMRES never stagnate (or if \(\widetilde{g}_i = 0 \Leftrightarrow g_i = 0\), i.e. if \(M\)-GMRES and \(I\)-GMRES stagnate at the same iterations) then the proposed \(T\) is a diagonal matrix and \(\widetilde{W}\) is simply a scaling of \(W\).

In the following theorem, we characterize the form of all weight matrices \(M\) for which \(M\)-GMRES realizes a prescribed convergence curve.

In the preceding results, the system \((A,b)\) was fixed, and we explored the weight matrices \(M\) that enforce a prescribed convergence curve for \(M\)-GMRES\((A,b)\). We now fix the weight matrix \(M\), and investigate the existence of a system \((A,b)\) such that both the convergence curves of \(I\)-GMRES\((A,b)\) and \(M\)-GMRES\((A,b)\) are prescribed.

Remark that, once more, there is no condition at all on the spectrum of \(A\). In 2.3, the conditions on \(T\) in the second item of the theorem are analyzed and discussed.

By an interlacing theorem for singular values [31], \[[\sigma_{\min}( T_{k+1:m}), \sigma_{\max}( T_{k+1:m})] \subset [\sigma_{\min}( T), \sigma_{\max}( T)].\] Together with 5 and ?? , this provides a new proof for 5 .

2.3 Analysis of the necessary and sufficient condition in 4↩︎

It appears to us that 4 is crucial in predicting whether the convergence of GMRES\((A,b)\) can be significantly modified by changing the inner product. The necessary and sufficient condition in item [it:two-cc-2] of 4 is unfortunately not very natural. Assuming for simplicity that there is no breakdown, there are \(n(n+1)/2\) coefficients in \(T\). The condition \(g = T \widetilde{g}\) produces one linear constraint within each row of \(T\) which leaves \(n(n-1)/2\) degrees of freedom to get the correct singular values.

For a \(2 \times 2\) matrix, we can examine the compatibility between ensuring \(g = T \widetilde{g}\) and setting the singular values to \(\sigma_1\) and \(\sigma_2\). Let \(T = \begin{pmatrix} a & b \\ 0 & d\end{pmatrix}\), \(g=(g_1,g_2)\), \(\widetilde{g} = (\widetilde{g}_1,\widetilde{g}_2)\), with \(g_2,\widetilde{g}_2 \neq 0\). If \(g = T \widetilde{g}\) then \[\label{eq:abd} \begin{equation} d = \frac{g_2}{\widetilde{g}_2} \text{ and } b = \frac{g_1 - a \widetilde{g}_1 }{\widetilde{g}_2}, \end{equation} so only a is still free. However, the product of the singular values equals \det(T) so, \begin{equation} \sigma_1 \sigma_2 = ad = \frac{ a g_2}{\widetilde{g}_2} \, \Leftrightarrow a = \frac{\sigma_1 \sigma_2 \widetilde{g}_2}{g_2}, \end{equation}\tag{16}\] and \(T\) has been entirely set. In order for \(T\) to satisfy the conditions in item [it:two-cc-2] of 4, it remains to ensure one final condition which can take the form of a condition on \(\sigma_1^2 + \sigma_2^2\) \[\label{eq:condition95singular95values} \sigma_1^2 + \sigma_2^2 = \tr(T^* T) = a^2 + b^2 + d^2 = \left(\frac{\sigma_1 \sigma_2 \widetilde{g}_2}{g_2}\right)^2 + \left( \frac{g_1 g_2 - {\sigma_1 \sigma_2 \widetilde{g}_2} \widetilde{g}_1}{g_2 \widetilde{g}_2} \right)^2 + \left( \frac{g_2}{\widetilde{g}_2} \right)^2.\tag{17}\] Unless \(\sigma_1\), \(\sigma_2\), \(g\) and \(\widetilde{g}\) satisfy the above, there is no system \((A,b)\) such that \(I\)-GMRES realizes \(g\) and \(M\)-GMRES realizes \(\widetilde{g}\).

For \(n > 2\), the situation is not as clear, and we list below some requirements.

3 Preconditioned GMRES↩︎

While weighted GMRES may sometimes be considered as a theoretical tool, rather than a practical method to solve real-world problems, preconditioned GMRES is widely employed to enhance the convergence of the standard \(I\)-GMRES method. Yet, both are linked, and preconditioned GMRES can be interpreted as weighted GMRES applied to a modified system. In this section, we explore what our findings on weighted GMRES imply on preconditioned GMRES.

A preconditioner can be applied on the left or on the right. If both are used, we speak of split preconditioning. We consider this general case directly by denoting a pair of left and right preconditioners as \((H_L,H_R)\). One of them can be set to \(I\) to fall back on one-sided preconditioning. \(I\)-GMRES preconditioned on the left by \(H_L\) and on the right by \(H_R\) is defined as \(I\)-GMRES applied to the linear system \[H_L A H_R u = H_Lb, \qquad x = H_Ru.\] At the \(i\)-th iteration, \(I\)-GMRES produces the iterate \(u_i\) (from which the approximate solution \(x_i := H_Ru_i\) can be deduced) and the residual \(\widetilde{r}_i := b - A H_R u_i\). Denoting by \(H := H_R H_L\) the combined preconditioner, \(\widetilde{r}_i\) is characterized by \[\|H_L \widetilde{r}_i\|_I = \min_{u\in \mathcal{K}_i(H_L A H_R, H_L b)} \|H_L b- H_L A H_R u\|_I = \min_{u\in H_L\mathcal{K}_i(AH, b)} \|b-AH_Ru\|_{H_L^* H_L} = \min_{x\in H\mathcal{K}_i(AH, b)} \|b-Ax\|_{H_L^* H_L}.\] Finally, introducing the variable \(v := H^{-1}x\) and the matrix \(\widehat{A} := AH\), the characterization rewrites \[\label{eq:min95split} \|H_L \widetilde{r}_i\|_I = \min_{v\in \mathcal{K}_i(AH, b)} \|b-AHv\|_{H_L^* H_L} = \min_{v\in \mathcal{K}_i(\widehat{A}, b)} \|b-\widehat{A}v\|_{H_L^* H_L}.\tag{18}\] This formulation as well as 1 show that the \(i\)-th residual \(\widetilde{r}_i\) of \(I\)-GMRES\((A,b)\) split-preconditioned by \((H_L,H_R)\) is equal to the \(i\)-th residual of non-preconditioned \((H_L^* H_L)\)-GMRES\((\widehat{A},b)\). We say that \(I\)-GMRES\((A,b)\) split-preconditioned by \((H_L,H_R)\) is equivalent to non-preconditioned \((H_L^* H_L)\)-GMRES\((\widehat{A},b)\). Specializing formulation 18 for special choices of \((H_L,H_R)\) allows us to derive the following equivalent methods:

1. If \(M\) is an hpd matrix that admits the factorization \(M = P^* P\), then \(M\)-GMRES\((A,b)\) is equivalent to \(I\)-GMRES\((A,b)\) split preconditioned by \((P, P^{-1})\).

2. \(I\)-GMRES(\(A,b\)) right preconditioned by \(H\) is equivalent to unpreconditioned \(I\)-GMRES(\(\widehat{A},b\)).

3. \(I\)-GMRES(\(A,b\)) left preconditioned by \(H\) is equivalent to unpreconditioned \((H^*H)\)-GMRES(\(\widehat{A},b\)).

We can also make two fundamental remarks:

• The choice of preconditioning on the left or on the right, or of split preconditioning does not modify the Krylov space in which the approximate solution \(x_i\) is optimized. The minimization space depends only on the combined preconditioner \(H = H_R H_L\).

• The norm in which the residual \(r_i = b - A x_i\) is minimized depends only on the left preconditioner through \(H_L^* H_L\). The fact that preconditioning on the right (i.e., setting \(H_L = I\)) does not modify the minimized norm is a rather well known fact.

3.1 Left, right and split preconditioned GMRES↩︎

Based on the equivalences above, the results from 2.1 can be rewritten for left, right and split preconditioned GMRES. We give below just two such examples that correspond to 6 and 9 (see also [7]).
Let the residuals of \(I\)-GMRES\((A,b)\) right preconditioned by \(H\) be denoted by \(r_k\) and the residuals of \(I\)-GMRES\((A,b)\) left preconditioned by \(H\) be denoted by \(\widetilde{r}_k\) (which means that the residual norm \(\|H \widetilde{r}_k\|_I\) is actually produced). The left/right preconditioned version of 5 is \[\label{eq:prec-GMRES-easy2} \| r_k \|_I \leq \| \widetilde{r}_k\|_I \leq \kappa(H) \| r_k \|_I \text{ and } \|H\widetilde{r}_k\|_I \leq \|H r_k\|_I \leq \kappa(H) \|H\widetilde{r}_k\|_I,\tag{19}\] where \(\kappa(H) := \|H\|_I\|H^{-1}\|_I = \sqrt{\kappa(H^* H)}\) is the condition number of \(H\).
The more involved bound is \[\label{eq:precIpsenfinal} \frac{ \|\widetilde{r}_k\|_N}{ \| r_k\|_N} = \frac{\| B (B^* H^* H B )^{-1} e_1\|_N}{ \| B (B^* B )^{-1} e_1\|_N }\frac{\| B (B^*B )^{-1} e_1\|_I^2}{\|H B (B^* H^* H B )^{-1} e_1\|_I^2},\tag{20}\] where \(N\) is any hpd matrix, \(B = (b \,\,\, W_k)\) is the concatenation of the right-hand-side with any matrix \(W_k \in \mathbb{C}^{n\times k}\) whose columns form a basis of \(AH \mathcal{K}_k(AH,b)\), and \(e_1 = (1,0, \dots, 0)^\top \in \mathbb{C}^{k+1}\).

3.2 Prescribed convergence curves↩︎

We now turn to extending the results of 2.2 to preconditioned GMRES. Following 18 and the subsequent remarks, we naturally extend the concept of realizing a convergence curve to preconditioned GMRES.

As a direct consequence of item [it:spliteq] above, 2 implies that

In the following result, we show that it is possible to simultaneously prescribe the convergence curves for the GMRES algorithm preconditioned on the left and on the right.

The following result translates 3 into the preconditioning formalism.

The following result is a corollary of 7: for any given system and preconditioner, regardless of the convergence curves achieved by left and right preconditioned GMRES, there exists another preconditioned system with the same spectrum that exhibits the opposite behavior. This implies that, when considering all possible pairs of systems and preconditioners, neither left nor right preconditioning is inherently superior to the other. We give a constructive proof using 8.

We end with the preconditioned GMRES version of 4.

The eigenvalues \(\lambda_i\) do not play a role in the second assertion, meaning that they can be independently prescribed.

The necessary and sufficient condition in 9 has been analyzed in 2.3.

From these results, we can make the following observation: there exist preconditioned systems where the choice of left or right preconditioning leads to significantly different GMRES convergence behaviours. For instance, left preconditioning may result in fast convergence, while right preconditioning may lead to slow convergence, even if in both cases, the eigenvalues of the preconditioned system are perfectly clustered. This observation reinforces what is already known: GMRES convergence is not solely determined by the eigenvalues. It also highlights that in certain cases, the choice of preconditioning on the left or on the right may not be trivial and lead to significant differences.

4 Illustrations↩︎

The purpose of the following experiments is to gain insight on the links between the convergence curves of \(I\)- and \(M\)-GMRES and the weight matrix \(M\). The experiments are run in MATLAB, and the scripts are openly available⁵. Previous numerical comparisons can be found in [18]–[20] for restarted GMRES, and [16], [22] for particular choices of the weight that arise from analyzing GMRES convergence.

A word of warning about the following results is that we only plot normalized residuals, so that all convergence curves start from the same initial point. This is the same as scaling \(b\) so that \(\|b\|_I = 1\) and scaling \(M\) so that \(\|b\|_M = 1\) also. For this reason, only the relative distribution of eigenvalues of \(M\) is significant. Moreover, we consider for simplicity that all prescribed convergence curves are of length \(n\) (i.e. no early breakdown), so that all matrices \(T\) of the form 3 are triangular.

4.1 Fixed spectrum for \(M\) and convergence curve for \(I\)-GMRES, variable \(T\)↩︎

We place ourselves in the formalism of 4. Our focus is on examining how the convergence of \(M\)-GMRES is affected by prescribing the spectrum of \(M\). Recall that for a given \(I\)-GMRES residual decrease vector \(g\in\mathbb{R}_+^n\) and a given spectrum \(\mu\in\mathbb{R}_+^n\) for \(M\), the possible convergence curves for \(M\)-GMRES correspond to the set of all \(\widetilde{g} := T^{-1}g\), such that the singular values of \(T\) are the \((1/\sqrt{\mu_i})_i\), which means that the singular values of \(T^{-1}\) are the \((\sqrt{\mu_i})_i\).

The experimental setup of this section is then the following: given a prescribed convergence curve for \(I\)-GMRES and a prescribed spectrum \(\mu\) for \(M\), we

1. construct the residual decrease vector \(g\) by 2,

2. randomly generate a matrix \(T^{-1}\) with singular values \((\sqrt{\mu_i})_i\) (see below),

3. compute \(\widetilde{g} := T^{-1}g\),

4. recover the residuals norms realized by \(M\)-GMRES through formula ?? .

In practice, to randomly generate a triangular matrix \(T^{-1}\) with prescribed singular values, we apply the following procedure: (i) generate a random orthogonal matrix \(V\) by performing the QR factorization of a general matrix with randomly generated coefficients; (ii) define \(T^{-1}\) as the triangular matrix in the QR factorization of \(\Sigma V\), where \(\Sigma\) denotes the diagonal matrix holding the prescribed singular values.

Browsing through all possible \(T^{-1}\) matrices spans all possible convergence curves for \(M\)-GMRES. However, in practice, randomizing the coefficients of \(T^{-1}\) by this procedure does not produce the complete variety of possible convergence behaviors. Indeed, first, the initial random matrix is drawn from a uniform distribution, which inherently restricts the diversity of resulting matrices (and thus, the range of orthogonal matrices \(V\) that can be obtained). Second, the QR factorization of \(\Sigma V\) produces a fully populated triangular matrix, excluding structurally sparse forms (such as diagonal matrices). Despite these limitations, we examine the convergence curves generated by this method as representative examples within the broader landscape of \(M\)-GMRES behavior.

In the following experiments, we consider real matrices and we set \(n=20\).

4.1.0.1 Experiment 1 (one eigenvalue jump)

The spectrum of \(M\) is chosen to contain two distinct eigenvalues, 1 and \(10^{12}\), with respective multiplicities \((n-k)\) and \(k\), with \(k=8\). 1 displays convergence curves of \(M\)-GMRES obtained from a sample of 5 random matrices \(T^{-1}\). Each subfigure corresponds to a prescribed convergence curve for \(I\)-GMRES: (a) complete stagnation until breakdown; (b) linear decay of the residual in logarithmic scale; (c) general, irregular decrease of the residual.

We observe that all samples initially follow the convergence pattern of \(I\)-GMRES. Subsequently, they exhibit a sudden and significant jump before resuming the residual decrease characteristic of \(I\)-GMRES. According to formula 7 , the magnitude of this jump is bounded by \(\sqrt{\kappa(M)}\), here \(10^6\). The plots indicate that this upper bound is closely approached. Notably, the jump occurs at iteration 8, which aligns with the order of multiplicity \(k\) of the large eigenvalue. Experiments with varying values of \(k\) confirm that the jump consistently occurs at iteration \(k\). This can be understood by recalling that \(T^{-1}\) is the triangular matrix in the QR factorization of \(\Sigma V\), a matrix that has \(8\) rows that are of much larger magnitude than the others.

Additionally, when the spectrum of \(M\) consists not of two distinct eigenvalues but of two clusters of eigenvalues randomly distributed around the same two values, the results remain qualitatively unchanged. Note also that permutations of the vector \(\mu\) does not change the results either.

4.1.0.2 Experiment 2 (two eigenvalue jumps)

The spectrum of \(M\) is chosen to contain three distinct eigenvalues: 1, \(10^{10}\) and \(10^{20}\), with respective multiplicities \((n-k_1-k_2)\), \(k_1\) and \(k_2\), with \(k_1:=7, k_2:=4\). 2 illustrates the results under the same experimental conditions as Experiment 1. The plots are similar, except that two jumps are observed due to the two jumps in the eigenvalues. In this scenario, the combined magnitude of both jumps is theoretically constrained by \(\sqrt{\kappa(M)} = 10^{10}\), which is also closely approached in this case. Concerning the location of the jumps: the first jump occurs at iteration \(k_2=4\), which corresponds to the order of multiplicity of the largest eigenvalue; the second jump occurs \(k_1\) iterations later, which corresponds to the order of multiplicity of the second-largest eigenvalue, here \(11\).

4.1.0.3 Experiment 3 (uniform distribution)

The spectrum of \(M\) is uniformly distributed on a logarithmic scale between 1 and \(10^{12}\). 3 illustrates the results under the same experimental conditions as the previous experiments. Based on our earlier interpretations, these curves adhere to the convergence pattern of \(I\)-GMRES, supplemented by small decreases at each iteration. Given that the eigenvalues are equally spaced on a logarithmic scale, the resulting jumps are of similar magnitude. Furthermore, since all eigenvalues are distinct, these small jumps manifest at each iteration.

4.1.0.4 Experiment 4 (diagonal \(T^{-1}\))

While the previous experiments explored fully populated triangular matrices \(T^{-1}\), we now consider diagonal matrices. The experimental setup is the following: the convergence curve of \(I\)-GMRES is set to a linear decay in logarithmic scale, and \(T^{-1}\) is the diagonal matrix \(\operatorname{diag}(\sqrt{\mu})\), i.e.with coefficients \((\sqrt{\mu_i})_i\). Several settings for \(\mu\) are tried out, all based on two eigenvalues, 1 and \(10^{12}\), in various orders: \[\begin{align} \underline{\mu}^k &:= [\underbrace{1, \dots, 1}_{k}, \underbrace{10^{12}, \dots, 10^{12}}_{n/2}, \underbrace{1, \dots, 1}_{n/2-k}]^* &\forall k=0,\dots,n/2, \\ \overline{\mu}^k &:= [\underbrace{10^{12}, \dots, 10^{12}}_{k}, \underbrace{1, \dots, 1}_{n/2}, \underbrace{10^{12}, \dots, 10^{12}}_{n/2-k}]^* &\forall k=0,\dots,n/2. \end{align}\] The results are displayed in 4. We observe that \(M\)-GMRES with \(\mu := \underline{\mu}^k\) stagnates during \(k\) iterations, follows the residual decrease of \(I\)-GMRES during \(n/2\) iterations, then jumps and follows \(I\)-GMRES for the remaining iterations. On the other hand, with \(\mu := \overline{\mu}^k\): we notice that \(\overline{\mu}^0 = \underline{\mu}^{n/2}\) and \(\overline{\mu}^{n/2} = \underline{\mu}^0\) (in red); for all the other values of \(k\), the convergence of \(M\)-GMRES follows that of \(I\)-GMRES during \((k-1)\) iterations, then jumps at the \(k\)-th iteration, and finally stagnates.

4.2 Can we break the observed behaviour?↩︎

In the first three experiments, all generated samples exhibited the same convergence pattern. In the following experiments, we demonstrate that this behavior can, in fact, be disrupted by setting up an experiment for which we can compute the residuals of weighted and unweighted GMRES as follows.

4.2.0.1 Experiment 5

1. Set \(\mu \in(\mathbb{R}_+\setminus\{0\})^n\). Let \(M_0 := Q \operatorname{diag}(\mu) Q^*\), where \(\operatorname{diag}(\mu)\) is the diagonal matrix corresponding to \(\mu\), and \(Q\) is a random unitary matrix. This way, \(M_0\) is an hpd matrix with eigenvalues held in \(\mu\).

2. Let \(b := \frac{1}{\sqrt{n}}Q [1, \dots, 1]^\top\) be the right-hand side.

3. Normalize \(M_0\) as \(M := \beta M_0\), where \(\beta := \|b\|_{M_0}^{-2}\) (so as to enforce \(\|b\|_M = 1\)). This is our weight matrix.

4. We consider a matrix \(A\) for which \(W := Q\) is a nested orthonormal basis of \(A\mathcal{K}_n(A,b)\) and compare \(I\)-GMRES\((A,b)\) to \(M\)-GMRES\((A,b)\). The residuals do not depend on the particular choice of \(A\) (by 2 ). There are two ways of computing the resulting residual norms:

   • Either, the matrix \(A\) can be constructed following the procedure in the proof of [11] (a result that extends [3] recalled in 1). Then \(I\)-GMRES\((A,b)\) and \(M\)-GMRES\((A,b)\) are run and the corresponding residual norms collected.

   • Or, the residuals can be computed directly. By 2 , denoting by \(w_i\) the \(i\)-th column of \(W\), \(\sqrt{\|r_{i-1}\|_I^2 - \|r_i\|_I^2} = |\langle b,w_i \rangle_I | = \frac{1}{\sqrt{n}}\) and \(\sqrt{\|r_{i-1}\|_M^2 - \|r_i\|_M^2} = \abs{\langle b, \sqrt{\frac{{\mu}_i}{\beta}}w_i \rangle_M} = \sqrt{\frac{\mu_i}{n \beta}}\) because the scaled vectors \((\sqrt{\frac{{\mu}_i}{\beta}} w_i)_i\) form an \(M\)-orthonormal nested basis of \(A\mathcal{K}_n(A,b)\).

The convergence curves are shown in 5. With \(n = 60, \epsilon = 10^{-2}\) and \(p=n/2\), three cases are considered for \(\mu\): \[\mu^1 := [\underbrace{1, \dots, 1}_{p}, \underbrace{\epsilon, \dots, \epsilon}_{n-p}]^\top, \text{ for which } \|\widetilde{r}_i\|_M = \begin{cases} \sqrt{1 - \frac{\beta}{n}i} &\text{if } i \leq p, \\ \sqrt{\|\widetilde{r}_{p}\|_M^2 - \frac{\beta \epsilon}{n}(i-p)} & \text{if } i > p, \end{cases}\] \[\mu^2 := [\underbrace{\epsilon, \dots, \epsilon}_{p}, \underbrace{1, \dots, 1}_{n-p}]^\top, \text{ for which } \|\widetilde{r}_i\|_M = \begin{cases} \sqrt{1 - \frac{\beta\epsilon}{n}i} \quad \approx 1 &\text{if } i \leq p, \\ \sqrt{\|\widetilde{r}_{p}\|_M^2 - \frac{\beta}{n}(i-p)} & \text{if } i > p, \end{cases}\] and \(\mu^3\), where the eigenvalues have been shuffled.

4.3 Left and right preconditioning↩︎

Note that the results from the previous sections can also be interpreted as instances of left and right preconditioning strategies. In this section, we consider the matrix HB/mcfe⁶ from the University of Florida Sparse matrix collection [33]. It is a real, non-symmetric, sparse matrix of size \(765\times 765\) with a condition number (in \(\|\cdot\|_I\)) of approximately \(10^{14}\). First, we solve the linear system using unpreconditioned GMRES for two different right-hand sides: \(b=(1, \dots, 1)^\top\) and a random \(b\). In both cases, the relative residual remains greater than \(10^{-8}\) after \(n-1=764\) iterations. This outcome confirms the challenge posed by this problem for GMRES. Moving forward, we will use the random \(b\). Now, we consider two preconditioners: (i) ILU: the preconditioner is \(H := U^{-1}L^{-1}\), where \(L\) and \(U\) are the factors in the incomplete LU factorization of \(A\), (ii) Symmetric part: \(H\) is the inverse of \((A+A^*)/2\). The corresponding convergence curves are displayed in 6. Using ILU as a preconditioner leads to fast convergence in both cases (less than 12 iterations) with an advantage to left preconditioning. On the other hand, using the symmetric part as a preconditioner exhibits a significant difference in convergence speed. For this case, some metrics given in 1 do not allow us to explain this behaviour. Note that, from these results, one might be tempted to think that left preconditioning generally offers a faster convergence. However, 3 shows this is not the case. Finally, in 7, we present plots of the preconditioned and unpreconditioned relative residual norms, along with the error. We use solid lines to display the residual norms actually minimized by left and right preconditioned GMRES: the preconditioned residual \(\|Hr\|_I/\|b\|_I\) for left preconditioning and the unpreconditioned residual \(\|r\|_I/\|b\|_I\) for right preconditioning. These are the residual to which the stopping criterion respectively applies. The errors produced by these algorithms are plotted in dashed line. These errors are computed from the GMRES approximations at each iteration, compared against the algebraic solution obtained through an LU factorization. Additionally, the residual not minimized by the algorithm is plotted for reference. In particular, while left preconditioning shows rapid convergence in terms of the preconditioned residual and error, the unpreconditioned residual (i.e.in Euclidean norm) remains high. This is a typical case where monitoring only the left preconditioned residual could lead to early termination if the user is not aware that the Euclidean norm of the residual can still be high.

5 Conclusion↩︎

In this work, we extended the theory of prescribed convergence curves for GMRES to the setting of weighted GMRES and preconditioned GMRES. Building on the foundational result of Greenbaum, Pták, and Strakoš, we demonstrated that for any linear system and any prescribed convergence behavior, one can construct a weight matrix or a preconditioning strategy that forces GMRES to exhibit this behavior. Our theoretical contributions include a full characterization of weight matrices that yield a desired convergence curve and the necessary and sufficient conditions for realizing two distinct convergence curves simultaneously (one for \(I\)-GMRES and the other for \(M\)-GMRES). We showed that these results naturally translate to the preconditioned setting, both with split and one-sided preconditioners, highlighting in particular that left and right preconditioning can yield markedly different convergence behaviors, regardless of the spectrum of the preconditioned system.

Acknowledgments↩︎

We thank Gérard Meurant for enlightening discussions about left and right preconditioning and for suggesting the HB/mcfe matrix to us.

References↩︎

---

1. CNRS, CMAP, École polytechnique, Institut Polytechnique de Paris↩︎

2. This work was supported in part by the ANR project DARK (research grant ANR-24-CE46-1633).↩︎

3. https://github.com/hpc-maths/2025_prescribed_gmres↩︎

4. https://github.com/hpc-maths/krylov4r↩︎

5. https://github.com/hpc-maths/2025_prescribed_gmres↩︎

6. https://www.cise.ufl.edu/research/sparse/matrices/HB/mcfe.html↩︎