betaFeedback

WorksMathematics

On-the-Fly Reduced Bases Through the Lens of Augmented Krylov Methods

Abstract

On-the-fly reduced order models (ROMs) are widely used in applications where multiple queries of large-scale models are required in an iterative method, like PDE-constrained optimization or fluid-structure interaction. When compared to classical offline–online ROMs, they have the advantage of being agnostic to any precomputed training data, mesh or geometry, which makes them more general linear/nonlinear solver accelerators. The main goal of this work is to study the effect of using a reduced basis constructed on-the-fly to accelerate a restarted Krylov algorithm, and to formally bridge this category of data-driven methods with classical augmented Krylov methods. The guiding principles of on-the-fly reduced basis will be translated into the framework of Krylov subspace methods, for a Petrov-Galerkin projection method. Previous corrections generated by the algorithm are stored in a snapshot matrix, and a singular value decomposition (SVD) is used to determine a reduced subspace containing the most significant directions. It will be shown that this approach can be embedded in the framework of Krylov methods with augmented or deflated restart, but with a different, data-driven recycling strategy. An analytical study will be presented to determine the consequences of augmentation by ROM-based vectors. Numerical experiments on a convection-diffusion problem with various degrees of convection will show that the proposed methodology yields results comparable to classical iterative linear solvers in some regimes, especially for nearly symmetric or skew-symmetric operators. At equal sizes of the augmentation basis, the convergence was sometimes faster with the proposed framework than with deflation methods.

Introduction

A popular class of algorithms to solve a linear system Ax=bAx=b is Krylov subspace methods, or more generally, projection methods. They are very efficient compared to direct methods, because their complexity is usually upper bounded by the number of matrix-vector products (matvecs) they require. The cost per matvec is at most O(n2)O(n^2) for dense matrices, or O(nnz⁡)O(\operatorname{nnz}) for sparse matrices, where nnz is the number of nonzero entries. This makes them especially suitable for very large and sparse systems arising from the numerical solution of partial differential equations (PDEs). The other driving cost of those methods is the orthogonalization step. For full projection methods, the most recent residual has to be orthogonalized against all previously computed residuals. When the algorithm converges in a large number of iterations, which can happen when the matrix is poorly conditioned, this cost becomes a non-negligible overhead per iteration. To alleviate this phenomenon, various strategies have been implemented since the popularization of these algorithms in the 1970s and 1980s, for instance with the arrival of MINRES [28] and GMRES [33]. One possible approach is to keep a reduced window of previous vectors to orthogonalize against, like the so-called Incomplete Orthogonalization Method (IOM) does [5, 32]. The orthogonalization cost is then capped by the fixed size of the window. Another strategy is restarting, which consists of prematurely stopping the algorithm past a certain number of iterations, and then restarting it from the current partial solution, while completely resetting the history of vectors to orthogonalize against. While this reduces the work dedicated to orthogonalization per iteration, the convergence is drastically slowed down since components that were constructed in previous cycles are forgotten and must be recomputed. The idea of recycling and augmenting came about to counter this phenomenon. By keeping only a few vectors that summarize well the work done in a previous cycle and augmenting the search space with those, the essential information is carried forward and the convergence becomes closer to that of the full, untruncated projection method. There are multiple ways to select such information, which give rise to multiple restarted Krylov methods with augmentation or recycling. We refer to the work of Soodhalter, de Sturler and Kilmer [36] for a comprehensive review of subspace recycling. Eiermann, Ernst and Schneider [15] classify augmentation methods into two fundamental strategies. One is based on a geometrical argument of measuring largest principal angles between two subspaces to preserve the most important orthogonality constraints, which amounts to the GCROT method [10]. They determine how to optimally truncate the search space of the previous cycle according to this metric. The other strategy is based on the idea of deflation, which means that information about invariant subspaces is carried over from cycle to cycle, because it usually slows down the convergence. This information is usually obtained by approximating eigenvectors by Ritz vectors, and augmenting the search space basis with those. This approach led to many algorithms like GMRES-DR [26], GCRO-DR [29] and Deflated-CG [34]. Deflation techniques are also used to design preconditioners [17, 27, 16] for full projection methods.

It is known that eigenvectors (or approximate eigenvectors) are a good basis for a deflation subspace because they reduce the effective condition number of the matrix by eliminating specific eigenvalues from the problem. However, it is fair to consider augmenting the basis with other vectors that are not necessarily approximations of eigenvectors, but may carry important information about the convergence. For instance, Baker, Jessup and Manteuffel [2] proposed the LGMRES method, which stores approximate errors between the cycles and augments the search space of GMRES with them. More recently, data-driven methods have been introduced. They usually reuse information obtained from a sequence of previously solved, similar linear systems in order to create augmentation spaces, especially with the proper orthogonal decomposition (POD). Kerfriden, Gosselet, Adhikari and Bordas [22] used a POD-augmented preconditioned conjugate gradient (PCG) method in a nonlinear Newton-Krylov solver. Carlberg, Forstall and Tuminaro [6] proposed a goal-oriented POD, for instance by introducing weights, to improve the convergence of PCG when using a POD-augmented search space. Diaz Cortes, Vuik and Jansen [11] proposed the use of POD deflation vectors in the case when the right-hand sides of the linear systems are subject to low-dimensional perturbations. Their follow-up work [12] compares an on-the-fly in time approach to build the POD deflation vectors with the classical offline-online paradigm for POD [30]. Li, Zikatanov and Zuo [24] proposed the Reduced Krylov Basis Method (RKBM) framework, in which a reduced Krylov basis is constructed in the offline POD training phase, and then used to find solutions quicker during the online phase. More recently, machine learning approaches, like DeepONet, have been used as well to construct the deflation space [23].

This article proposes an approach using information collected on-the-fly in a restarted Krylov solver, to build a reduced basis following the principles of the POD framework: constructing a snapshot matrix of corrections in the Krylov subspace, and using the singular value decomposition (SVD) to retain a low-dimensional, dominant subspace spanned by those corrections. The search space for corrections in the following iterations is then initially limited to that reduced space. We can show that this method acts formally as a restarted Krylov method with a POD-augmented subspace that changes at every cycle. However, it differs from other methods of this type present in the literature because the information necessary for the construction of the reduced basis is not obtained from the solution of a sequence of different linear systems, but purely from the convergence history of the current solver. In fact, this makes this method more similar to classical augmented or deflation-restarted Krylov methods, just like LGMRES, GCROT or GMRES-DR, the difference lying in the way the augmentation space is selected. The proposed approach uses a data-driven selection criterion, like POD, instead of the usual recency, spectral or geometric selection criteria.

§ 2 will recall useful concepts from the theory of Krylov subspace methods, introduce augmented Krylov methods, and present reduced bases in the on-the-fly paradigm. In § 3, reduced-basisaugmented minimal residual methods will be presented. The error between those augmented, restarted variants and untruncated methods will be derived explicitly. Moreover, we are able to characterize the proposed method as an interpolation between two classical methods, LGMRES(mm, 1) and ss-ORTHOMIN(1) [8]. § 4 will provide numerical illustration of the capabilities of the proposed algorithms. The goal of this section is to demonstrate that, while they neither systematically nor significantly outperform existing augmented Krylov methods, they are competitive when compared to other state-of-the-art linear solvers which are not data-driven.

Preliminaries

Projection Methods for Linear Systems

Let the linear system Ax=bAx=b, with A∈Rn×nA \in\mathbb{R}^{n \times n} nonsingular and x,b∈Rnx,b \in\mathbb{R}^{n} have the solution x=x∗x=x^*. Starting from an initial guess x0x^0, the core idea of projection methods is to look for an approximate solution of the form x∗≈xk∈x0+Wkx^* \approx x^k \in x^0+\mathcal{W}_k, with the additional property rk⊥Vkr^k \perp\mathcal{V}_k, where Wk\mathcal{W}_k, Vk\mathcal{V}_k are kk-dimensional subspaces and rk=b−Axkr^k=b-Ax^k is the residual [32]. The solution is found in an affine search space, under the constraint that its residual must be orthogonal to some linear subspace. Projection methods can be classified according to the choice of the subspaces.

Petrov-Galerkin methods are the most general. Assuming only that WkW_k, VkV_k are orthonormal bases of Wk\mathcal{W}_k and Vk\mathcal{V}_k respectively, the two conditions below must be satisfied:

xk=x0+WkykandVkT(b−Axk)=0⟺VkTAWkyk=VkTr0.(1)x^k=x^0+W_ky^k \quad\text{and} \quad V_k^{\mathsf{T}}(b-Ax^k)=0 \Longleftrightarrow V_k^{\mathsf{T}}AW_ky^k=V_k^{\mathsf{T}}r^0. \tag*{(1)}

In general, for AA invertible, it is not guaranteed that the projected system even has a unique solution. Very generic hypotheses like im⁡(AWk)∩im⁡(Vk)⊥={0}\operatorname{im}(AW_k)\cap\operatorname{im}(V_k)^\perp=\{0\} can be considered, but they are usually not very informative in practical cases. Within Petrov-Galerkin methods, the choice Vk=MWkV_k=MW_k yields most methods used in practice [18].

Setting M=IM=I, or Wk=VkW_k=V_k, yields Galerkin projection methods. The approximate solution satisfies the analog of the projected system (1) with Vk=WkV_k=W_k,

WkTAWkyk=WkTr0.W_k^{\mathsf{T}}AW_ky^k=W_k^{\mathsf{T}}r^0.

This class of methods is especially adapted for the case AA symmetric and positive definite (SPD), since the projected system above will also be nonsingular and SPD. Moreover, the projected system to solve is the stationarity condition for the minimization problem

xk=arg⁡min⁡x∈x0+Wk ∥x−x∗∥A2.x^k=\underset{x\in x^0+\mathcal{W}_k}{\arg\min}\ \lVert x-x^*\rVert_A^2.

the minimization of the AA-norm error. Another common choice is setting M=AM=A, or Vk=AWkV_k=AW_k. The Petrov-Galerkin system (1) becomes

WkTATAWkyk=WkTATr0.W_k^{\mathsf{T}}A^{\mathsf{T}}AW_ky^k=W_k^{\mathsf{T}}A^{\mathsf{T}}r^0.

It is easy to recognize the normal equations, which are equivalent to solving the minimization problem

∥rk∥=min⁡y∈Rk∥r0−AWky∥=min⁡x∈x0+Wk∥b−Ax∥=min⁡x∈x0+Wk∥x−x∗∥ATA.\lVert r^k\rVert=\min_{y\in\mathbb{R}^k}\lVert r^0-AW_ky\rVert=\min_{x\in x^0+\mathcal{W}_k}\lVert b-Ax\rVert=\min_{x\in x^0+\mathcal{W}_k}\lVert x-x^*\rVert_{A^{\mathsf{T}}A}.

This is why those methods are generally referred to as minimal residual projection methods. Notice the equivalence with minimizing the error in the ATAA^{\mathsf{T}}A-norm, which makes this norm (and the AA-norm for Galerkin methods) the natural choice for measuring convergence.

Krylov methods are special cases of both Petrov-Galerkin and Galerkin methods, where in addition of imposing the orthogonality constraint, the affine subspace is restricted to be the Krylov subspace of dimension kk,

Wk=Kk(A,r0)=span⁡{r0,Ar0,A2r0,…,Ak−1r0}.\mathcal{W}_k=\mathcal{K}_k(A,r^0)=\operatorname{span}\{r^0,Ar^0,A^2r^0,\ldots,A^{k-1}r^0\}.

