An exact answer to a measured problem

This field opened by removing every term from the identity the site is built on. Forward error zero, backward error zero, residual the zero vector, and a condition number multiplying nothing. Nine essays have been about what replaced it — the length of the numbers, the budget of primes, the bound on a reconstruction — and all of them are cost arguments.

There is one term that did not go away, and it is the one that decides whether any of the cost was worth paying.

The measurement #

Take the Hilbert matrix of order eight, cleared of its denominators so that every entry is an integer — multiplying by a constant changes no condition number, so this is the classical ill-conditioned matrix arriving in a field that cannot round. Choose a right-hand side. Solve exactly and call the answer the truth, because it is: there is no rounding anywhere in it and the residual is the zero vector.

Now perturb the matrix by an exact relative ε — each entry multiplied by 1 ± ε with ε a rational 10⁻ᵏ, so the perturbation is exactly ε rather than approximately — and solve exactly again. The residual of that solve is also the zero vector. It is the exact solution of the perturbed system.

At ε = 10⁻¹⁴ the two answers differ by a relative 10⁻⁵.

At ε = 10⁻¹⁰ they differ by 0.074. At ε = 10⁻⁶ they differ by 1.34 — the answer has no correct digits at all — and at 10⁻² by 8.8, which is larger than the answer.

The amplification at the accurate end is about 10⁹. That is the matrix’s condition number, doing the only thing left for it to do.

It is worth dwelling on what those numbers are, because the temptation is to read them as an arithmetic failure and there is no arithmetic in them. Every solve on that curve is over the rationals. Every entry of every answer is a fraction in lowest terms. Substituting any of them back into its own system gives an identity between integers, not a small number — the residual is not 10⁻¹⁶, it is the zero vector, and there is nothing on the plot for it to be compared against.

Why the field cannot fix this and never could #

The identity says forward error is bounded by condition number times backward error, and this field’s whole achievement is driving the backward error to exactly zero. What it cannot do is anything about the other factor, because the other factor is not about arithmetic.

The condition number is a property of the map from data to answer. It says how far the answer moves when the data moves, and it would say the same thing if the arithmetic were performed by an oracle. The essay that introduced it makes the point in floating point and the point is not about floating point: an amplifier amplifies whatever arrives, and what arrives here is the measurement’s own error rather than a rounding.

So the correct reading of the curve is that it has nothing to do with this field at all. It would be identical if the solves were done in double precision, up to the point where the double precision’s own error became comparable — which for this matrix is at about ε = 10⁻¹⁶, off the left edge. Every point on the plotted curve is a point where the arithmetic contributed nothing and the data contributed everything.

Where the exactness does help, precisely #

That is not the same as saying it never helps, and the boundary is worth drawing carefully, because it is the practical content of ten essays.

Exactness helps when the data is exact. A graph’s Laplacian is integers because a graph is vertices and edges; a spanning-tree count is an integer because Kirchhoff’s theorem says so; a combinatorial matrix has the entries it has and no measurement was involved. Those are the cases where the answer is a certificate, and the field’s cost is buying something real.

Exactness helps when the answer is discrete. A rank, a determinant’s sign, a count of lattice points, a decision about whether a system has an integer solution. There the amplification argument does not apply in the same way, because a small perturbation of the data changes the answer by nothing at all until it changes it completely — which is the graph field’s whole subject — and an exact routine lands on the right side of that discontinuity by construction.

And exactness helps as an instrument. The site’s floating-point measurements are checked against exact ones throughout: the Hilbert inverse in closed form, the resistances of a graph as ratios of integers, a characteristic polynomial compared as an integer polynomial. In every one of those the exact answer is not the deliverable; it is the ruler.

It does not help when the data was measured. Then the exact answer is the exact answer to somebody else’s problem, and the distance to the intended one is the condition number times the measurement error, and no arithmetic reaches it.

The awkward case is the fourth, and it is common: data that is nearly exact. A matrix of physical constants known to twelve digits, a discretisation whose coefficients are rationals rounded once when they were tabulated, a graph whose weights were measured. There the data’s error is well above the unit roundoff and well below anything anybody would call inaccurate, and the answer is that exactness buys the difference between 10⁻¹⁶ and the data’s own error — which is to say, nothing, and the routine should be chosen on the cost model rather than on the accuracy.

Why the perturbation had to be exact, which cost a rewrite #

The first version of this measurement perturbed the integer matrix the obvious way: scale every entry by 1/ε, round, and read the rounded matrix as the measured one. It produces an integer matrix, it is one line, and it is wrong.

