The number that cannot rank them

A symmetric positive definite Toeplitz system has two solvers. Gaussian elimination treats it as a matrix and costs O(n³) operations. Levinson’s recursion treats it as the n numbers the matrix actually holds — the structure stated at its tightest — and costs O(n²). Both are backward stable, and a library reporting on either prints one number to say so.

That number is the normwise backward error, and the reading it invites is that it belongs to the algorithm. Run both solvers on the same system, compare the two figures, take the smaller one as the better method. The reading is so natural that it is rarely stated: a backward error is quoted the way an operation count is quoted, as a fact about a routine rather than about a run.

This essay does the comparison, on a family where every quantity in it can be computed and one of them is known exactly, and reports what each of the three candidate numbers turns out to be a property of. The family is the Kac–Murdock–Szegő matrix ρ^|i−j|, swept at eight values of ρ from 0.5 to 0.999 and at six sizes from 8 to 20 — forty-eight systems, ninety-six solves, and a condition number that runs from 7.47 to 3.95·10⁴ across them.

The reported number has a range of five and no direction #

Across all ninety-six measurements the normwise backward error lies between 1.16·10⁻¹⁷ and 5.73·10⁻¹⁷. The smallest is Levinson’s at n = 20, ρ = 0.9; the largest is elimination’s at n = 10, ρ = 0.995. The whole spread is a factor of 4.94, which is smaller than the gap between two consecutive representable numbers is large, and it does not move with anything. Over the same forty-eight systems the condition number moves by a factor of five thousand and the reported backward error moves by a factor of five, in no particular direction.

So the first question — which solver is smaller — has an answer at every point and the answer is a coin. Levinson’s is the smaller at twenty of the forty-eight, elimination’s at twenty-eight, and along the eight-point curve at each size the sign of the difference changes fourteen times in forty-two adjacent steps. Two curves that cross that often are not two curves.

The decisive check is not the ordering but the scale it is read off. Fix one point — n = 12, ρ = 0.99 — and run it with fifteen different right-hand sides. Levinson’s own normwise backward error then runs from 1.52·10⁻¹⁷ to 4.57·10⁻¹⁷, a factor of 3.01, on the same matrix with the same algorithm. The mean absolute difference between the two solvers at that point is 1.05·10⁻¹⁷ — about a third of the range one solver covers by itself when only the right-hand side changes.

That is the finding, stated at its plainest: the difference between the two algorithms is smaller than the variation in either one across right-hand sides. A number whose between-method spread sits inside its within-method spread is measuring the run and not the method. The ordering does have a faint tilt, and it is worth naming rather than hiding: at that same point Levinson’s is the larger at seventy-five of the ninety right-hand sides. But the quantity it is tilted by is 10⁻¹⁷, a caller sees one right-hand side rather than ninety, and nothing a caller could do differently depends on it.

The structured number separates them, and not in one direction #

The quantity the nearby problem of the wrong kind introduced is the smallest perturbation that is itself a symmetric Toeplitz matrix — a problem of the kind that was posed rather than a problem of any kind at all. It is a minimum-norm least-squares answer rather than a formula, it cannot be smaller than the normwise number, and on this family it is larger by three to seven orders of magnitude.

It also separates the two solvers, decisively, at almost every point. At n = 10, ρ = 0.98 Levinson’s structured backward error is 3.28·10⁻¹² and elimination’s is 3.20·10⁻¹⁴ — Levinson’s is 102.5 times elimination’s, which on any reading is a difference between two methods rather than between two roundings.

Then at n = 12, ρ = 0.8 Levinson’s is 2.85·10⁻¹⁴ and elimination’s is 4.61·10⁻¹³, so Levinson’s is one sixteenth of it. At n = 20, ρ = 0.9 it is one thirteenth. At n = 8, ρ = 0.999 it is 3.91 times larger again.