This choice is particularly useful because the inverse of the matrix AA can be expressed as a polynomial in AA, pm(A)=A−1p_m(A)=A^{-1}, of degree at most m≤nm \le n [32]. A basis of the space of polynomials of degree at most mm would then be able to represent exactly the action of A−1A^{-1} by computing only powers of AA (or even, only matvecs). Indeed, the matrix Wm+1W_{m+1}, basis of Wm+1\mathcal{W}_{m+1}, has columns of the form qi(A)r0q_i(A)r^0 with deg⁡(qi)=m\deg(q_i)=m. They form a basis of the space of degree mm polynomials in AA. For some ym+1∈Rm+1y^{m+1} \in\mathbb{R}^{m+1},

Wm+1ym+1=(∑i=1m+1yim+1qi(A))r0.W_{m+1}y^{m+1} = \left(\sum_{i=1}^{m+1} y_i^{m+1}q_i(A)\right)r^0.

By setting ym+1y^{m+1} to be the coefficients of pmp_m in the basis {qi}i=1m+1\{q_i\}_{i=1}^{m+1}, Wm+1ym+1=A−1r0=x∗−x0W_{m+1}y^{m+1}=A^{-1}r^0=x^*-x^0, the exact correction needed to reach the solution from the starting point x0x^0. Krylov methods are built upon this principle, by constructing iteratively an orthonormal basis for Kk(A,r0)\mathcal{K}_k(A,r^0) until convergence is reached. Minimal residual methods will find the coefficients by minimizing the residual over this polynomial space at each iteration, and the Petrov-Galerkin condition ensures that the residual has no component in the AA-image of the current Krylov space, i.e., that the next coefficient will belong to the next power of AA. Numerically, convergence in mm or nn iterations does not need to be reached exactly, as we are interested in an approximate solution; a small residual would suffice to stop the algorithm. Moreover, floating-point arithmetic prevents reaching the exact solution and might propagate errors that destabilize convergence.

Both Petrov-Galerkin and Galerkin methods implement this paradigm. Note that in exact arithmetic, as long as the two spaces chosen are equal, the algorithms will produce identical iterates. However, floating-point arithmetic allows for different implementations of the same theoretical method to give different results, with potentially different properties. For instance, some representatives of Petrov-Galerkin, or more precisely minimal-residual Krylov methods are GMRES, MINRES and GCR. The conjugate gradient (CG) method and the full orthogonalization method (FOM) are representatives of Krylov methods from the Galerkin family. Frequently, these methods differ by optimizing some part of the orthogonalization process to specific matrix types, like using the Lanczos process instead of the Arnoldi process when AA is symmetric. This is the main distinction between FOM and CG [32], meaning they are otherwise equivalent in exact arithmetic. The families and methods named here are not exhaustive, and other choices of spaces can yield useful projection methods, like Wk=Kk(A,r0)\mathcal{W}_k=\mathcal{K}_k(A,r^0) and Vk=Kk(AT,r0)\mathcal{V}_k=\mathcal{K}_k(A^{\mathsf{T}},r^0) for the BiCG method.

Augmented Krylov Methods

The methods are based on a pattern of outer iterations or cycles (index i≤NOi \le N_O) and inner iterations (index k≤NIk \le N_I). A first group of augmented Krylov methods are projection methods where the search space has the form Wk,i=Vi⊕Kk(A,ri)\mathcal{W}_{k,i}=\mathcal{V}_i\oplus\mathcal{K}_k(A,r^i), meaning that it is the direct sum of a Krylov space and some other subspace with suitable properties. One of the main goals of these methods is to accelerate restarted Krylov methods. For instance, in GMRES(NIN_I), which is restarted every NIN_I iterations, the loss of orthogonality with directions obtained in previous cycles slows down its convergence considerably. Augmenting the search space with previous corrections acts as some form of memory mechanism which prevents the algorithm from generating contributions in subspaces that were already considered in the past. This approach has been implemented in LGMRES [2], where a few (usually, fewer than 5) corrections from past cycles are added in Vi\mathcal{V}_i, which effectively reduces the oscillatory behaviour appearing in the convergence of GMRES(NIN_I). In that case, if cycles are seen as independent restarts of the method, LGMRES is composed of a sequence of independent GMRES calls with an augmentation subspace Vi\mathcal{V}_i, which changes only between cycles. Other methods like GMRES-E [25] use this form, but with approximate eigenvectors instead. We will refer to such algorithms as augmented FGMRES methods, because Saad [31] introduced a generic modified Arnoldi algorithm following this form. Algorithm 1 presents this framework, more precisely the ii-th cycle, in which a Krylov subspace KNI(A,ri)\mathcal{K}_{N_I}(A,r^i) is constructed while maintaining orthogonality to mm additional vectors.

Another approach suggests that the operator of the Krylov subspace changes. Subspaces of the form Wk,i=Vi⊕Kk(PiA,ri)\mathcal{W}_{k,i}=\mathcal{V}_i\oplus\mathcal{K}_k(P_iA,r^i) are considered. This means that between each cycle, the augmented basis is updated (e.g., using deflation vectors), but also the projector PiP_i, to improve the convergence of the Krylov method within the cycle by potentially removing problematic eigenvectors. Such methods include GCROT, GCRO-DR and Deflated-CG, the last two using deflation [17] to augment the space and to accelerate convergence.

Algorithm 1 Augmented FGMRES-Like Algorithm (ii-th cycle)

  1. ri=b−Axir^i = b - Ax^i, z0=ri/∥ri∥z^0 = r^i/\|r^i\|, Vi=[v1,i,…,vm,i]V_i = [v^{1,i}, \ldots, v^{m,i}]

  2. [z0,…,zNI+m],Hi←Arnoldi⁡({z0,Az0,A2z0,…,ANIz0,Av1,i,…,Avm,i})[z^0,\ldots,z^{N_I+m}], H_i \leftarrow\operatorname{Arnoldi}(\{z^0,Az^0,A^2z^0,\ldots,A^{N_I}z^0,Av^{1,i},\ldots,Av^{m,i}\})

  3. Wi=[z0,…,zNI−1,v1,i,…,vm,i]W_i = [z^0,\ldots,z^{N_I-1},v^{1,i},\ldots,v^{m,i}]

  4. Zi=[z0,…,zNI+m]Z_i = [z^0,\ldots,z^{N_I+m}], s.t. AWi=ZiHiAW_i = Z_iH_i

  5. ζi=arg min⁡ζ∈RNI+m∥ZiTri−Hiζ∥\zeta^i = \operatorname*{arg\,min}_{\zeta\in\mathbb{R}^{N_I+m}}\|Z_i^\mathsf{T}r^i-H_i\zeta\|

  6. xi+1=xi+Wiζix^{i+1} = x^i + W_i\zeta^i

Deflation has also been used with CG [34], but the augmentation basis has to come from the solution of previous linear systems, since CG need not be restarted in general. Hicken and Zingg [20] proposed a variant of GCROT, GCROT(m,km,k), which simply keeps the kk most recent corrections as the augmentation vectors, like LGMRES would, but also projects the operator, something absent from LGMRES. Algorithm 2 presents the ii-th cycle of a GCRO-like algorithm, which uses mm augmentation vectors. Note that the projected operator PiAP_iA makes it so that all Arnoldi vectors are orthogonal to im⁡(AVi)\operatorname{im}(AV_i).

For an in-depth analysis of convergence for augmented methods, we recommend the thorough analysis of Saad [31]. We also refer to the general framework introduced by Gaul, Gutknecht, Liesen and Nabben [18], which allows one to describe all augmented, deflation-like methods in a single formalism [36].

Algorithm 2 Augmented GCRO-Like Algorithm (ii-th cycle)

  1. ri=b−Axir^i = b - Ax^i, Vi=[v1,i,…,vm,i]V_i = [v^{1,i},\ldots,v^{m,i}]

  2. QiRi=AViQ_iR_i = AV_i, Ci=QiC_i = Q_i, Ui=ViRi−1U_i = V_iR_i^{-1}

  3. Pi=I−CiCiTP_i = I-C_iC_i^\mathsf{T}

  4. r~i=Piri\tilde{r}^i = P_ir^i, z0=r~i/∥r~i∥z^0 = \tilde{r}^i/\|\tilde{r}^i\|

  5. [z0,…,zNI],Hi←Arnoldi⁡({z0,PiAz0,(PiA)2z0,…,(PiA)NIz0})[z^0,\ldots,z^{N_I}], H_i \leftarrow\operatorname{Arnoldi}(\{z^0,P_iAz^0,(P_iA)^2z^0,\ldots,(P_iA)^{N_I}z^0\})

  6. Wi=[Ui,z0,…,zNI−1]W_i = [U_i,z^0,\ldots,z^{N_I-1}]

  7. Zi=[Ci,z0,…,zNI]Z_i = [C_i,z^0,\ldots,z^{N_I}], s.t. AWi=ZiHiAW_i = Z_iH_i

  8. ζi=arg min⁡ζ∈RNI+m∥ZiTri−Hiζ∥\zeta^i = \operatorname*{arg\,min}_{\zeta\in\mathbb{R}^{N_I+m}}\|Z_i^\mathsf{T}r^i-H_i\zeta\|

  9. xi+1=xi+Wiζix^{i+1} = x^i + W_i\zeta^i

On-the-Fly Reduced Basis

The on-the-fly framework relies on the collection of so-called snapshots of a vector quantity xk∈Rnx^k \in\mathbb{R}^n that is computed at each iteration of an iterative process, which are stored in the columns of a snapshot matrix SNb∈Rn×NbS_{N_b} \in\mathbb{R}^{n\times N_b}, assumed to be full-rank. We note NbN_b the number of snapshots. Often, the snapshot matrix can also be centered, denoted S‾Nb\overline{S}_{N_b}, by subtracting the mean x‾Nb\overline{x}^{N_b} of all snapshots from each column. Notice that this reduces the rank of the matrix to Nb−1N_b-1. We consider a concrete application case. In a nonlinear solver, if a linear system Akxk=fkA_kx^k=f^k is solved at iterations k=1,…,Nbk=1,\ldots,N_b, then at iteration Nb+1N_b+1, the solution space of the system is restricted to either the full span of the snapshots, im⁡(S‾Nb)\operatorname{im}(\overline{S}_{N_b}), or to a subspace VNb⊆im⁡(S‾Nb)\mathcal{V}_{N_b}\subseteq\operatorname{im}(\overline{S}_{N_b}). In the second case, the search space is further reduced from dimension NbN_b to dimension m≤Nb≪nm\leq N_b\ll n. Suppose that VNb\mathcal{V}_{N_b} is spanned by an orthonormal basis, composed of the columns of a matrix VNb∈Rn×mV_{N_b}\in\mathbb{R}^{n\times m}. The solution can then be written as xNb+1=x‾Nb+VNbzNb+1x^{N_b+1}=\overline{x}^{N_b}+V_{N_b}z^{N_b+1}. There are multiple ways to determine the coefficients zNb+1z^{N_b+1} of the reduced solution, for instance residual minimization or Galerkin projection. In the case where there is no truncation, i.e., VNb=im⁡(S‾Nb)\mathcal{V}_{N_b}=\operatorname{im}(\overline{S}_{N_b}), then this method acts almost like a vector extrapolation algorithm, like RRE or MPE [4]. The main difference is that vector extrapolation would require solving the large-scale system at every iteration to construct the next extrapolated iterate, while the goal of the reduced basis is to bypass the solution of the system as often as possible. Thus, the snapshot matrix of the vector extrapolation method would be refreshed at each iteration with a new exact solution (often in a sliding window/FIFO pattern). On the other hand, the snapshot matrix of the on-the-fly reduced basis method would only be refreshed and recompressed every NIN_I iterations, which can be hardcoded, but ideally should be determined dynamically by using an error estimator for the reduced solution. This distinguishes them respectively as a convergence acceleration method and as a dimensionality reduction technique.