The relative perturbation it applies is the rounding’s, not ε’s. Asked for 10⁻⁶ on a matrix with two-digit entries it delivered about 2·10⁻⁸, so the x-axis of the plot was off by two orders of magnitude and the reported amplification with it. The figure was internally consistent, every assertion in it passed, and the numbers it printed were about a perturbation nobody had asked for.

The repair is to stay in the rationals. Entry aᵢⱼ becomes aᵢⱼ·(1 ± ε) with ε the exact rational 10⁻ᵏ, so the perturbation is ε by construction and the x-axis means what it says. That the repair is available at all is a property of this field — everywhere else on the site a perturbation of a specified size has to be applied approximately, and the essays say so.

It is worth recording because it is the shape of mistake this field is most exposed to. When nothing rounds, there is no residual to notice a construction error by, and an assertion about the answer passes happily while the question is a different one. The check that caught it was arithmetic on the two axes rather than anything the routine reported about itself.

What a backward-stable float solve is worth here, exactly #

The comparison worth making is not exact-against-float. It is exact-against-backward-stable, and the site has a phrase for what backward stability delivers: the exact answer to a nearby problem.

A backward-stable float solve returns the exact solution of (A + E)x = b with ‖E‖ of order u‖A‖ — a relative perturbation of about 10⁻¹⁶. An exact solve of measured data returns the exact solution of (A + E)x = b with ‖E‖ the measurement’s own error — here 10⁻¹⁴, a hundred times larger.

The tempting next sentence is that on this system the float solve is therefore nearer to the truth than the exact one, since its effective perturbation is smaller. That sentence is wrong, and it is worth being precise about why, because the arithmetic in it is right and the comparison is not.

The float solve is run on the measured matrix too. Its effective perturbation is the data’s error plus the rounding, never the rounding alone — there is no route that gets to see the unmeasured matrix, which is the whole content of the word measured. The comparison the sentence makes is between an exact solve of the data anybody has and a float solve of data nobody has.

Solving the same exactly-perturbed system both ways, and measuring each against the truth:

   ε        exact solve    float solve    ratio    the two answers apart
 10⁻¹⁶      3.443·10⁻⁷     4.358·10⁻⁷     1.266        9.2·10⁻⁸
 10⁻¹⁴      3.442·10⁻⁵     3.436·10⁻⁵     0.998        6.7·10⁻⁸
 10⁻¹²      3.431·10⁻³     3.431·10⁻³     1.000        1.2·10⁻⁷
 10⁻¹⁰      2.557·10⁻¹     2.557·10⁻¹     1.000        1.7·10⁻⁸
 10⁻⁸       9.657·10⁻¹     9.657·10⁻¹     1.000        1.2·10⁻¹⁰
 10⁻⁴       1.000          1.000          1.000        5.6·10⁻¹⁵

They are the same answer. Not comparably accurate — the same: at ε = 10⁻¹⁰ the two solutions differ from each other by 1.7·10⁻⁸ while both differ from the truth by 0.26, so the rounding is seven orders below the thing being measured. The well-conditioned family gives the same picture with the ratio pinned at 1.0000 across fourteen decades.

The one row where the two separate is the first, ε = 10⁻¹⁶, where the data’s error and the unit roundoff are the same size and the ratio is 1.27 on this matrix and 0.88 on the well-conditioned one — noise, in both directions. That is what a crossover looks like when it is reached rather than passed.

So the rule of thumb the argument was reaching for is correct, and its reason is different: exact arithmetic is worth its cost when the data’s own relative error is below the unit roundoff and worth nothing when it is above, because above it the two routes return the same vector. Not a better one and not a worse one — the same one, to seven digits, at a cost that differs by orders of magnitude. That is a stronger statement than a rule about which is nearer, and it is the one the measurement supports.

It also changes what the decision looks like from inside a program. A rule about which route is nearer is a rule about accuracy, and accuracy is the thing a numerical library is expected to trade against cost — so a reader carrying it would reasonably ask how much accuracy the cheap route gives up and whether the answer is tolerable. There is nothing to trade. Above the crossover the two routes are not two points on an accuracy-cost curve; they are one point at two prices, and the question of how much accuracy is being given up has no answer because the amount is zero.

That is the sharpest form of what this field’s tenth essay has to say, and it cuts both ways. It is why exact arithmetic on measured data is not a conservative choice but a wasted one — the caution buys digits that were destroyed before the routine was called. And it is why exact arithmetic on exact data is not an extravagance: there the crossover has not been reached, the data’s error is genuinely zero, and every digit the routine returns is a digit the float route would have lost.

The saturation at the right of the curve #

The plot bends, and the bend is worth explaining because it is not a numerical artefact.

