The same zero, and nothing was found

The previous argument rested on one fact about the Arnoldi recurrence: the number it divides by is a norm. A norm is zero exactly when its vector is, so a zero divisor means the new direction was already in the space, which means the space is invariant, which means the answer is inside it. There is no other reading available.

Arnoldi has a cost, and it is the cost that made everything after it necessary. To orthogonalise against the whole existing basis it has to keep the whole existing basis: k vectors at step k, and k inner products, so the work and the storage both grow with the step number. On a symmetric matrix that cost disappears — the orthogonality relations collapse to three terms and Lanczos runs in constant memory — and on a nonsymmetric one it does not.

The two-sided Lanczos recurrence is what buys the short recurrence back. It costs one thing, and this essay is about what that thing costs.

What changes, which is two lines #

Instead of one sequence orthogonal to itself, build two sequences bi-orthogonal to each other: v₁, v₂, … from A and w₁, w₂, … from Aᵀ, with ⟨w_i, v_j⟩ = 0 whenever i ≠ j.

That is enough to force a three-term recurrence on a matrix with no symmetry at all, which is the prize, and the derivation is a page long. The scaling of the two sequences is free, so it is fixed by requiring ⟨w_k, v_k⟩ = 1, and there it is: the divisor at step k is

δ_k = ⟨w̃, ṽ⟩

where ṽ and w̃ are the two new directions before normalisation. It is not a norm. It is an inner product of two vectors from two different sequences, and such a thing is zero on a hyperplane — a set of codimension one, which both vectors can sit either side of without being small.

Three things can happen, and only the first two have counterparts in Arnoldi.

The recurrence completes. Nothing to say.

ṽ or w̃ is zero. One of the two Krylov spaces has closed. This is the lucky breakdown, with the same meaning it has in Arnoldi, and it is what most of the census above records.

δ is zero and neither vector is. Nothing has closed. No subspace is invariant, no Ritz value has converged, and the recurrence has no next term. This is the serious breakdown, and it is the reason BiCG and its descendants have the reputation they have.

How often, which is the question the textbooks decline #

The standard sentence is that a serious breakdown is a measure-zero event and therefore does not happen in practice. The first half is true. The second does not follow, and the reason is worth being blunt about: measure zero is a statement about the reals, and a great many matrices are not random reals.

An incidence matrix is integers. A stencil is small rationals. A graph Laplacian is integers. A transfer matrix in a lattice model, a Markov chain on a finite state space, an adjacency structure, a combinatorial relaxation — integers, all of them, and integers are exactly where a set of measure zero in the reals is a set of positive density.

So the census counts. Four thousand 5×5 matrices with entries drawn uniformly from −2 to 2, the recurrence started from e₁ on both sides and run to step n − 1:

• 532 serious breakdowns — 13.3 per cent;
• 495 of them cleared by a look-ahead block of length two;
• 29 needing a longer block;
• 8 that cannot be cleared at any block length at all.

On Gaussian matrices every one of those four numbers is zero, at any number of trials, which is what makes the usual sentence defensible and what makes it useless.

Why the integers are not a special case #

It is tempting to read the census as a curiosity about small integer matrices and stop there. Two things make that reading expensive.

The first is that the structured matrices which produce exact zeros are exactly the matrices large enough to need a short recurrence. Nobody reaches for BiCG on a dense 5×5 problem. They reach for it on a transfer matrix, a lattice operator, a discretised transport equation with integer stencil weights, a graph — and every one of those has entries drawn from a small set by construction rather than by accident.

The second is that a matrix does not have to be integral for its inner products to be. A stencil with weights ±1 and a starting vector that is a unit basis vector produce integer inner products for as many steps as the arithmetic is exact for, which on a sparse operator with small entries is a great many. The set the divisor is being drawn from is discrete long after the matrix has stopped looking discrete.

What a look-ahead step needs, which is one inner product #

The repair is called look-ahead and its idea is simple: if the 1×1 division cannot be done, do a 2×2 solve instead — take two steps of the recurrence at once and require only that the block of moments be nonsingular.