When the truncated case is considered, i.e., VNb⊊im⁡(S‾Nb)\mathcal{V}_{N_b} \subsetneq\operatorname{im}(\overline{S}_{N_b}) and dim⁡(VNb)=m<Nb\dim(\mathcal{V}_{N_b}) = m < N_b, the SVD is often used to determine the best low-rank approximation of S‾Nb\overline{S}_{N_b} and determine its range. Indeed, for S‾Nb=UNbΣNbTNbT\overline{S}_{N_b} = U_{N_b}\Sigma_{N_b}T_{N_b}^{\mathsf{T}}, the basis matrix VNbV_{N_b} can be selected as VNb=[UNb]mV_{N_b} = [U_{N_b}]_m ([⋅]j[\cdot]_j will be used to denote the restriction of a matrix to its first jj columns), since they are associated to the mm largest singular values of S‾Nb\overline{S}_{N_b}. mm can be chosen dynamically by ensuring a certain ratio of energy is conserved, like taking the smallest mm such that

∑i=1mσi2∑i=1Nb−1σi2>1−εrb2.(2)\frac{\sum_{i=1}^{m}\sigma_i^2}{\sum_{i=1}^{N_b-1}\sigma_i^2} > 1-\varepsilon_{\mathrm{rb}}^2. \tag*{(2)}

The classical way to find the reduced coefficients in the POD framework is by using a Galerkin projection, i.e., by solving the system

VNbTAkVNbzk+1=VNbT(fk−AkxNbk)(Nb+1≤k≤NI),V_{N_b}^{\mathsf{T}}A_kV_{N_b}z^{k+1}=V_{N_b}^{\mathsf{T}}\left(f^k-A_kx_{N_b}^k\right) \qquad(N_b+1\leq k\leq N_I),

which ensures the residual orthogonality condition fk−AkxRBk+1⊥im⁡(VNb)f^k-A_kx_{\mathrm{RB}}^{k+1}\perp\operatorname{im}(V_{N_b}).

When updating the snapshot matrix, the SVD has to be recomputed to take into account the new snapshots. Since the two operations done to S‾k\overline{S}_k are a mean-centering update and a column update, they can be represented as an additive rank-2 update. Thus, the full SVD of the matrix need not be recomputed, and the incremental SVD algorithm proposed by Brand [3] can be used to update the matrices UkU_k, TkT_k and Σk\Sigma_k at a lower cost, especially for larger mm values.

On-the-fly reduced bases have been applied to accelerate a wide variety of PDE-constrained optimization algorithms, including trust-region methods [43, 41], line-search methods [19], and MMA [42] (introduced by Svanberg [37]), as well as more generic nonlinear solvers like Newton-Krylov methods [22] or fixed-point methods [39] in fluid-structure interaction.

Theoretical Framework

Minimal Residual Method on the Reduced Subspace

Augmentation of Krylov methods with POD vectors is not a new concept in itself [6, 11, 12, 24, 38]. However, most methods rely on parametric POD, meaning that the linear system comes from a parametrized PDE, and the solution to this PDE is computed for multiple parameter values. Then, a reduced basis is computed with the SVD, which can then be used as augmentation vectors for a Krylov solver, when solving the system at a new parameter value. However, we will leverage the POD framework in a different way, to compress information within a single linear solve. An on-the-fly reduced basis will be constructed from the convergence history. The reduced basis plays the role of an augmentation of the Krylov subspace. Indeed, the residual minimization problem

min⁡ζ∈Rm∥ri−AViζ∥\min_{\zeta\in\mathbb{R}^{m}}\lVert r^i-AV_i\zeta\rVert

can be seen as restricting the search space to a reduced subspace, as well as the first intermediate minimization in an augmented Krylov method.

In this section, the notation u∘u_\circ will be used to denote a zero-padded vector uu. We propose a variant of LGMRES(NIN_I, kk) named GMRES-RB(NbN_b, NIN_I, εrb\varepsilon_{\mathrm{rb}}, mmax⁡m_{\max}). This method will run NbN_b regular GMRES iterations, producing intermediate iterates

xk=x0+Kkyk,k=1,…,Nb,x^k=x^0+K_ky^k,\qquad k=1,\ldots,N_b,

where Kk∈Rn×kK_k\in\mathbb{R}^{n\times k} is the Krylov subspace matrix at iteration kk and yk∈Rky^k\in\mathbb{R}^k is the correction in Krylov coordinates. Initially, a snapshot matrix S0S_0 will be made with the Nb−1N_b-1 zero-padded correction vectors, y∘k∈RNby^k_{\circ} \in\mathbb{R}^{N_b}, from which the final correction yNby^{N_b} is subtracted. With an SVD S0=U0Σ0T0TS_0 = U_0\Sigma_0T_0^\mathsf{T}, the m0m_0 principal left singular vectors are extracted, by using the criterion that 100⋅(1−εrb2)%100 \cdot(1-\varepsilon_{\mathrm{rb}}^2)\% of the energy is captured. Because of the subtraction by y∘Nby^{N_b}_{\circ}, the columns of the snapshot matrix represent the intermediate corrections as perturbations of the final correction. Heuristically, we hope this will help to detect directions that were harder to converge during a single cycle. Then, Algorithm 1 is started with the augmentation matrix V0=KNb[U0]m0,y∘NbV_0 = K_{N_b}[U_0]_{m_0},y^{N_b}_{\circ}, which effectively contains the total correction of the GMRES cycle and a subspace spanning significant corrections. Then, the NIN_I inner corrections associated to the inner Arnoldi iterations from z0,…,zk,0z^0,\ldots,z^{k,0}, are stored, which is not usually the case in a typical application of Algorithm 1. At the end of this cycle, the POD methodology is again applied to the corrections: the last correction is subtracted from the others, and an energy-based criterion is applied to the SVD to select dominant modes. Moreover, we add a maximal reduced basis size mmax⁡m_{\max}, which can be set to ∞\infty if no threshold needs to be imposed. The next cycle of Algorithm 1 is started with the resulting reduced basis Vi+1V_{i+1}. A pseudocode description is available in Algorithm 3.

Algorithm 3 GMRES-RB(Nb,NI,εrb,mmax⁡N_b,N_I,\varepsilon_{\mathrm{rb}},m_{\max})

  1. xGMRES0,εrb,mmax⁡,Nb,ε,NO,NIx_{\mathrm{GMRES}}^0,\varepsilon_{\mathrm{rb}},m_{\max},N_b,\varepsilon,N_O,N_I given

  2. Do NbN_b GMRES iterations, produces Krylov basis matrix KNbK_{N_b} and corrections yi∈Riy^i \in\mathbb{R}^i

  3. S0=[y∘0−y∘Nb,…,y∘Nb−1−y∘Nb]S_0 = [y_{\circ}^0-y^{N_b}_{\circ},\ldots,y_{\circ}^{N_b-1}-y^{N_b}_{\circ}]

  4. U0Σ0T0T=S0U_0\Sigma_0T_0^\mathsf{T}=S_0

  5. Choose the smallest m0m_0 such that [U0]m0[U_0]_{m_0} captures 100⋅(1−εrb2)%100\cdot(1-\varepsilon_{\mathrm{rb}}^2)\% of the energy

  6. m0←min⁡(m0,mmax⁡)m_0 \leftarrow\min(m_0,m_{\max})

  7. V0=KNb[U0]m0,y∘NbV_0=K_{N_b}[U_0]_{m_0},y^{N_b}_{\circ}

  8. xGMRES−RB0=xGMRESNbx_{\mathrm{GMRES-RB}}^0=x_{\mathrm{GMRES}}^{N_b}

  9. i=0i=0

  10. while ∥ri∥>ε\lVert r^i\rVert>\varepsilon and i<NOi<N_O do

  11. Apply Algorithm 1 with augmentation vectors ViV_i and initial data xix^i

  12. for k=1,…,NI−1k=1,\ldots,N_I-1 do

  13. Obtain the kk-th partial correction:

ζk,i=argmin⁡ζ∈Rk+mi+1 ∥ri−AWi(k)ζ∥,\zeta^{k,i}=\underset{\zeta\in\mathbb{R}^{k+m_{i+1}}}{\operatorname{argmin}}\ \lVert r^i-AW_i^{(k)}\zeta\rVert,

where Wi(k)=[z0,…,zk−1,Vi]W_i^{(k)}=[z^0,\ldots,z^{k-1},V_i]

  1. end for

  2. Si=[ζ∘1,i−ζi,…,ζ∘NI−1,i−ζi]S_i=[\zeta_{\circ}^{1,i}-\zeta^i,\ldots,\zeta_{\circ}^{N_I-1,i}-\zeta^i]

  3. Ui+1Σi+1Ti+1T=SiU_{i+1}\Sigma_{i+1}T_{i+1}^{\mathsf{T}}=S_i

  4. Choose the smallest mi+1m_{i+1} such that [Ui+1]mi+1[U_{i+1}]_{m_{i+1}} captures 100⋅(1−εrb2)%100\cdot(1-\varepsilon_{\mathrm{rb}}^2)\% of the energy

  5. mi+1←min⁡(mi+1,mmax⁡)m_{i+1}\leftarrow\min(m_{i+1},m_{\max})

  6. Vi+1=Wi[Ui+1]mi+1,ζiV_{i+1}=W_i[U_{i+1}]_{m_{i+1}},\zeta^i

  7. i←i+1i\leftarrow i+1

  8. end while

In practice, the partial residual minimization problems can be solved more efficiently by using directly restrictions of HiH_i. Also, about the padded snapshot vectors, notice that the zeros will have to be added in the middle of the vectors, to eliminate the columns from WiW_i associated to zk,…,zNI−1z^k,\ldots,z^{N_I-1}.

The present algorithm is just a wrapper around Algorithm 1 with an SVD-based choice for the augmentation vectors. Notice that all vectors in the augmentation basis of cycle i+1i+1 originate from cycle ii; this is one of the main differences with LGMRES and GCROT(m,km,k), where the augmentation vectors are the final corrections from the kk previous cycles. Also, for both of these methods, the criterion to determine which vector to keep is recency (first in, first out). Here, we propose that the final correction is always kept, but that additional vectors could be retained as well, using the energy-based criterion (2). Moreover, GCROT(m,km,k) is a special case of Algorithm 2, which projects the operator on the orthogonal complement of the augmentation basis at each cycle.

We also introduce four other variants of the algorithm:

  1. GMRES-RB-O(NbN_b, NIN_I, kk), which keeps the last correction and the k−1k-1 oldest snapshots in SiS_i;

  2. GMRES-RB-L(NbN_b, NIN_I, kk), which keeps the last correction and the k−1k-1 latest snapshots in SiS_i;

  3. GMRES-RB-C(NbN_b, NIN_I, εrb\varepsilon_{\mathrm{rb}}, mmax⁡m_{\max}, ω\omega), which compresses the cumulative history of retained modes with the energy criterion, weighted by ω∈(0,1)\omega\in(0,1);

  4. GCRO-RB(NbN_b, NIN_I, εrb\varepsilon_{\mathrm{rb}}, mmax⁡m_{\max}), which uses Algorithm 2 as an inner loop.

The third variant is worth exploring in more detail. In Algorithm 3, all the recycling information comes exclusively from the previous cycle. For some harder problems, history from previous cycle might help convergence as well. This is done by realizing that the columns NI+1N_I+1 to NI+mi+1N_I+m_i+1 of WiW_i are Vi=Wi−1[[Ui]mi,ζi−1]V_i=W_{i-1}[[U_i]_{m_i},\zeta^{i-1}], precisely the history that we want to preserve. We define