Across the forty-eight points Levinson’s structured backward error is the larger at twenty-eight of them and the smaller at twenty, and the sign of the difference changes twenty-two times in the forty-two adjacent steps — more often than the normwise ordering changes, not less. At n = 16 it changes five times in seven steps, which is to say the two curves alternate.

So the structured quantity does the thing the normwise one fails to do — it distinguishes the two solvers, by two orders where the reported number distinguishes them by nothing — and it still does not rank them. It separates without ordering. The size of the separation is real and the sign of it is a property of the point, and a reader handed one of these systems and told that Levinson’s structured backward error is a hundred times elimination’s has learned something true about that system and nothing about Levinson.

That is a specific and unusual failure. A noisy instrument gives a small answer in a random direction; this one gives a large answer in a random direction, which is worse, because the magnitude is what makes it look like a finding.

And the size trend is erratic in the same way #

The picture invites a second reading, and it is worth checking because it is the reading the earlier essay’s own table supports. The unconstrained perturbation has n² entries to spend on a residual that lives in n dimensions and the constrained one has n, so the gap between them should widen with size. The slider says so, and so does the caption under it.

Measured on this sweep it does not. The worst ratio of structured to normwise backward error over the whole family, at each size in turn, is

   n        8         10         12         16        18        20
ratio  9.48·10⁴   2.07·10⁷   2.48·10⁶   7.27·10³  3.48·10³  3.06·10⁶

which rises by two and a half decades from n = 8 to n = 10, falls by three and a half decades to n = 16, and climbs three decades again by n = 20. Nothing monotone survives that. The exponent somebody would fit to it is not a small number badly estimated; there is no exponent, because the sequence is not a trend.

The honest reason the two readings differ is the number of right-hand sides. The earlier essay’s table used fifteen at each size and fitted n^1.37; this sweep uses one, because the structured minimisation is a dense least-squares solve at every one of forty-eight points and fifteen of them is fifteen times that. Averaging fifteen recovers a smooth curve. Running one gives the sequence above, and the sequence above is what a caller gets, because a caller runs one system with one right-hand side and reads one number.

Both statements are true and they are about different objects. The growth with n is a property of the family and it is real. The number in front of any particular caller is a draw from a distribution whose spread across right-hand sides is wider than three decades of that growth, and no amount of correctness in the trend makes a single draw informative about it.

The forward error ranks them, at every size #

There is a third number and it is the one nobody has. The forward error is the distance from the computed answer to the true one, it is what a reader actually wants, and it requires the true one.

This family supplies it. The Kac–Murdock–Szegő matrix has a closed-form inverse, so the exact solution of every system in the sweep is written down rather than computed — an answer that is known rather than a second float computation standing in for one. That is why this family is used here and a random Toeplitz matrix is not.

At the hardest point of the family, ρ = 0.999, the two forward errors are

   n          Levinson      elimination    ratio
   8         1.95·10⁻¹³     9.93·10⁻¹⁴     1.97
  10         2.06·10⁻¹³     1.12·10⁻¹³     1.83
  12         2.28·10⁻¹³     1.30·10⁻¹³     1.75
  16         3.93·10⁻¹³     1.61·10⁻¹³     2.45
  18         2.56·10⁻¹³     1.02·10⁻¹³     2.51
  20         2.62·10⁻¹³     1.45·10⁻¹³     1.80

Six sizes, one direction, and a factor between 1.75 and 2.51. Levinson is further from the truth than elimination at every size, by an amount that does not swing by orders and does not change sign. That is what a measurement of an algorithm looks like, and it is the only one of the three numbers on this page that looks like one.

The reason it can be that is not subtle and is worth saying flatly. The two backward errors ask what perturbation of the problem would make the computed answer right, and the answer depends on the computed answer, on the residual, on the right-hand side and on the geometry of the perturbation set — four things, of which the algorithm is one. The forward error compares the computed answer with the truth and depends on the algorithm and the problem. It has fewer places to hide the thing being measured.