The block is

M = [ ⟨w̃, ṽ⟩ ⟨w̃, Aṽ⟩ ] [ ⟨Aᵀw̃, ṽ⟩ ⟨Aᵀw̃, Aṽ⟩ ]

and its top-left entry is zero, because that is what the breakdown is. The two off-diagonal entries are the same number, since ⟨Aᵀw̃, ṽ⟩ and ⟨w̃, Aṽ⟩ are the same inner product written twice. So

det M = −(w̃ᵀ A ṽ)²

exactly: never positive, and nonzero precisely when the single number w̃ᵀAṽ is. The whole question of whether a two-step look-ahead is available is one inner product, and the determinant it decides is minus a perfect square.

That identity is not in any statement of the method this collection could find, and it is checked here rather than asserted: on forty serious breakdowns found by search, the 2×2 determinant computed from its four entries and −(w̃ᵀAṽ)² computed from one inner product agree to 3·10⁻¹⁵ relative in the worst case.

And the ones that cannot be cleared #

Look-ahead of length j needs w̃ᵀAʲ⁻¹ṽ ≠ 0. If every one of those is zero — for every j at all — then no block of any size works, and the breakdown is incurable. The two Krylov spaces have become orthogonal in a way that no amount of looking ahead repairs.

Eight of the 532 were like that, which is 1.5 per cent of the serious breakdowns and 0.2 per cent of the matrices. Small, and not zero, and there is nothing to do about it except restart from a different pair of starting vectors — which changes the answer’s arithmetic and not its algebra, and is the same admission the next section is about.

The near miss, which is what actually happens #

Exact serious breakdowns need exact zeros. What a floating-point run meets is a δ that is small, and “small” here is the whole subject.

The family is built out of the one free choice the method makes and cannot justify. BiCG needs a second starting vector r̃₀ — the shadow vector — and every account of the method says the same thing about it: commonly r̃₀ = r₀. No reason is given because there is none to give. The answer does not depend on it and the arithmetic does.

Along a line r̃₀ = b + s·d there is a value s* at which the second divisor is exactly zero. It is found here by bisection on a sign change rather than assumed to exist, and the family is the shadow vector at distance η from it. The matrix does not change. The right-hand side does not change. The answer does not change. What changes is a choice the caller was told to make arbitrarily.

The steps run 12, 12, 12, 13, 17, 20, 24 — and then the method does not converge at all within eighty. On a twelve-dimensional problem.

That is worth stating carefully, because it is not the failure anybody expects. The answer is not damaged. At every stop where the method finishes, it finishes at a relative residual of about 10⁻¹⁶ — the same accuracy at η = 10⁻² and at η = 10⁻⁷. Nothing about the computed solution degrades.

What degrades is the property that made the method attractive in the first place. BiCG on an n×n problem is a direct method in exact arithmetic: the two Krylov spaces span everything after n steps and the residual is zero. Near the breakdown surface that guarantee is gone. Not weakened — gone.

And the observable does not move #

The control in that figure is the one worth repeating from the previous essay, because it is the same shape arriving in a different method.

The largest relative residual over the first n steps — the visible hump every BiCG plot has, the thing that gets described as the method’s characteristic erratic behaviour — is 0.279 at η = 10⁻² and 0.271 at η = 10⁻⁷. It is the same number across five decades of the hidden quantity.

So a caller watching the residual history sees a run that looks exactly like every other run, right up to the point where it fails to stop. The quantity that is falling by five orders of magnitude is δ, and δ is not something any solver reports.

Two failures that look the same from outside #

Put the two essays’ pictures beside each other and the point of the pair is visible in one sentence.

In the lucky case the divisor falls to 10⁻¹⁴, the method stops, and the residual is 10⁻¹⁶. In the serious case the divisor falls to 10⁻¹⁴, the method stops, and the residual is whatever it happened to be — which on the shadow family is around 0.27.