Γi=Rmi[Σi]mimi,\Gamma_i = R_{m_i}[\Sigma_i]_{m_i m_i},

where [Σi]mimi[\Sigma_i]_{m_i m_i} is the top-left, square mi×mim_i \times m_i submatrix of Σi\Sigma_i, and Rmi∈R(NI+mi+1)×miR_{m_i} \in\mathbb{R}^{(N_I+m_i+1)\times m_i} is a zero matrix with an mi×mim_i \times m_i identity matrix in the bottom. Its columns are the coordinates of ViV_i in the WiW_i basis, weighted by their original energy. We can consider the following augmented snapshot matrix for the SVD,

Si=[ωΓi,ζ∘1,i−ζi,…,ζ∘NI−1,i−ζi].S_i = [\omega\Gamma_i,\zeta^{1,i}_{\circ}-\zeta^i,\ldots,\zeta^{N_I-1,i}_{\circ}-\zeta^i].

Notice that information that is allowed to traverse multiple cycles will decrease geometrically with rate ω\omega.

The main advantage of doing the SVD on the corrections in Krylov coordinates is that the matrix to factor is much smaller than a matrix with snapshots of xkx^k directly. However, since the matrix WiW_i does not have orthonormal columns, doing the SVD on SiS_i is not equivalent, up to a rotation, to doing it on WiSiW_iS_i. Experimentally, it was noticed that doing the SVD on SiS_i directly yielded better results.

Relations to Known Methods

The GMRES-RB method, in exact arithmetic, can be seen as interpolating two other classical methods. In the extreme case where the energy criterion were to discard all modes (mmax⁡=0m_{\max}=0) and Nb=NIN_b=N_I, the method would coincide in exact arithmetic with LGMRES(NIN_I, 1); only the total correction from the previous cycle is kept. In GMRES-RB, since the augmented basis always contains the total correction of the last cycle as in LGMRES, regardless of the truncation, we know that the skip angles satisfy

cos⁡θ(ri+1,ri−1)=∥ri+1∥∥ri−1∥,\cos\theta(r^{i+1},r^{i-1})=\frac{\lVert r^{i+1}\rVert}{\lVert r^{i-1}\rVert},

which helps to alleviate slow, alternating patterns in the corrections [2]. On the contrary, when the energy criterion does not truncate anything (εrb=0\varepsilon_{\mathrm{rb}}=0 and mmax⁡=∞m_{\max}=\infty), the method is equivalent to NIN_I-ORTHOMIN(1), in exact arithmetic.

ss-ORTHOMIN(kk) is an ss-step Krylov method. These methods were first introduced by [7], with the goal of obtaining computational gains on parallel computer architectures [9]. Recent advances extended the ss-step methods to dynamically chosen ss parameter, to improve convergence [35]. Within the ii-th cycle, ss-ORTHOMIN(kk) produces the iterate xi+1x^{i+1} and the residual ri+1r^{i+1}, by residual minimization over the affine space xi+im⁡(Pi)x^i+\operatorname{im}(P_i). Then, a basis of Ks(A,ri+1)K_s(A,r^{i+1}) is computed, which is orthogonalized against the kk previous bases Pi,…,Pi−k+1P_i,\ldots,P_{i-k+1}, resulting in the new basis Pi+1P_{i+1}. P0P_0 is set to be a basis of Ks(A,r0)K_s(A,r^0). It acts as a batch Krylov method, each iteration using a correction in an ss-dimensional Krylov space. The special case NIN_I-ORTHOMIN(1) will be detailed in Algorithm 4.

Line 4 minimizes the residual over the correction search space im⁡(Pi)\operatorname{im}(P_i). However, if we consider the PiP_i's to be augmentation spaces, we would be interested in the minimization over im⁡(Pi−1)⊕im⁡(Ri)\operatorname{im}(P_{i-1})\oplus\operatorname{im}(R_i). We can show that these two spaces yield the same solution.

Algorithm 4 NIN_I-ORTHOMIN(1)

  1. x0x^0, r0=b−Ax0r^0=b-Ax^0, P0=[r0,Ar0,…,ANI−1r0]P_0=[r^0,Ar^0,\ldots,A^{N_I-1}r^0]

  2. i=0i=0

  3. while ∥ri∥>ε\lVert r^i\rVert>\varepsilon and i<NOi<N_O do

  4. ζi+1=argmin⁡ζ∈RNI∥ri−APiζ∥\zeta^{i+1}=\underset{\zeta\in\mathbb{R}^{N_I}}{\operatorname{argmin}}\lVert r^i-AP_i\zeta\rVert

  5. ri+1=ri−APiζi+1r^{i+1}=r^i-AP_i\zeta^{i+1}

  6. xi+1=xi+Piζi+1x^{i+1}=x^i+P_i\zeta^{i+1}

  7. Ri+1=[ri+1,Ari+1,…,ANI−1ri+1]R_{i+1}=[r^{i+1},Ar^{i+1},\ldots,A^{N_I-1}r^{i+1}]

  8. ATAA^\mathsf{T}A-orthogonalize Ri+1R_{i+1} against PiP_i, yields Pi+1P_{i+1}

  9. end while

Lemma 3.1. For PiP_i and RiR_i defined in Algorithm 4,

argmin⁡ρ∈im⁡(APi−1)⊕im⁡(ARi)∥ri−ρ∥=argmin⁡ρ∈im⁡(APi)∥ri−ρ∥.\underset{\rho\in\operatorname{im}(AP_{i-1})\oplus\operatorname{im}(AR_i)}{\operatorname{argmin}}\lVert r^i-\rho\rVert = \underset{\rho\in\operatorname{im}(AP_i)}{\operatorname{argmin}}\lVert r^i-\rho\rVert.

Proof. Consider the problem

ζi+1=argmin⁡ζ∈RNI∥ri−APiζ∥,\zeta^{i+1}=\underset{\zeta\in\mathbb{R}^{N_I}}{\operatorname{argmin}}\lVert r^i-AP_i\zeta\rVert,

yielding the NIN_I-ORTHOMIN(1) residual ri+1=ri−APiζi+1r^{i+1}=r^i-AP_i\zeta^{i+1}. If ΠAPi−1\Pi_{AP_{i-1}} is the orthogonal projector on im⁡(APi−1)\operatorname{im}(AP_{i-1}), we can show that ΠAPi−1ri+1=0\Pi_{AP_{i-1}}r^{i+1}=0. Indeed,

ΠAPi−1ri+1=ΠAPi−1ri−ΠAPi−1APiζi+1.\Pi_{AP_{i-1}}r^{i+1}=\Pi_{AP_{i-1}}r^i-\Pi_{AP_{i-1}}AP_i\zeta^{i+1}.

However, ri⊥APi−1r^i\perp AP_{i-1} by Petrov-Galerkin orthogonality, so the first term is 0. Moreover, since PiP_i is ATAA^\mathsf{T}A-orthogonal to Pi−1P_{i-1}, and

ΠAPi−1APi=APi−1(Pi−1TATAPi−1)−1Pi−1TATAPi(Pi−1TATAPi−1)−1Pi−1TATAPi⏟0.\Pi_{AP_{i-1}}AP_i=AP_{i-1}(P_{i-1}^\mathsf{T}A^\mathsf{T}AP_{i-1})^{-1}P_{i-1}^\mathsf{T}A^\mathsf{T}AP_i \underset{0}{\underbrace{\vphantom{\left(P_{i-1}^\mathsf{T}A^\mathsf{T}AP_{i-1}\right)^{-1}P_{i-1}^\mathsf{T}A^\mathsf{T}AP_i}}}.

the second term is also 0. Consequently, the residual ri+1r^{i+1} also satisfies the minimal residual problem with orthogonality constraint on im⁡(APi−1)⊕im⁡(APi)\operatorname{im}(AP_{i-1})\oplus\operatorname{im}(AP_i), since it is orthogonal to im⁡(APi−1)\operatorname{im}(AP_{i-1}). Moreover, since the orthogonalization at line 8 gives im⁡(Ri)⊕im⁡(Pi−1)=im⁡(Pi)⊕im⁡(Pi−1)\operatorname{im}(R_i)\oplus\operatorname{im}(P_{i-1})=\operatorname{im}(P_i)\oplus\operatorname{im}(P_{i-1}), then im⁡(APi−1)⊕im⁡(APi)=im⁡(APi−1)⊕im⁡(ARi)\operatorname{im}(AP_{i-1})\oplus\operatorname{im}(AP_i)=\operatorname{im}(AP_{i-1})\oplus\operatorname{im}(AR_i). By uniqueness of the minimizer, the statement of the lemma holds.

This makes it clear that since im⁡(Ri)=KNI(A,ri)\operatorname{im}(R_i)=\mathcal{K}_{N_I}(A,r^i), by identifying Vi=Pi−1V_i=P_{i-1}, we find that NIN_I-ORTHOMIN(1) is an augmented Krylov method that fits in the framework of Algorithm 1. Moreover, in GMRES-RB without any truncation due to SVD, we can show that the augmentation spaces Vi+1V_{i+1} are equivalently obtained by ATAA^\mathsf{T}A-orthogonalization of KNb(A,ri)\mathcal{K}_{N_b}(A,r^i) against ViV_i, meaning the two algorithms are actually the same in exact arithmetic.

Lemma 3.2. Assume that AViAV_i has full column rank for any cycle ii of GMRES-RB(NIN_I, NIN_I, 0, ∞\infty) and NIN_I-ORTHOMIN(1). Then, im⁡(Pi)=im⁡(Vi)\operatorname{im}(P_i)=\operatorname{im}(V_i) and rGMRES−RBi=rORTHOMINi+1r_{\mathrm{GMRES-RB}}^i=r_{\mathrm{ORTHOMIN}}^{i+1} in exact arithmetic.

Proof. To simplify the notation, the iterates, residuals and errors produced by GMRES-RB will have no subscript.

After the warmup in GMRES-RB, the initial augmentation basis spans KNI(A,rGMRES0)\mathcal{K}_{N_I}(A,r_{\mathrm{GMRES}}^0), the same as in NIN_I-ORTHOMIN(1), so im⁡(V0)=im⁡(P0)\operatorname{im}(V_0)=\operatorname{im}(P_0). Also at the end of the NIN_I GMRES iterations in exact arithmetic, the final residual would be the same as for NIN_I-ORTHOMIN(1) since no restart happened yet, meaning r0=rGMRESNb=rORTHOMIN1r^0=r_{\mathrm{GMRES}}^{N_b}=r_{\mathrm{ORTHOMIN}}^1.

During cycle i≥0i \ge0, assume the induction hypotheses im⁡(Vi)=im⁡(Pi)\operatorname{im}(V_i) = \operatorname{im}(P_i) and ri=rORTHOMINi+1r^i = r_{\mathrm{ORTHOMIN}}^{i+1}. The GMRES-RB algorithm minimizes over the same space as NIN_I-ORTHOMIN(1):

im⁡(Vi)+KNI(A,ri)=im⁡(Pi)+KNI(A,rORTHOMINi+1)=im⁡(Pi)⊕im⁡(Ri+1).\operatorname{im}(V_i) + \mathcal{K}_{N_I}(A,r^i) = \operatorname{im}(P_i) + \mathcal{K}_{N_I}(A,r_{\mathrm{ORTHOMIN}}^{i+1}) = \operatorname{im}(P_i) \oplus\operatorname{im}(R_{i+1}).