The obvious objection is that the forward error is not independent evidence, because the textbook relation says it is bounded by the condition number times the backward error and κ is the same for both solvers on the same system. Measured, the relation holds and the objection does not. At ρ = 0.999 the condition number runs from 1.53·10⁴ at n = 8 to 3.95·10⁴ at n = 20, and κ times the reported backward error exceeds the measured forward error at all twelve solves — by a factor between 1.52 and 5.00. So the product is right, and the bound is loose by rather more than the factor of two that separates the solvers.

That slack is where the ordering is lost. The bound would predict that whichever solver reports the larger backward error ends further from the truth, since κ multiplies both by the same amount. At n = 8 and n = 10 the reported number is Levinson’s smaller one — 1.93·10⁻¹⁷ against elimination’s 2.78·10⁻¹⁷ at n = 8 — and the forward error says Levinson is 1.97 times worse. At two of the six sizes the reported backward error orders the two solvers the wrong way round. It is not that the inequality fails; it is that the factor of five it has to spare is larger than the difference it would have to carry.

Which is available only because the answer is known #

The cost of the ranking is the whole of the catch. A forward error needs a true solution, and outside constructed families nobody has one — which is the reason three errors and one number exists as an essay: of the three quantities a reader would like, the one that is free is the one that answers a question nobody asked, and the one that answers the question is unavailable.

What a constructed ground truth looks like is worth seeing beside the sweep, because it makes clear how narrow the circumstance is.

That system is the same lesson in its extreme form: a reported backward error at the rounding level, sitting over an answer with no correct digits in it, and the only thing that makes the second sentence sayable is that the right-hand side was manufactured from a known solution rather than measured. The two situations are the same trick — build the problem backwards from the answer, or use a family whose inverse is written down — and neither is available to somebody with a matrix that arrived from an experiment.

So the recommendation this essay ends at cannot be report the forward error. It is closer to the reverse: the number that ranks the two solvers is the one that needs an answer nobody normally has, which is a fact about instruments rather than about Levinson, and it means the ranking has to be done once on a family where the truth is known and then relied on elsewhere. That is exactly how a reference implementation is used, and it is the collection’s habit of two routes to a number applied to a case where the second route is not merely the more expensive one but the differently informed one — the first route being the quantity a method can actually see, which is the residual and nothing beyond it.

Where the ranking stops being a ranking #

The six-of-six above is one right-hand side, and the same fifteen-seed check that undid the size trend has to be run against it.

At ρ = 0.999, across fifteen right-hand sides and six sizes, Levinson is further from the truth at 68 of 90 points, with a median ratio of 1.33 and a range from 0.23 to 11.4. At ρ = 0.99 it is 82 of 90. Those are tendencies rather than laws: the six-of-six on the swept right-hand side is real and it overstates how reliable the ordering is.

And the direction is a property of where in the family the system sits. At ρ = 0.8 Levinson is further from the truth at only 14 of 90, and at ρ = 0.5 at 12 of 90 — so at the easy end of the family the ordering is the other way round, and just as consistently. The forward error does not say that elimination is the more accurate solver. It says that at a given point of the family, one of them is, reproducibly, and which one depends on the point.

The mechanism is visible inside the recursion, and on this family it is unusually clean. Levinson builds each solution from the previous one using a reflection coefficient, and on the Kac–Murdock–Szegő matrix those coefficients are −ρ at the first step and zero at every step afterwards — this family is a first-order autoregressive process, so one coefficient describes it and the rest are zero to rounding. What that leaves is a residual variance α that never decreases, because every later step multiplies it by one: α = 1 − ρ², which is 0.75 at ρ = 0.5, 0.36 at ρ = 0.8 and 2.00·10⁻³ at ρ = 0.999. The recursion divides by that number once per step. At the easy end of the family it is dividing by three quarters n times and at the hard end by two thousandths n times, and that is the whole of why the ordering has an end of the family it belongs to.

