- The recycling of Sonneveld spaces: It is possible to cheaply restrict an arbitrary right-hand side into a small-dimensioned Sonneveld space of a former solution process of a linear system. This is beneficial for an iterative method because it is a well-known experience that a smaller dimension of the Sonneveld space leads to a faster convergence (superlinear convergence). An early IDR-type method which is based on this concept is called SRIDR(s).
- Short Representations: This is a concept for the memory-efficient storage of basis matrices of Krylov subspaces. The concept can be used to recycle information from large Arnoldi-type decompositions, leading to the methods SRCG and SR-BiCG. One successor of these methods is SR-PCR.
- A stabilization approach for short representations by iteratively orthogonalizing a right-hand-side w.r.t. small blocks of a basis matrix of a test space (which is used in SR-PCR).
- A short recursion for the conservation of orthogonality properties of a residual which is found by the use of a short recycling method. Usually the recycling of new decent directions on a large recycled space would require long recurrences. However, by using an IDR-type post iteration method one can replace these long recursions by short ones.

The concept of Short Recycling was first presented on 24th of November 2015 at TU Delft with the following slides: Presentation .

Figure 1: Exemplary convergence curves for SRIDR(10) and SRBiCG on

a 100x100 finte difference discretisation of a Poisson problem.

Figure 1: Exemplary convergence curves for SRIDR(10) and SRBiCG on

a 100x100 finte difference discretisation of a Poisson problem.

Fig. 1 shows the convergence behaviour
SRIDR(10) and SRBiCG for a Poisson problem. One can observe that
the recycling methods yield a faster convergence than their
predecessors IDR(10) and BiCG. The overhead due to the recycling is 6
extra DOT products for SRBiCG compared to BiCG per matrix-vector
product (#MV) during the first 40 iterations and an additional storage
for 40 column vectors of length 10000. For SRIDR(10) there is no
overhead at all, neither in computations nor in storage.

There are Matlab implementations for SRIDR(s) and SRBiCG : SolverPack .

The following figures give a first impression of the way how Mstab converges compared to IDRstab.

Figure 2: Redundant solution of central FD discretised PDEs. We observe that Mstab converges earlier than IDRstab.

---

Figure 3: Further test cases.

Figure 4: Comparative study of IDRstab vs. Mstab on a parametric test case.

---

Figure 5: Comparison of the termination behaviour of IDRstab and Mstab.

The spaces G and M are the last spaces before the respective methods terminate.

Figure 6 demonstrates once again for a small dimensioned test problem and uncorrelated (namely orthogonal) right-hand sides that Mstab terminates earlier than IDRstab. On the x-axis there are markers after which Mstab would terminate if there was no round-off. Proofs for these theoretical bounds exist! Besides, one could achieve that the earlier termination is even more early by just increasing s. For the example it was chosen s=5.

One can think of some applications where such a kind of recycling under changing A is potentially useful:

- In SQP active set methods the replacement of one constraint by another results in a rank-1 update.
- In several quasi-Newton methods such as Broyden and BFGS. With BFGS one is luckily in the situation that the two column vectors of the rank-2 update stem from a common Krylov subspace.

Figure 6: The termination behaviour of M(5)stab(2) on a small-dimensioned test problem.

back to main page: Back