The first equality holds by the induction hypothesis, and Lemma 3.1 tells us that the space on the right is the NIN_I-ORTHOMIN(1) space. Thus the residuals ri+1r^{i+1} and rORTHOMINi+2r_{\mathrm{ORTHOMIN}}^{i+2} are equal.

The intermediate corrections problem, given by,

ζk,i=argmin⁡ζ∈Rk+mi+1 ∥ri−AWi(k)ζ∥,\zeta^{k,i} = \underset{\zeta\in\mathbb{R}^{k+m_{i+1}}}{\operatorname{argmin}}\ \lVert r^i - AW_i^{(k)}\zeta\rVert,

can be rewritten as

ζk,i=[αk,iβk,i],{αk,i,βk,i}=argmin⁡α,β ∥ri−A[Zi]kα−AViβ∥.\zeta^{k,i} = \begin{bmatrix} \alpha^{k,i} \\ \beta^{k,i} \end{bmatrix}, \qquad \{\alpha^{k,i},\beta^{k,i}\} = \underset{\alpha,\beta}{\operatorname{argmin}}\ \lVert r^i - A[Z_i]_k\alpha- AV_i\beta\rVert.

Thus, the intermediate correction can be written as xk,i−xi=[Zi]kαk,i+Viβk,ix^{k,i} - x^i = [Z_i]_k\alpha^{k,i} + V_i\beta^{k,i}. For a fixed α\alpha, the solution in β\beta is given by the normal equations

β=(ViTATAVi)−1ViTAT(ri−A[Zi]kα)=−(AVi)+A[Zi]kα,\beta= (V_i^{\mathsf{T}}A^{\mathsf{T}}AV_i)^{-1}V_i^{\mathsf{T}}A^{\mathsf{T}}(r^i - A[Z_i]_k\alpha) = -(AV_i)^+A[Z_i]_k\alpha,

where (⋅)+(\cdot)^+ denotes the Moore-Penrose pseudo-inverse for matrices with full column rank. Since im⁡(AVi)\operatorname{im}(AV_i) is a subspace of im⁡(AWi−1)\operatorname{im}(AW_{i-1}), and ri⊥im⁡(AWi−1)r^i \perp\operatorname{im}(AW_{i-1}), the first term is 0. For the optimal αk,i\alpha^{k,i}, the correction is

Wiζ∘k,i=xk,i−xi=(I−Vi(AVi)+A)[Zi]kαk,i,W_i\zeta_{\circ}^{k,i} = x^{k,i} - x^i = (I - V_i(AV_i)^+A)[Z_i]_k\alpha^{k,i},

which yields the following equalities, provided no breakdown happens:

im⁡(Vi+1)=im⁡(Wi[Ui+1,ζi])=im⁡(Wi[ζ∘1,i,…,ζi])=(I−ΠViATA)KNI(A,ri).\operatorname{im}(V_{i+1}) = \operatorname{im}(W_i[U_{i+1},\zeta^i]) = \operatorname{im}(W_i[\zeta_{\circ}^{1,i},\ldots,\zeta^i]) = (I-\Pi_{V_i}^{A^{\mathsf{T}}A})\mathcal{K}_{N_I}(A,r^i).

Notice that ΠViATA=Vi(AVi)+A\Pi_{V_i}^{A^{\mathsf{T}}A}=V_i(AV_i)^+A is the ATAA^{\mathsf{T}}A-orthogonal projector onto im⁡(Vi)\operatorname{im}(V_i), meaning that Vi+1V_{i+1} spans the Krylov subspace KNI(A,ri)\mathcal{K}_{N_I}(A,r^i), from which components of im⁡(Vi)\operatorname{im}(V_i) in the ATAA^{\mathsf{T}}A-inner product have been removed. For NIN_I-ORTHOMIN(1), the updated subspace would be equal by using the induction hypothesis (notice that the projector is independent of the basis chosen)

im⁡(Pi+1)=(I−ΠPiATA)KNI(A,rORTHOMINi+1)=(I−ΠViATA)KNI(A,ri).\operatorname{im}(P_{i+1}) = (I-\Pi_{P_i}^{A^{\mathsf{T}}A})\mathcal{K}_{N_I}(A,r_{\mathrm{ORTHOMIN}}^{i+1}) = (I-\Pi_{V_i}^{A^{\mathsf{T}}A})\mathcal{K}_{N_I}(A,r^i).

By induction, since the initial subspaces and residuals are the same, they will remain the same since they are transformed in the same way.

Proposition 3.1. The untruncated GMRES-RB(NI,NI,0,∞)(N_I,N_I,0,\infty) method coincides, in exact arithmetic, with NIN_I-ORTHOMIN(1), i.e., xGMRES−RBi=xORTHOMINi+1x_{\mathrm{GMRES-RB}}^i=x_{\mathrm{ORTHOMIN}}^{i+1} for i≥0i \ge0.

Proof. Direct consequence of Lemma 3.2. The shift by 1 comes from the fact that the iterate of the GMRES warmup phase is xGMRES−RB0x_{\mathrm{GMRES-RB}}^0, but is the first ORTHOMIN iterate.

Now that this equivalence is established, we can use other equivalences proven by Chronopoulos [8], for specific classes of matrices. In particular, when AA is symmetric, the method matches MINRES in exact arithmetic.

Corollary 3.1. Let MM and NN be symmetric and skew-symmetric matrices respectively. Suppose A=MA=M, A=NA=N or A=I−NA=I-N. Moreover, assume that for some NI≥2N_I \ge2, ANIA^{N_I} is definite. Then, in exact arithmetic, GMRES and GMRES-RB(NI,NI,0,∞)(N_I,N_I,0,\infty) produce the same iterates if they start from the same initial point x0x^0. More precisely, xGMRES−RBi=xGMRES(i+1)NIx_{\mathrm{GMRES-RB}}^i=x_{\mathrm{GMRES}}^{(i+1)N_I} for i≥0i \ge0.

Proof. Theorem 5.5 and Corollary 5.1 of Chronopoulos [8] yield the result, because of an equivalence between ss-ORTHOMIN(1) and ss-GCR for some matrices, and then an equivalence between ss-GCR and full GCR when AsA^{s} is definite. GCR is equivalent to GMRES in exact arithmetic, see for instance the consequences of Lemma 6.21 from Saad [32].

This gives a first heuristic of why the proposed algorithm would work well. If for instance, the matrix AA is symmetric or skew-symmetric, and the truncated approximation space is a very good approximation of the untruncated one (e.g., there is fast decay of the singular values, by the Eckart-Young theorem [13]), then the method should approximate in some sense the behaviour of GMRES. It is not unlikely that the algorithm will also behave nicely when applied to matrices which are perturbations of symmetric or skew-symmetric matrices as a consequence. Moreover, in the case NI=2N_I = 2 and where AA is symmetric, GMRES-RB(2,2,0,∞\infty) transfers two vectors in its reduced basis to the next cycle, meaning WiW_i will contain four vectors, and that maintaining orthogonality to this window of four vectors is enough to construct the polynomial representation of the solution; GMRES-RB can capture the short-term recurrence if it exists.

For the GCRO-RB variant, we also see that in the case where all vectors are truncated, GCRO-RB(NI+1,NI,0,0N_I+1,N_I,0,0) is equivalent to GCROT(NI,1N_I,1), where only the final correction of the last cycle is kept. In a sense, GCROT(m,km,k) is really the deflated analog of LGMRES(m,km,k); they use the same information for the augmentation basis, but the former also projects the operator.

Error Analysis

For augmented Krylov methods, improved convergence rates or recycling properties are often obtained by using the hypothesis that the augmentation space approximates an appropriate AA-invariant subspace [31, 15, 29, 21]. However, the hypothesis that the space generated by the snapshots contains or approximates well-enough the right invariant subspace cannot be verified a priori in general. Baker et al. [2, 1] propose convergence analyses based on angles between residuals to estimate how truncated GMRES or LGMRES oscillates. As mentioned in the previous section, we already capture the skip angles property because the last correction is in the augmentation subspace.

We study global behaviour of the GMRES-RB algorithm, meaning that we determine the error between GMRES-RB and full, untruncated GMRES.

Lemma 3.3. The correction search spaces generated by GMRES-RB satisfy

im⁡(Vi)⊂KNb+iNI(A,rGMRES0),\operatorname{im}(V_i) \subset\mathcal{K}_{N_b+iN_I}(A,r^0_{GMRES}),
im⁡(Wi)⊂KNb+(i+1)NI(A,rGMRES0),\operatorname{im}(W_i) \subset\mathcal{K}_{N_b+(i+1)N_I}(A,r^0_{GMRES}),

where rGMRES0r^0_{GMRES} is the residual at the beginning of the warmup phase.

Proof. After the warmup phase, im⁡(V0)⊂KNb(A,rGMRES0)\operatorname{im}(V_0) \subset\mathcal{K}_{N_b}(A,r^0_{GMRES}). Also, r0=rGMRESNb∈KNb+1(A,rGMRES0)r^0 = r^{{N_b}}_{GMRES} \in\mathcal{K}_{N_b+1}(A,r^0_{GMRES}). Consequently, the first NIN_I vectors of W0W_0, which span KNI(A,r0)\mathcal{K}_{N_I}(A,r^0) are all in KNb+NI(A,rGMRES0)\mathcal{K}_{N_b+N_I}(A,r^0_{GMRES}). The last m0m_0 columns are the columns of V0V_0, meaning that the whole im⁡(W0)\operatorname{im}(W_0) is contained in KNb+NI(A,rGMRES0)\mathcal{K}_{N_b+N_I}(A,r^0_{GMRES}). The base case is satisfied; we assume the strong induction hypothesis

im⁡(Vs)⊂KNb+sNI(A,rGMRES0),\operatorname{im}(V_s) \subset\mathcal{K}_{N_b+sN_I}(A,r^0_{GMRES}),
im⁡(Ws)⊂KNb+(s+1)NI(A,rGMRES0),\operatorname{im}(W_s) \subset\mathcal{K}_{N_b+(s+1)N_I}(A,r^0_{GMRES}),

for s≤is \leq i. By construction of the augmentation basis in Algorithm 3,

im⁡(Vi+1)⊂im⁡(Wi)⊂KNb+(i+1)NI(A,rGMRES0).\operatorname{im}(V_{i+1}) \subset\operatorname{im}(W_i) \subset\mathcal{K}_{N_b+(i+1)N_I}(A,r^0_{GMRES}).

Following the construction of WiW_i in Algorithm 1,

im⁡(Wi+1)=im⁡(Vi+1)+KNI(A,ri+1).\operatorname{im}(W_{i+1}) = \operatorname{im}(V_{i+1}) + \mathcal{K}_{N_I}(A,r^{i+1}).

However, ri+1∈KNb+(i+1)NI+1(A,rGMRES0)r^{i+1} \in\mathcal{K}_{N_b+(i+1)N_I+1}(A,r_{\mathrm{GMRES}}^0), since

ri+1=r0−∑j=0iAWjζjr^{i+1}=r^0-\sum_{j=0}^{i}AW_j\zeta^j

with r0∈KNb+1(A,rGMRES0)r^0 \in\mathcal{K}_{N_b+1}(A,r_{\mathrm{GMRES}}^0) and the second term being in AKNb+(i+1)NI(A,rGMRES0)A\mathcal{K}_{N_b+(i+1)N_I}(A,r_{\mathrm{GMRES}}^0). Thus, KNI(A,ri+1)⊂KNb+(i+2)NI(A,rGMRES0)\mathcal{K}_{N_I}(A,r^{i+1}) \subset\mathcal{K}_{N_b+(i+2)N_I}(A,r_{\mathrm{GMRES}}^0). To conclude,