At small ε the error is proportional to ε with the condition number as the constant, which is the straight part. As ε grows the perturbed system stops being a perturbation of the original one: at ε = 10⁻² the matrix has changed in its second digit and its solution is a different vector of comparable size, so the relative difference settles at a number of order one rather than continuing to grow. The amplification, being the ratio of the two, therefore falls as ε rises — 10⁹ at 10⁻¹⁴, 1.3·10⁶ at 10⁻⁶, 880 at 10⁻².

Where that bend begins is worth pinning down rather than leaving to the eye, because it is the boundary of every condition-number statement in this field.

The plateau ends somewhere between the second stop and the third. Four decades of noise cost a quarter of the amplification; the next two decades cost a factor of thirty. Below the knee the condition number is the whole story, and above it the answer is already so wrong that the linearisation the condition number comes from has stopped describing the problem.

So the first-order regime ends between 10⁻¹⁰ and 10⁻⁸, and it ends abruptly. The amplification is 10⁹ at 10⁻¹⁴ and 7.4·10⁸ at 10⁻¹⁰ — flat to within 26% across four decades — then loses a factor of thirty in the next two and reaches 2.81·10⁴ at 10⁻⁴. What ends it is not the data’s size but the answer’s: at 10⁻⁸ the relative error is 0.271, so there is less than a factor of four of room left before saturation, and a ratio whose numerator cannot grow must fall. The practical form is that a condition number describes the map only while the predicted error is still small compared with one — which for a κ of 10⁹ means data good to better than 10⁻⁹, and is exactly the regime a measured problem is not in.

That is the first-order theory failing exactly where it is supposed to. The condition number bounds the derivative of the answer with respect to the data, so it predicts the error for perturbations small enough that the derivative describes the map, and the bend marks where the perturbation stops being small in that sense. The essay on a condition number for one eigenvalue meets the same boundary from the other side: a first-order sensitivity that is exact in the limit and useless at a perturbation the reader would call small.

So the useful reading of the figure is the left half, where the slope is one, and the right half is the standing reminder that a condition number is a linearisation.

The conditioning is visible in the field’s own unit #

There is one thing this field can say about conditioning that the floating-point essays cannot, and it is a small pleasure.

The exact solution of an ill-conditioned integer system has long parts. The Hilbert family’s determinant at order eight occupies forty bits where a random matrix with comparable entries occupies twenty-four, and the answer’s numerators and denominators are correspondingly long. So the difficulty of the problem shows up as bits — as a cost — rather than as an error, and a routine measuring how much work it is doing is measuring something related to the conditioning.

Related, and not equal. The two quantities are genuinely different: a matrix can have a long determinant and be perfectly conditioned, which is what the Hadamard family is, and a matrix can have a determinant of exactly 1 and be badly conditioned, which is what a unit-triangular matrix with large off-diagonal entries is. So the correspondence is a tendency rather than an identity, and it would be an error to read a long answer as a warning. What it is safe to read it as is a cost, which is what this field measures everything in — and the pleasant part is that an ill-conditioned problem is honestly expensive here in a way it is not in floating point, where it costs exactly the same number of operations as an easy one and returns a worse answer for the same price.

The one place the two authors can be separated completely #

There is a positive result buried in the negative one, and it is the sharpest form of a claim this site has been making since its second field.

The identity says a wrong answer has two possible authors and that they are separately measurable. In floating point the separation takes work: a backward error has to be estimated, a condition number has to be estimated, and both estimates carry their own error — the essay on estimating a condition number is about an estimator that can be made to report whatever one likes.

Here the separation is free and it is exact. The backward error is zero, by construction, with no estimate involved. So the entire forward error is the second author’s, and dividing it by the data’s own error gives the amplification measured rather than bounded — 10⁹ on this matrix, at a perturbation where the linearisation still holds.

That makes this field the only place on the site where the identity can be checked rather than applied. Everywhere else the two factors are estimated and their product compared with an observed error, and agreement within an order of magnitude counts as confirmation. Here one factor is exactly zero, the other is exactly the ratio of two exactly computed quantities, and there is nothing left to estimate.

What the field is for, stated once at the end #

Ten essays in, the honest summary is a narrow one and it is better for being narrow.

Exact linear algebra removes one of the two authors of a wrong answer completely. That is worth a great deal when the other author is silent — combinatorial data, integral input, a discrete output, a ruler for measuring something else — and it is worth nothing at all when the other author is loud. The cost of removing it is not a slowdown by a constant; it is a change in what the cost model is, from a count of operations to a count of operations weighted by the length of their operands, and the four orders of magnitude between the best and worst arrangements of the same elimination are the field’s central measurement.

And the condition number survives all of it. It was never a statement about arithmetic — that is the site’s oldest claim, made in its second field and repeated in most of the twenty since — and here it is demonstrated in the only setting where it can be demonstrated cleanly, because here it is the only term left.