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ᵢ, vⱼ⟩ = 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ₖ, vₖ⟩ = 1, and there it is: the divisor at step k is

δₖ = ⟨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.

Both halves of that go the opposite way to the obvious guess, so the sweep is worth walking. More steps means more opportunities for a divisor to vanish, which suggests the trouble should grow with the size. It shrinks.

The rate falls by half and the incurable cases very nearly vanish. Across n = 4, 5, 6, 7 and 8 the serious breakdowns are 663, 532, 414, 337 and 333 of four thousand — 16.6%, 13.3%, 10.3%, 8.4% and 8.3% — while the count that no look-ahead can repair goes 44, 8, 1, 0, 1.

And the share a block of two clears rises with the size rather than holding: 87%, 93%, 96%, 96% and 98% of the serious cases across those five sizes. So the remedy gets better exactly as the problem gets rarer, which is the opposite of the shape a reader would brace for and is worth saying plainly: the two-by-two look-ahead is close to sufficient at every size tested and is furthest from sufficient on the smallest matrices, where a direct method would be used anyway.

The mechanism is the one the counting suggests once it is turned around. A serious breakdown needs a coincidence between two vectors, and the larger the space the two vectors live in, the less likely a coincidence is — the extra steps supply more chances to fail and the extra dimensions make each chance less likely, and the second effect wins. On a 4×4 with small integer entries the coincidence is common because there is very little room; incurability at 44 in four thousand is a fact about tiny matrices rather than about the algorithm.

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 same question of what a threshold is measured against that the form that makes it affordable settles for a deflation test.

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₀. It is a free parameter with no principle behind it, which is the condition rank is a decision argues should be stated rather than defaulted. 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, and on a matrix an eigenvalue that arrives twice would call unremarkable.

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.

Two things that sentence leaves open are worth closing, because a residual is not an answer and a run that does not finish still returns something.

The forward error confirms the reading rather than complicating it. Where the method finishes it is 2 to 5·10⁻¹⁶ at every η, flat across five decades, and it is measured against an LU solve rather than inferred from the residual. That agreement is not automatic — a small residual is not a small error is the essay about when it fails — and it holds here for a reason worth stating: κ(A) = 2.26. On a well-conditioned matrix the gap between residual and error has nothing to open into, so the control is trustworthy on this family and would not be on a harder one.

And past the cliff there is nothing to salvage. The natural repair for a run that misses its tolerance is to keep the best iterate rather than the last, and the best-residual column says that does not help: 0.126 at η = 10⁻⁹, 0.271 at 10⁻¹⁰, with forward errors of 4.1 and 9.1. The answer is four hundred and nine hundred per cent wrong at every step of the run, not merely at the one the method stopped on. There is no moment in eighty iterations at which the method knew the answer.

The transition is also not quite a cliff, which is the one thing the residual sweep could not show. At η = 10⁻⁸ there is a decade-wide band where the method limps rather than fails — nine digits instead of sixteen, in eighty steps instead of twelve. Either side of that band the outcome is sixteen digits or none.

assertThereIsNoGoodIterateToSalvage measures both halves, and asserts the conditioning too, since the whole reading depends on it.

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 — which is exactly the shape the residual the method reports is about, arriving in a different method.

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, which is a stopping test a tolerance that reads its own residual would call unearned. 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 — the arrangement an orthogonalisation nobody calls one prices — 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 — the kind of input a bound that is proved insists a claim be shown, 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.