A monitoring routine that logs “divisor below tolerance, stopping” prints the same line in both cases. A caller who reads only that line cannot tell which happened. The two are distinguished by a quantity neither of them logs — whether ṽ and w̃ are themselves small — and it costs two norms to find out.

That is the cheapest lesson in this essay and it is the one worth acting on: a routine that detects a breakdown should record which kind it was, because the information is available at the moment of detection, costs nothing, and cannot be recovered afterwards from anything the method returns.

Why anybody puts up with this #

Because the alternative costs memory that does not exist.

GMRES on a nonsymmetric matrix stores every basis vector, so a thousand-step run on a million-unknown problem needs a thousand million-length vectors. Restarted GMRES bounds the storage and gives up the optimality — and, as this collection has already measured, restarting can stall outright on a matrix whose spectrum looks perfectly reasonable.

The two-sided recurrence stores three vectors. Whatever it costs, it costs that in a fixed amount of memory, and for a large enough problem “fixed” is the only column in the table that matters. Every method in the BiCG family — CGS, BiCGStab, QMR, TFQMR — is an attempt to keep the short recurrence and mitigate what it brings with it, and each of them mitigates a different part.

QMR is the most direct about it: it takes the same recurrence, admits that the residual is not being minimised, and minimises a quasi-residual instead — which smooths the history and, crucially, is where look-ahead was first made practical.

What the family says about the advice #

The shadow vector is chosen arbitrarily and the arbitrary choice decides whether the method terminates. That is an uncomfortable sentence, and the discomfort is the point of the measurement rather than a side effect of it.

It is not that r̃₀ = r₀ is a bad default. It is that there is no basis on which to call it a good one. The quantity it controls is invisible, the failure it can cause is a non-termination rather than a wrong answer, and the distance from the surface where the failure lives is not something a caller can compute without doing the work the method was supposed to save.

What practice does instead — and this is the honest resolution rather than a criticism — is treat the shadow vector as a resource to be re-drawn. If a run stalls, restart with a different r̃₀. The new run is a different arithmetic path to the same answer, so a stall on one and success on another is not a contradiction, and two runs that agree are two routes to a number in the sense this site means. It is a randomised remedy for a deterministic problem, and this collection has a whole field about what changes when a guarantee starts holding with a probability instead of holding.

What is symmetric about symmetry #

The comparison worth ending on is not between Arnoldi and the two-sided recurrence, it is between what each of them is allowed to assume.

On a symmetric matrix, Aᵀ is A, the two sequences are the same sequence, and δ becomes ⟨v, v⟩ — a norm again. Every ambiguity in this essay disappears at once, and the short recurrence and the unambiguous divisor come together rather than being separate gifts. That is not a coincidence: both of them are the same statement about A having an orthogonal eigenbasis.

This site has an essay saying that symmetry is worth more than precision, measured on the eigenvalue problem. Here is the same conclusion from a different direction and it is sharper: symmetry is worth the difference between a method that always terminates and a method that terminates unless a hidden inner product gets close to zero, in which case it may not terminate at all and will not say so.

The refusal #

The assertion behind this essay is fed a two-sided recurrence whose starting pair is not bi-orthogonal — ⟨w₁, v₁⟩ = 0 before any step has been taken.

It is the case a caller produces by choosing the shadow vector badly rather than arbitrarily, and it is the one where the two readings of a zero are hardest to keep apart: the divisor is zero, so a routine that treats a zero divisor as convergence reports that the method has finished, at step zero, with the initial guess as the answer and a residual equal to the whole right-hand side.

That is not a subtle failure and it is not a hypothetical one. It is what “treat the breakdown as convergence” means when the breakdown is the wrong kind, and refusing it is the difference between a method that stops and a method that answers.

What is next #

Both essays so far have been about a divisor. The next is about the same event in a method where the division is not the point at all — where the quantity that goes non-positive is the curvature of a quadratic, the method has nothing to divide by and nothing to find, and the direction it stopped on is the single most valuable object the iteration can produce.