im⁡(Wi+1)⊂KNb+(i+2)NI(A,rGMRES0).\operatorname{im}(W_{i+1}) \subset\mathcal{K}_{N_b+(i+2)N_I}(A,r_{\mathrm{GMRES}}^0).

This loose inclusion is sufficient to show the following proposition, which give the exact error terms of GMRES-RB when compared to full, untruncated GMRES. The accuracy is directly controlled by how well the vector Δi=xGMRESNb+(i+1)NI−xGMRES−RBi\Delta^i=x_{\mathrm{GMRES}}^{N_b+(i+1)N_I}-x_{\mathrm{GMRES-RB}}^i is approximated in the augmented subspace im⁡(Wi)\operatorname{im}(W_i) with respect to the ATAA^\mathsf{T}A-inner product.

Proposition 3.2. For i≥0i \ge0, let eGMRESNb+(i+1)NIe_{\mathrm{GMRES}}^{N_b+(i+1)N_I} be the full GMRES error, and eGMRES−RBi+1e_{\mathrm{GMRES-RB}}^{i+1} be the corresponding GMRES-RB error. They satisfy the following identity:

∥eGMRES−RBi+1∥ATA2=∥eGMRESNb+(i+1)NI∥ATA2+∥(I−ΠWiATA)Δi∥ATA2,\left\lVert e_{\mathrm{GMRES-RB}}^{i+1}\right\rVert_{A^\mathsf{T}A}^{2}=\left\lVert e_{\mathrm{GMRES}}^{N_b+(i+1)N_I}\right\rVert_{A^\mathsf{T}A}^{2}+\left\lVert\left(I-\Pi_{W_i}^{A^\mathsf{T}A}\right)\Delta^i\right\rVert_{A^\mathsf{T}A}^{2},

where ΠWiATA\Pi_{W_i}^{A^\mathsf{T}A} is the orthogonal projector on im⁡(Wi)\operatorname{im}(W_i) w.r.t. the ATAA^\mathsf{T}A-inner product.

Proof. To shorten the notation in the proof, the GMRES-RB subscript will be dropped when referring to GMRES-RB iterates, residuals, and errors. Also, let j:=Nb+(i+1)NIj := N_b+(i+1)N_I.

Let x∗x^* be the exact solution to Ax∗=bAx^*=b. We know that ri=Aeir^i=Ae^i where ei=x∗−xie^i=x^*-x^i. The residual satisfies

∥ri+1∥=min⁡ζ∈RNI+mi+1∥ri−AWiζ∥.\left\lVert r^{i+1}\right\rVert=\min_{\zeta\in\mathbb{R}^{N_I+m_{i+1}}}\left\lVert r^i-AW_i\zeta\right\rVert.

Then, let eGMRESj=x∗−xGMRESje_{\mathrm{GMRES}}^j=x^*-x_{\mathrm{GMRES}}^j. We have that rGMRESj=AeGMRESjr_{\mathrm{GMRES}}^j=Ae_{\mathrm{GMRES}}^j and by Lemma 3.3

ei−eGMRESj=xGMRESj−xi=(xGMRESj−xGMRES0)−(xi−xGMRES0)∈Kj(A,rGMRES0).e^i-e_{\mathrm{GMRES}}^j=x_{\mathrm{GMRES}}^j-x^i=(x_{\mathrm{GMRES}}^j-x_{\mathrm{GMRES}}^0)-(x^i-x_{\mathrm{GMRES}}^0)\in\mathcal{K}_j(A,r_{\mathrm{GMRES}}^0).

Then, we can additively shift the problem by A(ei−eGMRESj)A(e^i-e_{\mathrm{GMRES}}^j),

∥ri+1∥2=min⁡ζ∈RNI+mi+1∥rGMRESj+A(ei−eGMRESj−Wiζ)∥2.\left\lVert r^{i+1}\right\rVert^2=\min_{\zeta\in\mathbb{R}^{N_I+m_{i+1}}}\left\lVert r_{\mathrm{GMRES}}^j+A(e^i-e_{\mathrm{GMRES}}^j-W_i\zeta)\right\rVert^2.

The second term in the sum is in AKjA\mathcal{K}_j because of the inclusion in Lemma 3.3. Because rGMRESj⊥AKjr_{\mathrm{GMRES}}^j \perp A\mathcal{K}_j, the Pythagorean theorem gives

∥ri+1∥2=∥rGMRESj∥2+min⁡ζ∈RNI+mi+1∥A(xGMRESj−xi−Wiζ)∥2.\left\lVert r^{i+1}\right\rVert^2=\left\lVert r_{\mathrm{GMRES}}^j\right\rVert^2+\min_{\zeta\in\mathbb{R}^{N_I+m_{i+1}}}\left\lVert A(x_{\mathrm{GMRES}}^j-x^i-W_i\zeta)\right\rVert^2.

By converting everything in terms of the error,

∥ei+1∥ATA2=∥eGMRESj∥ATA2+min⁡w∈im⁡(Wi)∥xGMRESj−xi−w∥ATA2,\left\lVert e^{i+1}\right\rVert_{A^\mathsf{T}A}^{2}=\left\lVert e_{\mathrm{GMRES}}^j\right\rVert_{A^\mathsf{T}A}^{2}+\min_{w\in\operatorname{im}(W_i)}\left\lVert x_{\mathrm{GMRES}}^j-x^i-w\right\rVert_{A^\mathsf{T}A}^{2},

and the last term is given by the orthogonal projector onto im⁡(Wi)\operatorname{im}(W_i) for the ATAA^\mathsf{T}A-inner product.

Proposition 3.2 could be reinterpreted more generally in terms of geometry of nested Krylov subspaces. However, to keep it more understandable and interpretable, we will keep it specific to the case at hand and refer to the articles of Eiermann, Ernst and Schneider [15, 14] for a more general study. Moreover, this conclusion is not unique to GMRES-RB, in the sense that the selection mechanism of the augmentation vectors did not matter in the proof. The only thing required is that the construction of Lemma 3.3 remains true, i.e., that the augmentation vectors at the start of a cycle are subspaces of the right Krylov subspace.

xGMRES−RBix_{\mathrm{GMRES-RB}}^{i} represents the starting point at beginning of cycle ii. Δi\Delta^{i} represents the next full GMRES iterate, from which all current progress from GMRES-RB has been removed. Thus, the discrepancy between the next GMRES and GMRES-RB iterates is quantified by how much of the remaining necessary progress is orthogonal to the current search space, in the ATAA^{\mathsf{T}}A-norm.

Numerical Experiments

Comparison to Other Solvers

The reduced basis methods will be compared to classical, state-of-the-art augmented Krylov methods. As a representative of methods of the GCRO family (Algorithm 2), GCRO-DR, with either Rayleigh–Ritz or harmonic Ritz vectors will be used. This method will be implemented in the same framework as GCRO-RB, with only the augmented basis construction algorithm changing between the two. Methods which use corrections from previous cycles will also be compared against our proposed algorithms. The implementations of LGMRES and GCROT(m,km,k) from SciPy 1.15.0 [40] will be used. This implementation of GCROT(m,km,k) also has the capability to use de Sturler’s optimal truncation based on the largest principal angles, which will also be compared against. The baseline algorithms GMRES and GMRES(mm) will also be taken from SciPy. Also, the choice Nb=NIN_b = N_I will be maintained to match the cycles of other methods.

2D Convection-Diffusion Problem

As a first example, we use the convection-diffusion problem [25, 2]

Δu+C∂u∂x=−(41)2,\Delta u + C\frac{\partial u}{\partial x} = -(41)^2,

for multiple CC values. The discretized operator is obtained from a centered finite difference stencil on the unit square, with h=1/41h = 1/41. The boundary conditions are homogeneous Dirichlet conditions. The initial value of the solver will be set to x0=0x^0 = 0.

For small CC, the symmetric part of the discretized matrix is dominant with respect to the skew-symmetric part, and large CC reverses this relationship. Corollary 3.1 gives the intuition that for symmetric or skew-symmetric matrices, the behaviour of the algorithm should become closer to that of GMRES when the truncation preserves most of the information. By sweeping CC values on this problem, we can observe the behaviour for matrices with a varying degree of dominance between the symmetric and skew-symmetric parts. The ratio of the norm of the skew-symmetric part to the norm of the symmetric part will vary between roughly 1/262 to 412, i.e., from mostly diffusive (symmetric) to mostly advective (skew-symmetric) problems. Table 1 shows how the considered CC values and their associated ratio vary.

CC∥AT−A∥F/∥AT+A∥F\lVert A^{\mathsf{T}} - A\rVert_F/\lVert A^{\mathsf{T}} + A\rVert_F
00
10.003817
410.1565
16816.417
107901411.9

Table 1. Ratio of the skew-symmetric part energy to symmetric part energy for multiple values of the advection coefficient CC.

Comparison of the Reduced Basis Selection Rules

The first test consists of comparing all the variants (-O, -L, -C, GCRO-RB) of GMRES-RB. To accurately measure which selection criteria/augmented subspace contains the richest information, all methods will be constrained to choose the same number of augmentation vectors, or the same budget, kk. For the methods relying on an energy criterion (GMRES-RB and GMRES-RB-C), this will be enforced by setting εrb=0\varepsilon_{\mathrm{rb}}=0 and mmax⁡=k−1m_{\max}=k-1, to keep the total correction and k−1k-1 singular vectors. The basis size will be independent of εrb\varepsilon_{\mathrm{rb}}, but the singular vectors will still be ranked according to their energy instead of their recency. In the case of GMRES-RB-C, the damping coefficient will be set to ω=0.5\omega=0.5. Moreover, we will validate that setting k=NIk=N_I and k=1k=1 indeed match the performance of full GMRES and LGMRES(NIN_I, 1), by choosing C=0C=0, a pure Laplace problem, which is SPD. Figure 1 and Figure 2 show the convergence of the relative residual norm for all variants at k=1,3,5,7,10k=1,3,5,7,10 for NI=10N_I=10, and k=1,5,10,20,30k=1,5,10,20,30 for NI=30N_I=30.

Comparison plot of the different variants of GMRES-RB at fixed budget $k$ on the Laplacian problem for $N_I=10$

Figure 1. Comparison between the different variants of GMRES-RB at fixed budget kk on the Laplacian (C=0C=0) problem, for NI=10N_I=10.

Comparison plot of the different variants of GMRES-RB at fixed budget $k$ on the Laplacian problem for $N_I=30$

Figure 2. Comparison between the different variants of GMRES-RB at fixed budget kk on the Laplacian (C=0C=0) problem, for NI=30N_I=30.

First, we notice that in both cases, full GMRES and LGMRES(NIN_I,1) are exactly or almost exactly replicated by the budgets k=NIk=N_I and k=1k=1, due to round-off errors, which validates the conclusions of Corollary 3.1. Then, when comparing at equal budget, a ranking emerges. The best-performing methods at an equal budget are those based on the energy criterion; GMRES-RB-C first, then GMRES-RB. In the case NI=10N_I=10, we confirm that GMRES-RB-C is not equivalent to GMRES, even when there is no truncation, because the cumulative history prevents all corrections from the current cycle from being preserved. Thus, at k=10k=10, it is outperformed by the other variants. However, as soon as truncation takes place, GMRES-RB-C requires fewer matvecs when compared with the others at equal budget. This means that information carried from multiple previous cycles does help to accelerate convergence. To measure how much information can be attributed to the historical augmented basis, we can measure the magnitude of the jj-th column of UiU_i, uju^j in the recycled part of the basis, i.e., ∥Rmi⊤uj∥\lVert R_{m_i}^{\top}u^j\rVert. These values are averaged over multiple cycles in Table 2. The most remarkable thing to notice is that the leading POD modes almost always lies exactly in the cumulative space, except for a few components. This is potentially due to the choice of ω=0.5\omega=0.5, which does not decrease sufficiently fast with respect to the magnitude of the snapshots through the cycles. However, as it will be seen in the following experiments, this choice gives a relatively performant method with respect to the other state-of-the-art methods that will be studied. The interpretation of this phenomenon is that the cumulative history compression process is a hybrid between picking the total correction of the last kk cycles, like LGMRES or GCROT would do, and the memoryless GMRES-RB, that only gets information from the current cycle. As will be seen in later experiments, although the exact composition of the subspace is not easily characterized, it proves to be, at times, richer than both the subspaces of LGMRES and GMRES-RB.

