Definition of 'iteration' for Krylov subspace solvers

[Slaedr]

The issue is the definition of iteration in polynomial-based linear solvers including Krylov subspace methods. We can use the number of SpMVs, or the increase in the dimension of the Krylov subspace used to search for the solution, or perhaps something else.

For BiCG it's very clear that the dimension of the Krylov subspace is increased by only 1 per 2 SpMVs. For CGS and BiCGSTab it's not so clear, mainly because the whole concept of basis vector is not very relevant though they are loosely based on BiCG. They are defined in terms of polynomials - having the residual be r_0 times some polynomial of A, rather than explicitly looking for the solution in some subspace by orthogonalizing the residual w.r.t. some (other) subspace. The recursion for the polynomials is inspired by the BiCG Krylov subspace. Overall it's difficult to talk about CGS and BiCGStab in terms of basis vectors, so in this sense I see no clear reason to define 'iteration' one way or another.

In CGS and BiCGSTab, if one looks at the degree of the polynomial which defines the residual and solution, the degree is increased by two per iteration (where each iteration consists of 2 SpMVs). So perhaps it makes sense to count one SpMV as one iteration. But, it's interesting to note that similar to BiCG, BiCGStab also converges in at most n iterations according to Van der Vorst, where n is the dimension of the problem and 'iteration' is 2 SpMVs. Van der Vorst himself calls it one iteration for two SpMVs.

[pratikvn]

The definition of an iteration for fixed point methods is the number of times it updates its iterate, x in x_{n+1} = F(x_n) I think going by SpMVs would not be correct. For memory and other performance estimation reasons, I think the number of SpMVs can be used as a multiplier to uniformize the comparisons, but in the algorithm itself and logging the iterations, it would be best to stick to the number of updates in the solution vector. So, for our algorithms now:

Solver	Overall number of solution vector updates	Iteration count	SpMV (with sys-mat) multiplier	Cost (only considering sys-mat SpMVs)
CG	N	N	1	N
BiCGSTAB	N	N	2	2N
BiCG	N	N	2	2N
CGS	N	N	2	2N
IDR	s*N	N	2	2sN
GMRES	N/r	N	1 + 1/r	N + N/r

We are slightly inconsistent only for GMRES as num_updates*multiplier ≠ cost. But this looks like an addition/modification from our end.

[Slaedr]

That actually makes a lot of sense. I agree that SpMVs are not always the most conceptually appropriate counting metric.

However, pretty much no one counts GMRES iterations as restart cycles. The counter-argument against counting GMRES like what you say is that we could update the solution every iteration within the restart cycle too. In fact we do that when the solver terminates in the middle of a restart cycle. Just for efficiency, we don't do that all the time. To me the natural definition of GMRES iteration happens to correspond to one per SpMV in this case. Also, what would "iteration" be for un-restarted GMRES under your definition? On the other hand, the argument for your way of counting is that a restart is a smallest cycle which has the same cost every cycle - the usual conception of GMRES iteration has a different cost for each iteration.

[upsj]

Okay, trying to come to a consensus here:

(F)CG has 1 iteration for loop iteration
GMRES has 1 iteration per loop iteration (d iterations for a full restart cycle)
BiCG has 1 iteration per loop iteration
CGS has 1 iteration per loop iteration (2 SpMVs per iteration)
IDR has 1 iteration per loop iteration (s+1 SpMVs per iteration)
BiCGSTAB has 2 iterations per loop iteration (i.e. half-iterations)

How does that sound? Except for BiCGSTAB, this matches exactly with our mathematical understanding of iterations. Not sure about CGS, since there we could also count halt-iterations.

[Slaedr]

That sounds reasonable. But I would make CGS match BicGStab. They're quite analogous. Both add two polynomial degrees per loop iteration.

[pratikvn]

Yes, that sounds reasonable.

[upsj]

Unfortunately, BiCGSTAB without half-iterations can be unstable, so we will probably need to leave it as-is.