In this paper
AbstractIntroductionPreliminariesProjection Methods for Linear SystemsAugmented Krylov MethodsOn-the-Fly Reduced BasisTheoretical FrameworkMinimal Residual Method on the Reduced SubspaceRelations to Known MethodsError AnalysisNumerical ExperimentsComparison to Other Solvers2D Convection-Diffusion ProblemComparison of the Reduced Basis Selection RulesThe Diffusion-Dominated CaseThe Advection-Dominated CaseConclusionAcknowledgementsConflict of InterestFundingAI Usage StatementReferencesWorksMathematics
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 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 for dense matrices, or 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(, 1) and -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 , with nonsingular and have the solution . Starting from an initial guess , the core idea of projection methods is to look for an approximate solution of the form , with the additional property , where , are -dimensional subspaces and 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 , are orthonormal bases of and respectively, the two conditions below must be satisfied:
In general, for invertible, it is not guaranteed that the projected system even has a unique solution. Very generic hypotheses like can be considered, but they are usually not very informative in practical cases. Within Petrov-Galerkin methods, the choice yields most methods used in practice [18].
Setting , or , yields Galerkin projection methods. The approximate solution satisfies the analog of the projected system (1) with ,
This class of methods is especially adapted for the case 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
the minimization of the -norm error. Another common choice is setting , or . The Petrov-Galerkin system (1) becomes
It is easy to recognize the normal equations, which are equivalent to solving the minimization problem
This is why those methods are generally referred to as minimal residual projection methods. Notice the equivalence with minimizing the error in the -norm, which makes this norm (and the -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 ,
This choice is particularly useful because the inverse of the matrix can be expressed as a polynomial in , , of degree at most [32]. A basis of the space of polynomials of degree at most would then be able to represent exactly the action of by computing only powers of (or even, only matvecs). Indeed, the matrix , basis of , has columns of the form with . They form a basis of the space of degree polynomials in . For some ,
By setting to be the coefficients of in the basis , , the exact correction needed to reach the solution from the starting point . Krylov methods are built upon this principle, by constructing iteratively an orthonormal basis for 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 -image of the current Krylov space, i.e., that the next coefficient will belong to the next power of . Numerically, convergence in or 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 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 and for the BiCG method.
Augmented Krylov Methods
The methods are based on a pattern of outer iterations or cycles (index ) and inner iterations (index ). A first group of augmented Krylov methods are projection methods where the search space has the form , 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(), which is restarted every 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 , which effectively reduces the oscillatory behaviour appearing in the convergence of GMRES(). 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 , 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 -th cycle, in which a Krylov subspace is constructed while maintaining orthogonality to additional vectors.
Another approach suggests that the operator of the Krylov subspace changes. Subspaces of the form are considered. This means that between each cycle, the augmented basis is updated (e.g., using deflation vectors), but also the projector , 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 (-th cycle)
, ,
, s.t.
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(), which simply keeps the most recent corrections as the augmentation vectors, like LGMRES would, but also projects the operator, something absent from LGMRES. Algorithm 2 presents the -th cycle of a GCRO-like algorithm, which uses augmentation vectors. Note that the projected operator makes it so that all Arnoldi vectors are orthogonal to .
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 (-th cycle)
,
, ,
,
, s.t.
On-the-Fly Reduced Basis
The on-the-fly framework relies on the collection of so-called snapshots of a vector quantity that is computed at each iteration of an iterative process, which are stored in the columns of a snapshot matrix , assumed to be full-rank. We note the number of snapshots. Often, the snapshot matrix can also be centered, denoted , by subtracting the mean of all snapshots from each column. Notice that this reduces the rank of the matrix to . We consider a concrete application case. In a nonlinear solver, if a linear system is solved at iterations , then at iteration , the solution space of the system is restricted to either the full span of the snapshots, , or to a subspace . In the second case, the search space is further reduced from dimension to dimension . Suppose that is spanned by an orthonormal basis, composed of the columns of a matrix . The solution can then be written as . There are multiple ways to determine the coefficients of the reduced solution, for instance residual minimization or Galerkin projection. In the case where there is no truncation, i.e., , 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 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., and , the SVD is often used to determine the best low-rank approximation of and determine its range. Indeed, for , the basis matrix can be selected as ( will be used to denote the restriction of a matrix to its first columns), since they are associated to the largest singular values of . can be chosen dynamically by ensuring a certain ratio of energy is conserved, like taking the smallest such that
The classical way to find the reduced coefficients in the POD framework is by using a Galerkin projection, i.e., by solving the system
which ensures the residual orthogonality condition .
When updating the snapshot matrix, the SVD has to be recomputed to take into account the new snapshots. Since the two operations done to 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 , and at a lower cost, especially for larger 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
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 will be used to denote a zero-padded vector . We propose a variant of LGMRES(, ) named GMRES-RB(, , , ). This method will run regular GMRES iterations, producing intermediate iterates
where is the Krylov subspace matrix at iteration and is the correction in Krylov coordinates. Initially, a snapshot matrix will be made with the zero-padded correction vectors, , from which the final correction is subtracted. With an SVD , the principal left singular vectors are extracted, by using the criterion that of the energy is captured. Because of the subtraction by , 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 , which effectively contains the total correction of the GMRES cycle and a subspace spanning significant corrections. Then, the inner corrections associated to the inner Arnoldi iterations from , 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 , which can be set to if no threshold needs to be imposed. The next cycle of Algorithm 1 is started with the resulting reduced basis . A pseudocode description is available in Algorithm 3.
Algorithm 3 GMRES-RB()
given
Do GMRES iterations, produces Krylov basis matrix and corrections
Choose the smallest such that captures of the energy
while and do
Apply Algorithm 1 with augmentation vectors and initial data
for do
Obtain the -th partial correction:
where
end for
Choose the smallest such that captures of the energy
end while
In practice, the partial residual minimization problems can be solved more efficiently by using directly restrictions of . 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 associated to .
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 originate from cycle ; this is one of the main differences with LGMRES and GCROT(), where the augmentation vectors are the final corrections from the 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() 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:
GMRES-RB-O(, , ), which keeps the last correction and the oldest snapshots in ;
GMRES-RB-L(, , ), which keeps the last correction and the latest snapshots in ;
GMRES-RB-C(, , , , ), which compresses the cumulative history of retained modes with the energy criterion, weighted by ;
GCRO-RB(, , , ), 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 to of are , precisely the history that we want to preserve. We define
where is the top-left, square submatrix of , and is a zero matrix with an identity matrix in the bottom. Its columns are the coordinates of in the basis, weighted by their original energy. We can consider the following augmented snapshot matrix for the SVD,
Notice that information that is allowed to traverse multiple cycles will decrease geometrically with rate .
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 directly. However, since the matrix does not have orthonormal columns, doing the SVD on is not equivalent, up to a rotation, to doing it on . Experimentally, it was noticed that doing the SVD on 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 () and , the method would coincide in exact arithmetic with LGMRES(, 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
which helps to alleviate slow, alternating patterns in the corrections [2]. On the contrary, when the energy criterion does not truncate anything ( and ), the method is equivalent to -ORTHOMIN(1), in exact arithmetic.
-ORTHOMIN() is an -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 -step methods to dynamically chosen parameter, to improve convergence [35]. Within the -th cycle, -ORTHOMIN() produces the iterate and the residual , by residual minimization over the affine space . Then, a basis of is computed, which is orthogonalized against the previous bases , resulting in the new basis . is set to be a basis of . It acts as a batch Krylov method, each iteration using a correction in an -dimensional Krylov space. The special case -ORTHOMIN(1) will be detailed in Algorithm 4.
Line 4 minimizes the residual over the correction search space . However, if we consider the 's to be augmentation spaces, we would be interested in the minimization over . We can show that these two spaces yield the same solution.
Algorithm 4 -ORTHOMIN(1)
, ,
while and do
-orthogonalize against , yields
end while
Lemma 3.1. For and defined in Algorithm 4,
Proof. Consider the problem
yielding the -ORTHOMIN(1) residual . If is the orthogonal projector on , we can show that . Indeed,
However, by Petrov-Galerkin orthogonality, so the first term is 0. Moreover, since is -orthogonal to , and
the second term is also 0. Consequently, the residual also satisfies the minimal residual problem with orthogonality constraint on , since it is orthogonal to . Moreover, since the orthogonalization at line 8 gives , then . By uniqueness of the minimizer, the statement of the lemma holds.
This makes it clear that since , by identifying , we find that -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 are equivalently obtained by -orthogonalization of against , meaning the two algorithms are actually the same in exact arithmetic.
Lemma 3.2. Assume that has full column rank for any cycle of GMRES-RB(, , 0, ) and -ORTHOMIN(1). Then, and 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 , the same as in -ORTHOMIN(1), so . Also at the end of the GMRES iterations in exact arithmetic, the final residual would be the same as for -ORTHOMIN(1) since no restart happened yet, meaning .
During cycle , assume the induction hypotheses and . The GMRES-RB algorithm minimizes over the same space as -ORTHOMIN(1):
The first equality holds by the induction hypothesis, and Lemma 3.1 tells us that the space on the right is the -ORTHOMIN(1) space. Thus the residuals and are equal.
The intermediate corrections problem, given by,
can be rewritten as
Thus, the intermediate correction can be written as . For a fixed , the solution in is given by the normal equations
where denotes the Moore-Penrose pseudo-inverse for matrices with full column rank. Since is a subspace of , and , the first term is 0. For the optimal , the correction is
which yields the following equalities, provided no breakdown happens:
Notice that is the -orthogonal projector onto , meaning that spans the Krylov subspace , from which components of in the -inner product have been removed. For -ORTHOMIN(1), the updated subspace would be equal by using the induction hypothesis (notice that the projector is independent of the basis chosen)
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 method coincides, in exact arithmetic, with -ORTHOMIN(1), i.e., for .
Proof. Direct consequence of Lemma 3.2. The shift by 1 comes from the fact that the iterate of the GMRES warmup phase is , 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 is symmetric, the method matches MINRES in exact arithmetic.
Corollary 3.1. Let and be symmetric and skew-symmetric matrices respectively. Suppose , or . Moreover, assume that for some , is definite. Then, in exact arithmetic, GMRES and GMRES-RB produce the same iterates if they start from the same initial point . More precisely, for .
Proof. Theorem 5.5 and Corollary 5.1 of Chronopoulos [8] yield the result, because of an equivalence between -ORTHOMIN(1) and -GCR for some matrices, and then an equivalence between -GCR and full GCR when 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 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 and where is symmetric, GMRES-RB(2,2,0,) transfers two vectors in its reduced basis to the next cycle, meaning 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() is equivalent to GCROT(), where only the final correction of the last cycle is kept. In a sense, GCROT() is really the deflated analog of LGMRES(); 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 -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
where is the residual at the beginning of the warmup phase.
Proof. After the warmup phase, . Also, . Consequently, the first vectors of , which span are all in . The last columns are the columns of , meaning that the whole is contained in . The base case is satisfied; we assume the strong induction hypothesis
for . By construction of the augmentation basis in Algorithm 3,
Following the construction of in Algorithm 1,
However, , since
with and the second term being in . Thus, . To conclude,
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 is approximated in the augmented subspace with respect to the -inner product.
Proposition 3.2. For , let be the full GMRES error, and be the corresponding GMRES-RB error. They satisfy the following identity:
where is the orthogonal projector on w.r.t. the -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 .
Let be the exact solution to . We know that where . The residual satisfies
Then, let . We have that and by Lemma 3.3
Then, we can additively shift the problem by ,
The second term in the sum is in because of the inclusion in Lemma 3.3. Because , the Pythagorean theorem gives
By converting everything in terms of the error,
and the last term is given by the orthogonal projector onto for the -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.
represents the starting point at beginning of cycle . 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 -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() from SciPy 1.15.0 [40] will be used. This implementation of GCROT() 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() will also be taken from SciPy. Also, the choice 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]
for multiple values. The discretized operator is obtained from a centered finite difference stencil on the unit square, with . The boundary conditions are homogeneous Dirichlet conditions. The initial value of the solver will be set to .
For small , the symmetric part of the discretized matrix is dominant with respect to the skew-symmetric part, and large 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 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 values and their associated ratio vary.
| 0 | 0 |
| 1 | 0.003817 |
| 41 | 0.1565 |
| 1681 | 6.417 |
| 107901 | 411.9 |
Table 1. Ratio of the skew-symmetric part energy to symmetric part energy for multiple values of the advection coefficient .
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, . For the methods relying on an energy criterion (GMRES-RB and GMRES-RB-C), this will be enforced by setting and , to keep the total correction and singular vectors. The basis size will be independent of , 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 . Moreover, we will validate that setting and indeed match the performance of full GMRES and LGMRES(, 1), by choosing , a pure Laplace problem, which is SPD. Figure 1 and Figure 2 show the convergence of the relative residual norm for all variants at for , and for .

Figure 1. Comparison between the different variants of GMRES-RB at fixed budget on the Laplacian () problem, for .

Figure 2. Comparison between the different variants of GMRES-RB at fixed budget on the Laplacian () problem, for .
First, we notice that in both cases, full GMRES and LGMRES(,1) are exactly or almost exactly replicated by the budgets and , 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 , 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 , 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 -th column of , in the recycled part of the basis, i.e., . 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 , 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 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.
| 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.88 | 0.89 |
Table 2. Component of the leading POD modes of GMRES-RB-C in the recycled space (mean over modes, median over cycles), for , .
In the 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 of the 30 available snapshots (or for GMRES-RB-C), required only a handful more matvecs than GMRES needed to reach the same tolerance. In particular, for GMRES-RB-C, 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 , 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 , which does not reflect the convergence behaviour observed in Figure 1, which is faster at any .
| Kept | |||||||||
| Oldest | 0.22 | 0.090 | 0.042 | 0.025 | 0.013 | 0.0072 | 0.0036 | 0.0018 | 0.00073 |
| Latest | 0.22 | 0.081 | 0.035 | 0.018 | 0.0091 | 0.0061 | 0.0040 | 0.0023 | 0.00094 |
| Energy | 0.22 | 0.053 | 0.0092 | 0.0045 | 0.0017 | 0.0011 | 0.00074 | 0.00050 | 0.00028 |
Table 3. Projection error of the full space on space spanned by the oldest/latest snapshots and leading POD modes, for and .
This leads to the second hypothesis, which is that the oldest snapshots span the Krylov space , 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 or 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.
| 2 | 0 | 26.8 | |||||||
| 3 | 0 | 1.8 | 48.0 | ||||||
| 4 | 0 | 0.1 | 10.0 | 69.6 | |||||
| 5 | 0 | 0 | 0.7 | 19.9 | 79.1 | ||||
| 6 | 0 | 0 | 0 | 1.0 | 26.3 | 81.7 | |||
| 7 | 0 | 0 | 0 | 0 | 0.8 | 20.8 | 79.5 | ||
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 10.9 | 68.7 | |
| 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 48.0 |
Table 4. Median principal angles (degrees) between the augmentation spaces built by GMRES-RB and GMRES-RB-O at budget , for , .
| 2 | 0 | 31.7 | |||||||
| 3 | 0 | 5.3 | 62.9 | ||||||
| 4 | 0 | 0.7 | 26.5 | 84.3 | |||||
| 5 | 0 | 0 | 4.0 | 50.1 | 86.8 | ||||
| 6 | 0 | 0 | 0.1 | 9.1 | 58.5 | 88.3 | |||
| 7 | 0 | 0 | 0 | 0 | 8.4 | 61.1 | 88.0 | ||
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 47.9 | 86.8 | |
| 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 82.2 |
Table 5. Median principal angles (degrees) between the augmentation spaces built by GMRES-RB and GMRES-RB-L at budget , for , .
The Diffusion-Dominated Case
The cases where and will be studied. For these values, the operator is still diffusion-dominated. Figure 3 shows convergence curves for and Figure 4 for when (resp. Figure 5 and Figure 6 in the case ). We note that since is equivalent to LGMRES for GMRES-RB and GMRES-RB-C, they will be excluded from the figures if is present.

Figure 3. Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem () with a fixed budget , and .

Figure 4. Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem () with a fixed budget , and .

Figure 5. Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem () with a fixed budget , and .

Figure 6. Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem () with a fixed budget , and .
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 , , the behaviour in is nonmonotonic. For multiple methods, notably GCRO-DR with harmonic vectors, GMRES-RB and GCRO-RB, performs significantly better than .
The plain GMRES-RB method is generally lagging behind every other algorithm at equal budget, except sometimes for LGMRES at higher and . This behaviour is slightly surprising, since in the case, GMRES-RB largely outperformed GCRO-RB at the same budget, but introducing even a relatively small amount of advection (, 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 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 , since in the case and , taking 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 and .
The Advection-Dominated Case
The case yields a ratio of approximately 6 between the skew-symmetric and symmetric parts. Figure 7 shows what happens at , and Figure 8 at . 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 ) the deflation methods at larger . Most of the time, it beats the tested GCROT methods. However, at small , 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 .

Figure 7. Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem () with a fixed budget , and .

Figure 8. Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem () with a fixed budget , and .
The last parameter value studied, , makes the problem largely dominated by advection, and the relative distance from to its skew-symmetric part is around 0.2%. Figure 9 and Figure 10 show the convergence behaviour at and 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.
| Method | ||||||
| GMRES-RB | 294 | 270 | 294 | 290 | 290 | 280 |
| GMRES-RB-C | 294 | 284 | 298 | 348 | 286 | 308 |
| GCRO-RB | 2692 | 318 | 520 | 404 | 332 | 238 |
| GCRO-DR harmonic | 1776 | 1776 | 1252 | 746 | 418 | 376 |
| GCRO-DR Ritz | 1720 | 1720 | 1084 | 548 | 252 | 242 |
| GCROT | 3163 | 439 | 1442 | 1241 | 1912 | 2135 |
| GCROT de Sturler | 3163 | 429 | 1148 | – | – | – |
| LGMRES | 296 | 322 | 274 | 290 | 288 | 266 |
Table 6. Number of matvecs required to reach convergence, , . The number in bold is the lowest in its column.
| Method | ||||||||
| GMRES-RB | 302 | 274 | 264 | 300 | 312 | 340 | 350 | 242 |
| GMRES-RB-C | 302 | 296 | 278 | 238 | 272 | 262 | 268 | 222 |
| GCRO-RB | 432 | 494 | 558 | 752 | 702 | 664 | 402 | 216 |
| GCRO-DR harmonic | 658 | 658 | 260 | 268 | 216 | 214 | 198 | 192 |
| GCRO-DR Ritz | 368 | 368 | 280 | 244 | 214 | 210 | 198 | 190 |
| GCROT | 465 | 965 | 1030 | 1212 | 1594 | 1205 | 297 | 398 |
| GCROT de Sturler | 465 | 941 | 870 | – | – | – | 297 | 398 |
| LGMRES | 302 | 326 | 312 | 300 | 300 | 300 | 300 | 300 |
Table 7. Number of matvecs required to reach convergence, , . The number in bold is the lowest in its column.

Figure 9. Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem () with a fixed budget , and .

Figure 10. Comparison between variants of GMRES-RB and other classical solvers on the convection-diffusion problem () with a fixed budget , and .
The global observation here is that for this problem setup, GMRES-RB starts to show some promise again. On larger budgets , GCRO-DR with Rayleigh–Ritz vectors starts picking up and it significantly reduces the number of matvecs required. For , GCRO-RB is also able to beat the deflation method by a few matvecs. However, for smaller budgets , 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 , 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 . The closest method to GMRES-RB is LGMRES for both 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 -step ORTHOMIN() 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 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 values made it behave poorly. Moreover, it would be interesting to relate the properties of 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(), 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]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]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]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]C. Brezinski, M. Redivo-Zaglia, and Y. Saad. Shanks sequence transformations and anderson acceleration. SIAM Review, 60(3):646–669, Jan. 2018.DOI
- [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]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]A. T. Chronopoulos. A Class of Parallel Iterative Methods Implemented on Multiprocessors. Ph.d., University of Illinois at Urbana-Champaign, Illinois, 1987.
- [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]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]E. de Sturler. Truncation strategies for optimal krylov subspace methods. SIAM Journal on Numerical Analysis, 36(3):864–889, Jan. 1999.
- [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]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]C. Eckart and G. Young. The approximation of one matrix by another of lower rank. 1(3):211–218, 1936.DOI
- [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]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]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]J. Frank and C. Vuik. On the construction of deflation-based preconditioners. SIAM Journal on Scientific Computing, 23(2):442–462, Jan. 2001.
- [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]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]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]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]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]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]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]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]R. B. Morgan. GMRES with deflated restarting. SIAM Journal on Scientific Computing, 24(1):20–37, Jan. 2002.DOI
- [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]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]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]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]Y. Saad. Analysis of augmented krylov subspace methods. SIAM Journal on Matrix Analysis and Applications, 18(2):435–449, Apr. 1997.
- [32]Y. Saad. Iterative Methods for Sparse Linear Systems. Other Titles in Applied Mathematics. Society for Industrial and Applied Mathematics, Jan. 2003.DOI
- [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]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]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]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]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]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]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]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]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]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]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