k=2k=2k=3k=3k=4k=4k=5k=5k=6k=6k=7k=7k=8k=8k=9k=9k=10k=10
∥Rmi⊤uj∥2\lVert R_{m_i}^{\top}u^j\rVert^21.001.001.001.001.001.001.000.880.89

Table 2. Component ∥Rmi⊤uj∥2\lVert R_{m_i}^{\top}u^j\rVert^2 of the k−1k-1 leading POD modes of GMRES-RB-C in the recycled space Vi=Wi−1[Ui]miV_i=W_{i-1}[U_i]_{m_i} (mean over modes, median over cycles), for C=0C=0, NI=10N_I=10.

In the NI=30N_I=30 case, we notice the high level of compressibility of the per-cycle history for this problem. Indeed, the SVD-based criterion in GMRES-RB and GMRES-RB-C, by keeping only k=10k=10 of the 30 available snapshots (or 30+mi30+m_i for GMRES-RB-C), required only a handful more matvecs than GMRES needed to reach the same tolerance. In particular, for GMRES-RB-C, k=5k=5 needed only around 15 more matvecs, and outperformed all the other variants by nearly 30 matvecs.

It is also quite clear that for this problem, the information encoded by the oldest snapshots is richer than the latest, because at equal budget, GMRES-RB-O consistently requires 20 to 40 fewer matvecs than GMRES-RB-L. There are two possible hypotheses as to why this happens. First, the optimal case would be to keep all the snapshots. By measuring ∥(I−ΠVi+1)Si∥F\lVert(I-\Pi_{V_{i+1}})S_i\rVert_F, we can determine how much of the full space is captured by the reduced basis. Table 3 shows that POD (which gives the optimal choice) is indeed lower than both other schemes, but the latest snapshots capture more of the full space at small kk, which does not reflect the convergence behaviour observed in Figure 1, which is faster at any kk.

Keptk=1k = 1k=2k = 2k=3k = 3k=4k = 4k=5k = 5k=6k = 6k=7k = 7k=8k = 8k=9k = 9
Oldest0.220.0900.0420.0250.0130.00720.00360.00180.00073
Latest0.220.0810.0350.0180.00910.00610.00400.00230.00094
Energy0.220.0530.00920.00450.00170.00110.000740.000500.00028

Table 3. Projection error ∥(I−ΠVi+1)Si∥F/∥Si∥F\lVert(I-\Pi_{V_{i+1}})S_i\rVert_F/\lVert S_i\rVert_F of the full space on space spanned by the kk oldest/latest snapshots and leading POD modes, for C=0C = 0 and NI=10N_I = 10.

This leads to the second hypothesis, which is that the oldest snapshots span the Krylov space Kk(A,ri)\mathcal{K}_k(A,r^i), and the newest snapshots do not span a proper Krylov space, even if they are contained in one. In any case, the principal angles between the augmentation spaces spanned by the oldest/latest vectors and leading POD modes are shown in Table 4 and Table 5. What it shows is that POD captures a large subspace of dimension k−2k - 2 or k−3k - 3 of both GMRES-RB-L and GMRES-RB-O. However, the extra dimensions are more aligned with the content of GMRES-RB-O. This hints at the fact that POD might approximate well a Krylov subspace with additional helpful directions.

kkθ1\theta_1θ2\theta_2θ3\theta_3θ4\theta_4θ5\theta_5θ6\theta_6θ7\theta_7θ8\theta_8θ9\theta_9
2026.8
301.848.0
400.110.069.6
5000.719.979.1
60001.026.381.7
700000.820.879.5
800000010.968.7
90000000048.0

Table 4. Median principal angles θi\theta_i (degrees) between the augmentation spaces built by GMRES-RB and GMRES-RB-O at budget kk, for C=0C = 0, NI=10N_I = 10.

kkθ1\theta_1θ2\theta_2θ3\theta_3θ4\theta_4θ5\theta_5θ6\theta_6θ7\theta_7θ8\theta_8θ9\theta_9
2031.7
305.362.9
400.726.584.3
5004.050.186.8
6000.19.158.588.3
700008.461.188.0
800000047.986.8
90000000082.2

Table 5. Median principal angles θi\theta_i (degrees) between the augmentation spaces built by GMRES-RB and GMRES-RB-L at budget kk, for C=0C = 0, NI=10N_I = 10.

The Diffusion-Dominated Case

The cases where C=1C = 1 and C=41C = 41 will be studied. For these values, the operator is still diffusion-dominated. Figure 3 shows convergence curves for NI=10N_I = 10 and Figure 4 for NI=30N_I = 30 when C=1C = 1 (resp. Figure 5 and Figure 6 in the case C=41C = 41). We note that since k=1k = 1 is equivalent to LGMRES for GMRES-RB and GMRES-RB-C, they will be excluded from the figures if k=1k = 1 is present.

Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem

Figure 3. Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem (C=1C = 1) with a fixed budget kk, and NI=10N_I = 10.

Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem

Figure 4. Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem (C=1C = 1) with a fixed budget kk, and NI=30N_I = 30.

Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem

Figure 5. Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem (C=41C = 41) with a fixed budget kk, and NI=10N_I = 10.

Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem

Figure 6. Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem (C=41C = 41) with a fixed budget kk, and NI=30N_I = 30.

The most striking feature of these figures is that at equal budgets, the deflation methods GCRO-DR with either harmonic Ritz or Ritz vectors outperform all other methods. This is to be expected, since these methods approximate invariant subspaces, and benefit from provably improved convergence rates.

One of the noticeable things that can be observed is that in the case NI=10N_I = 10, C=41C = 41, the behaviour in kk is nonmonotonic. For multiple methods, notably GCRO-DR with harmonic vectors, GMRES-RB and GCRO-RB, k=7k = 7 performs significantly better than k=10k = 10.

The plain GMRES-RB method is generally lagging behind every other algorithm at equal budget, except sometimes for LGMRES at higher CC and NIN_I. This behaviour is slightly surprising, since in the C=0C = 0 case, GMRES-RB largely outperformed GCRO-RB at the same budget, but introducing even a relatively small amount of advection (C=1C = 1, skew-sym. to sym. ratio well under 1%) reversed the trend. This indicates that the behaviour of GMRES-RB is very sensitive to departure from symmetry. On the contrary, GMRES-RB-C, for largest kk values, seems to outperform or at least approximately match both GCROT variants at equal budget. However, there seems to be some sensitivity to the value of kk, since in the case C=41C = 41 and NI=10N_I = 10, taking k=3k = 3 leads GMRES-RB-C to be the second worst method. What is also surprising is that GMRES(10) outperforms most reduced basis methods and classical methods for C=41C = 41 and NI=10N_I = 10.

The Advection-Dominated Case

The case C=1681C = 1681 yields a ratio of approximately 6 between the skew-symmetric and symmetric parts. Figure 7 shows what happens at NI=10N_I = 10, and Figure 8 at NI=30N_I = 30. In that case, GMRES-RB-C again outperforms the other reduced-basis methods. In fact, in this regime, the method performs almost as well as (or even slightly outperforms, in the case NI=10N_I = 10) the deflation methods at larger kk. Most of the time, it beats the tested GCROT methods. However, at small kk, the trend reverses and it is almost always the worst method. As for GCRO-RB and GMRES-RB the former still requires fewer matvecs than the latter, especially at NI=30N_I = 30.

Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem

Figure 7. Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem (C=1681C = 1681) with a fixed budget kk, and NI=10N_I = 10.

Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem

Figure 8. Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem (C=1681C = 1681) with a fixed budget kk, and NI=30N_I = 30.

The last parameter value studied, C=107901C = 107901, makes the problem largely dominated by advection, and the relative distance from AA to its skew-symmetric part is around 0.2%. Figure 9 and Figure 10 show the convergence behaviour at NI=10N_I = 10 and NI=30N_I = 30 respectively. Because well-performing methods are clustered between 100 and 400 matvecs, the number of matvecs for each budget is also shown in Table 6 and Table 7.

Methodk=1k = 1k=2k = 2k=3k = 3k=5k = 5k=7k = 7k=10k = 10
GMRES-RB294270294290290280
GMRES-RB-C294284298348286308
GCRO-RB2692318520404332238
GCRO-DR harmonic177617761252746418376
GCRO-DR Ritz172017201084548252242
GCROT31634391442124119122135
GCROT de Sturler31634291148–––
LGMRES296322274290288266

Table 6. Number of matvecs required to reach convergence, C=107901C = 107901, NI=10N_I = 10. The number in bold is the lowest in its column.

Methodk=1k = 1k=2k = 2k=3k = 3k=5k = 5k=7k = 7k=10k = 10k=20k = 20k=30k = 30
GMRES-RB302274264300312340350242
GMRES-RB-C302296278238272262268222
GCRO-RB432494558752702664402216
GCRO-DR harmonic658658260268216214198192
GCRO-DR Ritz368368280244214210198190
GCROT4659651030121215941205297398
GCROT de Sturler465941870–––297398
LGMRES302326312300300300300300

Table 7. Number of matvecs required to reach convergence, C=107901C = 107901, NI=30N_I = 30. The number in bold is the lowest in its column.

Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem

Figure 9. Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem (C=107901C = 107901) with a fixed budget kk, and NI=10N_I = 10.

Comparison between variants of GMRES-RB and other classical solvers

Figure 10. Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem (C=107901C = 107901) with a fixed budget kk, and NI=30N_I = 30.

The global observation here is that for this problem setup, GMRES-RB starts to show some promise again. On larger budgets k≥7k \ge7, GCRO-DR with Rayleigh–Ritz vectors starts picking up and it significantly reduces the number of matvecs required. For NI=k=10N_I = k = 10, GCRO-RB is also able to beat the deflation method by a few matvecs. However, for smaller budgets k≤5k \le5, GMRES-RB and GMRES-RB-C always come on top, except once to GCRO-DR and once to LGMRES (as mentioned earlier, in the case k=1k = 1, it is equivalent to LGMRES in exact arithmetic). The magnitude of the gains when compared to classical methods is modest in most cases, but the best recorded case happens at budget k=2k = 2. The closest method to GMRES-RB is LGMRES for both NIN_I values, and it requires 19% more matvecs than the former.

Conclusion

This work introduces a family of accelerated Krylov methods, based on the framework of on-the-fly reduced bases. We show that these methods fit naturally in the framework of augmented Krylov methods, the main difference being that the augmentation vectors are obtained from a data-driven criterion. We show that if the basis is not truncated, i.e., it consists of all intermediate corrections completed in the current cycle, the proposed GMRES-RB algorithm is equivalent in arithmetic to an ss-step ORTHOMIN(kk) method. By using known results about this algorithm, it is possible to deduce that for symmetric or skew-symmetric matrices, the existence of a short-recurrence orthogonalization algorithm will ensure that GMRES-RB also coincides with GMRES in exact arithmetic. We can conjecture that matrices that are either close to symmetric or skew-symmetric could make the reduced basis methods behave well.