That is still categorically different from what the two backward errors do, and the comparison is exact because it is the same ninety points. At ρ = 0.999 the structured backward error puts Levinson above elimination at 51 of 90 and at ρ = 0.99 at 53 of 90 — a coin, at both ends of the family, on the quantity whose magnitudes differ by two orders. The forward error at those same two points reads 68 and 82. One instrument has a direction that survives a change of right-hand side and the other does not, and the one with the direction is the one that needed the answer.

What the ladder says about which number to trust #

The three quantities can be laid out on one matrix, because the condition number of the model already built the ladder for them: one matrix described four ways, each description a subset of the one above it.

Read down that ladder and the pattern of this essay is visible in one picture. The quantity that moves the most between the first rung and the last is the one that is not computed; the quantity that is printed is the one at the top, which barely moves at all. Constant diagonals buy a factor of 2.48 on the conditioning side and the last rung buys 416, which is the other half of the trade measured on a palindromic quadratic rather than on a Toeplitz system, and it points the same way there.

What follows for anything that reports a backward error #

The consequence is narrower than “backward errors are useless” and it is worth going through case by case.

A single reported backward error is still worth printing. It is ‖r‖ over ‖x̂‖ and costs one matrix–vector product, it bounds the structured quantity from below, and a value that is not at the rounding level is a genuine alarm. Nothing here says otherwise, and a small residual is not a small error is about the other direction, where the number is small and reassuring and the answer is wrong.

Two reported backward errors must not be compared. That is the finding. The difference between the two solvers here is a third of the scatter of either one, so the comparison reports which of two roundings came out larger. A benchmark table with a backward-error column and two rows in it is answering a question about the right-hand side.

The structured number is a diagnostic and not a score. It is the right quantity for asking is there a nearby problem of the kind that was posed, and it answers that well — three to seven orders above the reported figure on this family, and absent altogether at the last rung of the ladder. It is the wrong quantity for asking which of two methods produced it, because its sign is set by the point.

And a method’s accuracy is not a number it carries. Accurate is not a property of a method argues that in general and this is a sharp instance: the ordering of these two solvers reverses between ρ = 0.8 and ρ = 0.999 on the only quantity that has an ordering at all. Whatever is true of Levinson here is true of Levinson on this family at this end of it, and the essay that says so about what the spectrum does as ρ climbs is describing the same coordinate.

The refusal #

The claim fed to the assertion is that the structured backward error, being the honest measurement, is therefore the one to compare two solvers by. The first half is granted; the second does not follow, and the arithmetic behind the first half is what makes the failure of the second worth recording.

Restricting the perturbation cannot lower the backward error. The same residual has to be explained by fewer degrees of freedom, so the minimum over the smaller set cannot be below the minimum over the larger one, and at every one of the forty-eight points here the structured number is the larger — 1.83·10⁻¹² against 1.93·10⁻¹⁷ for Levinson at n = 8, ρ = 0.999. The assertion is fed the opposite claim, computed on a perturbation that moves every coefficient of a quadratic eigenvalue problem, where the same relation holds between an unrestricted backward error and one confined to a single coefficient matrix, and it is required to reject it.

What the sweep adds is that the inequality is not an ordering. Being larger by construction says nothing about being larger for one solver than for another, and the measurement says it is larger for Levinson at twenty-eight points and for elimination at twenty. An inequality that holds by an argument about degrees of freedom has been read as a ranking, and it is a ranking of perturbation sets rather than of algorithms.

The sentence this collection is built on — the exact answer to a nearby problem — survives all of this intact. Both solvers return the exact answer to a nearby problem, both nearby problems are close, and the one that is a genuine symmetric Toeplitz system is further away than the reported number suggests. What does not survive is the extra step nobody writes down: that the distance to the nearby problem, being a small number attached to an algorithm, can be used to choose between two of them.