We then illustrate numerically that some methods in the proposed family, especially GMRES-RB-C, can perform almost as well as deflation methods for a similar budget. It also often outperforms correction-based augmentation methods like GCROT and LGMRES, especially when the matrices are very close to being either symmetric or skew-symmetric, and for larger kk values. The plain GMRES-RB method also performs well in these extremal cases, but for general, nonsymmetric matrices, it is generally outperformed by other augmentation algorithms. This allows us to conclude that preserving some convergence history from previous cycles as well as from the current cycle is important to preserve an improved global convergence rate, except for instance when the matrix is SPD, where GMRES is matched exactly by untruncated GMRES-RB.

A follow-up problem to the conclusions of this work is to establish exactly the rate at which departure from symmetry or skew-symmetry degrades the performance of GMRES-RB. Another relevant question, in the case of GMRES-RB-C, is to understand how departure from symmetry is compensated by the presence of the compressed convergence history, and how to balance in a more refined way the choice between information from older and later cycles. In particular, we hope that this could bring greater stability to GMRES-RB-C, because smaller kk values made it behave poorly. Moreover, it would be interesting to relate the properties of AA and the decay of the singular values of the snapshot matrix, which would tell us how many modes can be truncated in each situation without degrading too much the short-recurrence in the symmetric case. More generally, the understanding of the mechanisms behind the improved convergence with respect to GMRES(mm), even in the SPD case, needs to be improved.

Acknowledgements

The author thanks Prof. Félix Kwok and Prof. Jean Deteix for enlightening discussions and advice about the ideas and content of this manuscript.

Conflict of Interest

The author declares no conflict of interest.

Funding

The author was funded by a Natural Sciences and Engineering Research Council of Canada (NSERC) grant (grant number ALLRP 585256-2023).

AI Usage Statement

The author used the large language model (LLM) Claude Opus 5.5 in the research leading up to the writing of this article, between September and November 2026. It was used for proof-reading the text and theoretical results of this manuscript, for code generation, optimization and debugging, and more generally as a conversational agent for testing intuitions and exchanging proof ideas. No text or data directly output by the LLM was included in the manuscript. Every conclusion presented in this work that was inspired by an output of the LLM was thoroughly validated and edited by the author.

References

  1. [1]A. H. Baker, E. R. Jessup, and T. V. Kolev. A simple strategy for varying the restart parameter in GMRES(m). Journal of Computational and Applied Mathematics, 230(2):751–761, Aug. 2009.
  2. [2]A. H. Baker, E. R. Jessup, and T. Manteuffel. A technique for accelerating the convergence of restarted GMRES. SIAM Journal on Matrix Analysis and Applications, 26(4):962–984, Jan. 2005.DOI
  3. [3]M. Brand. Fast low-rank modifications of the thin singular value decomposition. Linear Algebra and its Applications, 415(1):20–30, May 2006.DOI
  4. [4]C. Brezinski, M. Redivo-Zaglia, and Y. Saad. Shanks sequence transformations and anderson acceleration. SIAM Review, 60(3):646–669, Jan. 2018.DOI
  5. [5]P. N. Brown and A. C. Hindmarsh. Matrix-free methods for stiff systems of ODE’s. SIAM Journal on Numerical Analysis, 23(3):610–638, 1986.DOI
  6. [6]K. Carlberg, V. Forstall, and R. Tuminaro. Krylov-subspace recycling via the POD-augmented conjugate-gradient method. SIAM Journal on Matrix Analysis and Applications, 37(3):1304–1336, Jan. 2016.arxiv.org/abs/1512.05820
  7. [7]A. T. Chronopoulos. A Class of Parallel Iterative Methods Implemented on Multiprocessors. Ph.d., University of Illinois at Urbana-Champaign, Illinois, 1987.
  8. [8]A. T. Chronopoulos. s-step iterative methods for (non)symmetric (in)definite linear systems. SIAM Journal on Numerical Analysis, 28(6):1776–1789, Dec. 1991.
  9. [9]A. T. Chronopoulos and S. K. Kim. s-step Orthomin and GMRES implemented on parallel computers. (arXiv:2001.04886), Jan. 2020. arXiv:2001.04886 [math.NA].arxiv.org/abs/2001.04886
  10. [10]E. de Sturler. Truncation strategies for optimal krylov subspace methods. SIAM Journal on Numerical Analysis, 36(3):864–889, Jan. 1999.
  11. [11]G. B. Diaz Cortes, C. Vuik, and J. D. Jansen. On POD-based deflation vectors for DPCG applied to porous media problems. Journal of Computational and Applied Mathematics, 330:193–213, Mar. 2018.DOI
  12. [12]G. B. Diaz Cortés, C. Vuik, and J.-D. Jansen. Accelerating the solution of linear systems appearing in two-phase reservoir simulation by the use of POD-based deflation methods. Computational Geosciences, 25(5):1621–1645, Oct. 2021.DOI
  13. [13]C. Eckart and G. Young. The approximation of one matrix by another of lower rank. 1(3):211–218, 1936.DOI
  14. [14]M. Eiermann and O. G. Ernst. Geometric aspects of the theory of krylov subspace methods. Acta Numerica, 10:251–312, May 2001.DOI
  15. [15]M. Eiermann, O. G. Ernst, and O. Schneider. Analysis of acceleration strategies for restarted minimal residual methods. Journal of Computational and Applied Mathematics, 123(1):261–292, Nov. 2000.DOI
  16. [16]Y. A. Erlangga and R. Nabben. Deflation and balancing preconditioners for krylov subspace methods applied to nonsymmetric matrices. SIAM Journal on Matrix Analysis and Applications, 30(2):684–699, Jan. 2008.DOI
  17. [17]J. Frank and C. Vuik. On the construction of deflation-based preconditioners. SIAM Journal on Scientific Computing, 23(2):442–462, Jan. 2001.
  18. [18]A. Gaul, M. H. Gutknecht, J. Liesen, and R. Nabben. A framework for deflated and augmented krylov subspace methods. SIAM Journal on Matrix Analysis and Applications, 34(2):495–518, Jan. 2013.
  19. [19]D. S. Grundvig and M. Heinkenschloss. Line-search based optimization using function approximations with tunable accuracy. Optimization Methods and Software, 0(0):1–32, Dec. 2024.DOI
  20. [20]J. E. Hicken and D. W. Zingg. A simplified and flexible variant of GCROT for solving nonsymmetric linear systems. SIAM Journal on Scientific Computing, 32(3):1672–1694, Jan. 2010.DOI
  21. [21]K. Kahl and H. Rittich. The deflated conjugate gradient method: Convergence, perturbation and accuracy. Linear Algebra and its Applications, 515:111–129, Feb. 2017.arxiv.org/abs/1209.1963
  22. [22]P. Kerfriden, P. Gosselet, S. Adhikari, and S. P. A. Bordas. Bridging proper orthogonal decomposition methods and augmented newton–krylov algorithms: An adaptive model order reduction for highly non-linear mechanical problems. Computer Methods in Applied Mechanics and Engineering, 200(5):850–866, Jan. 2011.
  23. [23]A. Kopaničáková, Y. Lee, and G. E. Karniadakis. Leveraging operator learning to accelerate convergence of the preconditioned conjugate gradient method. Machine Learning for Computational Science and Engineering, 1(2):39, Nov. 2025.
  24. [24]Y. Li, L. T. Zikatanov, and C. Zuo. Reduced krylov basis methods for parametric partial differential equations. SIAM Journal on Numerical Analysis, 63(2):976–999, Apr. 2025.arxiv.org/abs/2405.07139
  25. [25]R. B. Morgan. A restarted GMRES method augmented with eigenvectors. SIAM Journal on Matrix Analysis and Applications, 16(4):1154–1171, Oct. 1995.DOI
  26. [26]R. B. Morgan. GMRES with deflated restarting. SIAM Journal on Scientific Computing, 24(1):20–37, Jan. 2002.DOI
  27. [27]R. Nabben and C. Vuik. A comparison of deflation and the balancing preconditioner. SIAM Journal on Scientific Computing, 27(5):1742–1759, Jan. 2006.DOI
  28. [28]C. C. Paige and M. A. Saunders. Solution of sparse indefinite systems of linear equations. SIAM Journal on Numerical Analysis, 12(4):617–629, 1975.DOI
  29. [29]M. L. Parks, E. de Sturler, G. Mackey, D. D. Johnson, and S. Maiti. Recycling krylov subspaces for sequences of linear systems. SIAM Journal on Scientific Computing, 28(5):1651–1674, Jan. 2006.
  30. [30]A. Quarteroni, A. Manzoni, and F. Negri. Reduced Basis Methods for Partial Differential Equations, volume 92 of UNITEXT. Springer International Publishing, Cham, 2016.DOI
  31. [31]Y. Saad. Analysis of augmented krylov subspace methods. SIAM Journal on Matrix Analysis and Applications, 18(2):435–449, Apr. 1997.
  32. [32]Y. Saad. Iterative Methods for Sparse Linear Systems. Other Titles in Applied Mathematics. Society for Industrial and Applied Mathematics, Jan. 2003.DOI
  33. [33]Y. Saad and M. H. Schultz. GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal on Scientific and Statistical Computing, 7(3):856–869, 1986.DOI
  34. [34]Y. Saad, M. Young, J. Erhel, and F. Guyomarc’h. A deflated version of the conjugate gradient algorithm. SIAM Journal on Scientific Computing, 21(5):1909–1926, Jan. 2000.DOI
  35. [35]H. Shokri Kaveh, M. Hajarian, and A. T. Chronopoulos. On the construction of efficient variable s-step methods for solving linear systems with applications in cyber-physical systems. International Journal of Systems Science, 0(0):1–19, Aug. 2026.DOI
  36. [36]K. M. Soodhalter, E. de Sturler, and M. E. Kilmer. A survey of subspace recycling iterative methods. GAMM-Mitteilungen, 43(4):e202000016, 2020.arxiv.org/abs/2001.10347
  37. [37]K. Svanberg. The method of moving asymptotes—a new method for structural optimization. International Journal for Numerical Methods in Engineering, 24(2):359–373, 1987.DOI
  38. [38]R. Vallot, F. d. Vuyst, T. Dairay, and M. Mougeot. Learning features from newton’s algorithm: a way to accelerate nonlinear parametrized PDE solvers. (arXiv:2607.28036), 2026. arXiv:2607.28036 [cs.LG].arxiv.org/abs/2607.28036
  39. [39]J. Vierendeels, L. Lanoye, J. Degroote, and P. Verdonck. Implicit coupling of partitioned fluid–structure interaction problems with reduced order models. Computers & Structures, 85(11):970–976, 2007.DOI
  40. [40]P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, Ï. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Pertold, R. C. Cimrman, I. Henriksen, E. A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261–272, 2020.
  41. [41]T. Wen and M. J. Zahr. A globally convergent method to accelerate large-scale optimization using on-the-fly model hyperreduction: Application to shape optimization. Journal of Computational Physics, 484:112082, 2023.DOI
  42. [42]M. Xiao, J. Ma, D. Lu, B. Raghavan, and W. Zhang. Stress-constrained topology optimization using approximate reanalysis with on-the-fly reduced order modeling. Advanced Modeling and Simulation in Engineering Sciences, 9(1), 2022.DOI
  43. [43]M. Yano, T. Huang, and M. J. Zahr. A globally convergent method to accelerate topology optimization using on-the-fly model reduction. Computer Methods in Applied Mechanics and Engineering, 375, 2021.DOI

Paper details

vlnc:W_4cyx7aa5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude Opus 5.5

View statement
Looking for related papers…
Contents