Numerical Linear Algebra
where the algebra stops being the arithmetic
Exact arithmetic, and what it costs instead

An exact answer to a measured problem

The residual is the zero vector, nothing was rounded at any step, and the answer is wrong in its first digit. Data accurate to fourteen places, an exact solve of the system it defines, and an error of 10⁻⁵ — because conditioning was never a statement about arithmetic and removing the arithmetic error removes none of it.
42 min read 35 figures Whose fault is itExact ground truthMeasured, not assertedWhere the algebra stops being the arithmetic

Worth reading first: The condition number is an amplifier · The exact answer to a nearby problem · An answer with no error in it.

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.

An exact solve of a measured 8 × 8 system, against the error the measurement put thereThe rising curve is the distance from the exact solution of a perturbed system to the exact solution of the unperturbed one, as the perturbation grows from a relative 10⁻¹⁶ to 1. Every point on it was computed with no rounding anywhere: the elimination is over the rationals, the residual of each solve is the zero vector, and the error is entirely the data's. At a measurement accurate to 10^-12 the answer is wrong by 9.988·10⁻⁴, which is 10·10⁸ times the data's own error — the matrix's condition number, doing the only job left for it to do. The straight line of slope one is the whole finding: removing the arithmetic error changes nothing about this quantity, because this quantity was never about the arithmetic.10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻⁷10⁻⁵10⁻³10⁻¹10¹relative error in the datarelative error in the answerthe answer's errorthe data's errornothing here is the arithmetic'sdata error10⁻¹²answer error10·10⁻⁴amplification10·10⁸rounding committed0residual0the residual is exactly zeroand the answer is wrong anyway
Fig. 1 An integer Hilbert system of order eight, perturbed by an exact relative ε and solved over the rationals at every ε from 10⁻¹⁶ to 1. Nothing is rounded at any point on that curve. The residual of every solve is the zero vector.

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.

So on this system, the float solve is nearer to the truth than the exact one is, because its effective perturbation is smaller. That is not a paradox and it is not an argument against exact arithmetic; it is the identity being read correctly. The two routes differ only in the size of the perturbation they are exactly solving, and one of them inherits the data’s.

The general form is a rule of thumb worth stating: exact arithmetic is worth its cost when the data’s own relative error is below the unit roundoff, and is worth nothing when it is above. Between those, it buys a fraction of a digit.

An exact solve of a measured 8 × 8 system, against the error the measurement put thereThe rising curve is the distance from the exact solution of a perturbed system to the exact solution of the unperturbed one, as the perturbation grows from a relative 10⁻¹⁶ to 1. Every point on it was computed with no rounding anywhere: the elimination is over the rationals, the residual of each solve is the zero vector, and the error is entirely the data's. At a measurement accurate to 10^-6 the answer is wrong by 2.049·10⁻⁶, which is 2.05 times the data's own error — the matrix's condition number, doing the only job left for it to do. The straight line of slope one is the whole finding: removing the arithmetic error changes nothing about this quantity, because this quantity was never about the arithmetic.10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1relative error in the datarelative error in the answerthe answer's errorthe data's errornothing here is the arithmetic'sdata error10⁻⁶answer error2·10⁻⁶amplification2rounding committed0residual0the residual is exactly zeroand the answer is wrong anyway
Fig. 2 A well-conditioned integer system for contrast: an amplification of 2.05, so a measurement good to six places gives an answer good to six places, and the exactness is again beside the point.

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⁻².

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 exact solution of a hilbert system is longer than the systemAx = b with A a hilbert integer matrix and b chosen so the answer is a genuine vector of fractions. At n = 8 the question occupies 1216 bits — 8² entries of 19 bits each — and the answer occupies 117, a ratio of 0.0962. Every entry is a ratio of two determinants by Cramer's rule, checked here by multiplying each one back by det A and comparing it with the determinant of the column-replaced matrix as an integer — so every denominator divides det A and none of them is longer than its 40 bits, while a numerator can be, at 16 here. The answer IS that long, whatever route produced it. That is a floor no exact solver can get under, and it is why the modular route reconstructs the answer rather than eliminating its way to it.34567810²nbitsthe answerthe question · det Abits in, bits outn8question1216answer117det A40widest part16the answer is the floorand no route writes it down more cheaply
Fig. 3 The ill-conditioned family’s answers, in bits. The difficulty appears as length here, which is the field’s only currency.

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.

Backward error, forward error and the condition number, with measured valuesTwo boxes at the top — the problem posed and the nearby problem the algorithm answered exactly — and two answers below them, with the distances between all four labelled by numbers from a Hilbert solve.the problem you posedA = H10b = A·(1, 2, …, 10)the problem it answered exactlyA + δA, b + δb‖δ‖ / ‖A‖ = 2.3·10⁻¹⁷the answer you wantedx = (1, 2, …, 10), exactlythe answer you gotx̂, wrong by 2.7·10⁻⁴ relativebackward error 2.3·10⁻¹⁷forward error 2.7·10⁻⁴κ = 1.6·10¹³κ · η = 3.6·10⁻⁴, and the measured forward error is 2.7·10⁻⁴.The algorithm is not at fault. The problem is.H10, LU with partial pivotingresidual and error differ
Fig. 4 The identity with both factors present, in the field where one of them is not zero.

At other settings

An exact solve of a measured 8 × 8 system, against the error the measurement put thereThe rising curve is the distance from the exact solution of a perturbed system to the exact solution of the unperturbed one, as the perturbation grows from a relative 10⁻¹⁶ to 1. Every point on it was computed with no rounding anywhere: the elimination is over the rationals, the residual of each solve is the zero vector, and the error is entirely the data's. At a measurement accurate to 10^-14 the answer is wrong by 1.002·10⁻⁵, which is 10⁹ times the data's own error — the matrix's condition number, doing the only job left for it to do. The straight line of slope one is the whole finding: removing the arithmetic error changes nothing about this quantity, because this quantity was never about the arithmetic.10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻⁷10⁻⁵10⁻³10⁻¹10¹relative error in the datarelative error in the answerthe answer's errorthe data's errornothing here is the arithmetic'sdata error10⁻¹⁴answer error10⁻⁵amplification10⁹rounding committed0residual0the residual is exactly zeroand the answer is wrong anyway
Fig. 5 Data good to fourteen places, an answer good to five.
An exact solve of a measured 8 × 8 system, against the error the measurement put thereThe rising curve is the distance from the exact solution of a perturbed system to the exact solution of the unperturbed one, as the perturbation grows from a relative 10⁻¹⁶ to 1. Every point on it was computed with no rounding anywhere: the elimination is over the rationals, the residual of each solve is the zero vector, and the error is entirely the data's. At a measurement accurate to 10^-8 the answer is wrong by 0.2705, which is 2.7·10⁷ times the data's own error — the matrix's condition number, doing the only job left for it to do. The straight line of slope one is the whole finding: removing the arithmetic error changes nothing about this quantity, because this quantity was never about the arithmetic.10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻⁷10⁻⁵10⁻³10⁻¹10¹relative error in the datarelative error in the answerthe answer's errorthe data's errornothing here is the arithmetic'sdata error10⁻⁸answer error0.27amplification2.7·10⁷rounding committed0residual0the residual is exactly zeroand the answer is wrong anyway
Fig. 6 Data good to eight places, and an answer with no correct digits.
An exact solve of a measured 8 × 8 system, against the error the measurement put thereThe rising curve is the distance from the exact solution of a perturbed system to the exact solution of the unperturbed one, as the perturbation grows from a relative 10⁻¹⁶ to 1. Every point on it was computed with no rounding anywhere: the elimination is over the rationals, the residual of each solve is the zero vector, and the error is entirely the data's. At a measurement accurate to 10^-4 the answer is wrong by 2.806, which is 28100 times the data's own error — the matrix's condition number, doing the only job left for it to do. The straight line of slope one is the whole finding: removing the arithmetic error changes nothing about this quantity, because this quantity was never about the arithmetic.10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻⁷10⁻⁵10⁻³10⁻¹10¹relative error in the datarelative error in the answerthe answer's errorthe data's errornothing here is the arithmetic'sdata error10⁻⁴answer error2.8amplification2.8·10⁴rounding committed0residual0the residual is exactly zeroand the answer is wrong anyway
Fig. 7 And a coarse measurement, where the error saturates because the answer cannot be more wrong than it is large.
An exact solve of a measured 8 × 8 system, against the error the measurement put thereThe rising curve is the distance from the exact solution of a perturbed system to the exact solution of the unperturbed one, as the perturbation grows from a relative 10⁻¹⁶ to 1. Every point on it was computed with no rounding anywhere: the elimination is over the rationals, the residual of each solve is the zero vector, and the error is entirely the data's. At a measurement accurate to 10^-10 the answer is wrong by 2.049·10⁻¹⁰, which is 2.05 times the data's own error — the matrix's condition number, doing the only job left for it to do. The straight line of slope one is the whole finding: removing the arithmetic error changes nothing about this quantity, because this quantity was never about the arithmetic.10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1relative error in the datarelative error in the answerthe answer's errorthe data's errornothing here is the arithmetic'sdata error10⁻¹⁰answer error2·10⁻¹⁰amplification2rounding committed0residual0the residual is exactly zeroand the answer is wrong anyway
Fig. 8 The well-conditioned system, where the same sweep is a line of slope one and amplification 2.
An exact solve of a measured 8 × 8 system, against the error the measurement put thereThe rising curve is the distance from the exact solution of a perturbed system to the exact solution of the unperturbed one, as the perturbation grows from a relative 10⁻¹⁶ to 1. Every point on it was computed with no rounding anywhere: the elimination is over the rationals, the residual of each solve is the zero vector, and the error is entirely the data's. At a measurement accurate to 10^-2 the answer is wrong by 0.02007, which is 2.01 times the data's own error — the matrix's condition number, doing the only job left for it to do. The straight line of slope one is the whole finding: removing the arithmetic error changes nothing about this quantity, because this quantity was never about the arithmetic.10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1relative error in the datarelative error in the answerthe answer's errorthe data's errornothing here is the arithmetic'sdata error0.01answer error0.02amplification2rounding committed0residual0the residual is exactly zeroand the answer is wrong anyway
Fig. 9 And at a coarse measurement on the same system, where the answer is as good as the data.
The exact solution of a hilbert system is longer than the systemAx = b with A a hilbert integer matrix and b chosen so the answer is a genuine vector of fractions. At n = 9 the question occupies 1944 bits — 9² entries of 24 bits each — and the answer occupies 193, a ratio of 0.0993. Every entry is a ratio of two determinants by Cramer's rule, checked here by multiplying each one back by det A and comparing it with the determinant of the column-replaced matrix as an integer — so every denominator divides det A and none of them is longer than its 73 bits, while a numerator can be, at 21 here. The answer IS that long, whatever route produced it. That is a floor no exact solver can get under, and it is why the modular route reconstructs the answer rather than eliminating its way to it.345678910²nbitsthe answerthe question · det Abits in, bits outn9question1944answer193det A73widest part21the answer is the floorand no route writes it down more cheaply
Fig. 10 The lengths the ill-conditioned family produces, which is what its difficulty costs here.
8 × 8: three exact determinants agree to the digit, and the float one does notdet A = 778350798225 on a hilbert matrix of order 8, computed three ways with no rounding anywhere: fraction-free elimination, elimination over the rationals, and elimination modulo 6 word-sized primes put back together by the Chinese remainder theorem. The three differ by exactly zero — as integers, not to a tolerance. The floating-point LU of the same matrix returns 7.7835078·10¹¹, a relative error of 2.322·10⁻⁸, which is what a determinant of 40 bits does to a significand of 53. The modular route's entries never exceed 26 bits, which is why the number of primes has to be decided in advance: Hadamard's bound says 141 bits are needed and 6 primes supply them.Bareiss60 bitsrationals19 bitsmodular26 bitsthe answer40 bitsHadamard141 bitswidest number formedrelative error against the exact answerfraction-free (Bareiss)0rational elimination0modular, 6 primes0floating-point LU2.3·10⁻⁸det A = 778350798225three routes, one integerand no tolerance anywhere in the comparison
Fig. 11 Its determinant, where the float route has lost the answer and the exact ones have not noticed.
Three exact eliminations of the same hilbert matrix, and the widest number each one formsEvery route here returns the same determinant exactly, so there is no error to plot and the y-axis is the length of the intermediates in bits. At n = 9 the answer itself is 73 bits and Hadamard's bound allows 203. Fraction-free elimination never forms a number wider than 91 bits, because each of its intermediates is a minor of the original matrix. Rational elimination that reduces every fraction to lowest terms reaches 24 bits and pays a gcd on every arithmetic operation to stay there. Rational elimination that does not reduce reaches 487668 bits — 5360 times the width of the fraction-free route and 6680 times the width of the answer. All three are correct.3456789110¹10²10³10⁴10⁵10⁶nwidest intermediate, in bitsrationals, not reducedfraction-free · rationals reduced · the answerone answer, three widthsn9answer73Hadamard bound203fraction-free91reduced rationals24unreduced4.9·10⁵the error is zero on every curvethe cost is the length of the numbers
Fig. 12 And its intermediates, where the conditioning is invisible and only the length is measured.
The exact solution of a 13×13 Hilbert system beside the computed oneTwo columns of numbers: the exact answer, which is the integers one to thirteen, and the answer double-precision elimination returns, with the number of correct digits beside each.H13 x = b, b formed exactly so that x = (1, 2, …, 13)12345678910111213exact1.00002.00003.00133.97865.18864.993010.46720.048921.2657-2.575319.21478.906013.5113computed6.6 correct digits4.8 correct digits3.4 correct digits2.3 correct digits1.4 correct digit0.8 correct digitno correct digitsno correct digitsno correct digitsno correct digitsno correct digits0.6 correct digit1.4 correct digitbackward error2.2·10⁻¹⁷κ = 1.7·10¹⁸The algorithm solved a neighbouring problem perfectly. That problem's answer is this one.right-hand side built in BigInt rationalsthe truth is known
Fig. 13 The same matrix used as a ruler rather than as a problem, which is where the exactness pays.
How much a perturbation of the right-hand side is amplified, κ = 10⁶The cumulative distribution of the amplification factor over two hundred random perturbation directions, with the condition number marked as the upper limit.110¹10²10³10⁴10⁵10⁶10⁷00.250.50.751amplification of the input perturbationfraction of directions at or belowκ = 10·10⁵worst found 7.6·10⁵6×6, 200 directionsmedian reaches 0.29 of κ
Fig. 14 The amplifier itself, in the field that named it.
Backward and forward error against the condition numberA log–log plot over twelve decades of condition number. The backward error is a flat line at ten to the minus sixteen; the forward error rises in proportion to the condition number.110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)relative errorforward errorbackward errorpredicted: κ · u8×8, 20 seeds per κ; dashed is the worstthe problem worsens, not the method
Fig. 15 A small residual and a large error, which this field reaches with a residual of exactly zero.
Forward error of a 6×6 Hilbert solve at eight precisionsA bar for each significand width from 12 to 53 bits showing the relative error in the computed solution, with the condition number times the unit roundoff marked as a prediction.κ = 1.5·10⁷ · the exact answer is (1, 2, …, 6)12 bits3.316 bits0.8620 bits4.324 bits0.09330 bits7.6·10⁻⁴36 bits6.2·10⁻⁶43 bits2·10⁻⁷53 bits4.5·10⁻¹¹dashed: κ · unit roundoffone matrix, eight arithmeticsmeasured against a known answer
Fig. 16 The precision knob, which this field has set to infinity and which has not helped.
One 6 × 6 integer matrix, 3 different ranksThe same matrix of integers, its rank computed exactly with no rounding and no threshold anywhere, over the rationals and over the fields with 2, 3, 5, 7, 11, 13, 101, 65537 elements. Over ℚ the rank is 6; over 𝔽2 and 𝔽3 it is 4 and 5. Nothing has been approximated and nothing has been decided by a tolerance — the eliminations are exact in every case, and there is no small number anywhere for a threshold to be compared against. The rank is not a property of the array of numbers; it is a property of the array together with the ring the entries are read in, and a modular algorithm that reports a rank has reported the second one.ℚ6𝔽24𝔽35𝔽56𝔽76𝔽116𝔽136𝔽1016𝔽655376rank, by the ring the entries are read inthe rank of one matrixover ℚ6over 𝔽24over 𝔽35over 𝔽56over 𝔽76nothing is rounded hereand the answer still is not a property of the matrix
Fig. 17 The other quantity exactness does not settle, for an entirely unrelated reason.
An exact solve of a measured 8 × 8 system, against the error the measurement put thereThe rising curve is the distance from the exact solution of a perturbed system to the exact solution of the unperturbed one, as the perturbation grows from a relative 10⁻¹⁶ to 1. Every point on it was computed with no rounding anywhere: the elimination is over the rationals, the residual of each solve is the zero vector, and the error is entirely the data's. At a measurement accurate to 10^-6 the answer is wrong by 1.342, which is 1.3·10⁶ times the data's own error — the matrix's condition number, doing the only job left for it to do. The straight line of slope one is the whole finding: removing the arithmetic error changes nothing about this quantity, because this quantity was never about the arithmetic.10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻⁷10⁻⁵10⁻³10⁻¹10¹relative error in the datarelative error in the answerthe answer's errorthe data's errornothing here is the arithmetic'sdata error10⁻⁶answer error1.3amplification1.3·10⁶rounding committed0residual0the residual is exactly zeroand the answer is wrong anyway
Fig. 18 Data good to six places, and an answer larger than the truth.
An exact solve of a measured 8 × 8 system, against the error the measurement put thereThe rising curve is the distance from the exact solution of a perturbed system to the exact solution of the unperturbed one, as the perturbation grows from a relative 10⁻¹⁶ to 1. Every point on it was computed with no rounding anywhere: the elimination is over the rationals, the residual of each solve is the zero vector, and the error is entirely the data's. At a measurement accurate to 10^-14 the answer is wrong by 2.049·10⁻¹⁴, which is 2.05 times the data's own error — the matrix's condition number, doing the only job left for it to do. The straight line of slope one is the whole finding: removing the arithmetic error changes nothing about this quantity, because this quantity was never about the arithmetic.10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1relative error in the datarelative error in the answerthe answer's errorthe data's errornothing here is the arithmetic'sdata error10⁻¹⁴answer error2·10⁻¹⁴amplification2rounding committed0residual0the residual is exactly zeroand the answer is wrong anyway
Fig. 19 The well-conditioned system at the accurate end, amplifying by two.
An exact solve of a measured 6 × 6 system, against the error the measurement put thereThe rising curve is the distance from the exact solution of a perturbed system to the exact solution of the unperturbed one, as the perturbation grows from a relative 10⁻¹⁶ to 1. Every point on it was computed with no rounding anywhere: the elimination is over the rationals, the residual of each solve is the zero vector, and the error is entirely the data's. At a measurement accurate to 10^-10 the answer is wrong by 2.167·10⁻⁴, which is 2.2·10⁶ times the data's own error — the matrix's condition number, doing the only job left for it to do. The straight line of slope one is the whole finding: removing the arithmetic error changes nothing about this quantity, because this quantity was never about the arithmetic.10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1relative error in the datarelative error in the answerthe answer's errorthe data's errornothing here is the arithmetic'sdata error10⁻¹⁰answer error2.2·10⁻⁴amplification2.2·10⁶rounding committed0residual0the residual is exactly zeroand the answer is wrong anyway
Fig. 20 Order six, where the conditioning is smaller and the story is the same.
The exact solution of a hilbert system is longer than the systemAx = b with A a hilbert integer matrix and b chosen so the answer is a genuine vector of fractions. At n = 6 the question occupies 540 bits — 6² entries of 15 bits each — and the answer occupies 73, a ratio of 0.135. Every entry is a ratio of two determinants by Cramer's rule, checked here by multiplying each one back by det A and comparing it with the determinant of the column-replaced matrix as an integer — so every denominator divides det A and none of them is longer than its 32 bits, while a numerator can be, at 10 here. The answer IS that long, whatever route produced it. That is a floor no exact solver can get under, and it is why the modular route reconstructs the answer rather than eliminating its way to it.345610²nbitsthe answerthe question · det Abits in, bits outn6question540answer73det A32widest part10the answer is the floorand no route writes it down more cheaply
Fig. 21 The lengths the ill-conditioned family produces at small sizes.
Three exact eliminations of the same hilbert matrix, and the widest number each one formsEvery route here returns the same determinant exactly, so there is no error to plot and the y-axis is the length of the intermediates in bits. At n = 8 the answer itself is 40 bits and Hadamard's bound allows 140. Fraction-free elimination never forms a number wider than 60 bits, because each of its intermediates is a minor of the original matrix. Rational elimination that reduces every fraction to lowest terms reaches 19 bits and pays a gcd on every arithmetic operation to stay there. Rational elimination that does not reduce reaches 94136 bits — 1570 times the width of the fraction-free route and 2350 times the width of the answer. All three are correct.345678110¹10²10³10⁴10⁵nwidest intermediate, in bitsrationals, not reducedfraction-free · rationals reduced · the answerone answer, three widthsn8answer40Hadamard bound140fraction-free60reduced rationals19unreduced9.4·10⁴the error is zero on every curvethe cost is the length of the numbers
Fig. 22 Its intermediates, which the conditioning is invisible in.
6 × 6: three exact determinants agree to the digit, and the float one does notdet A = 2435091120 on a hilbert matrix of order 6, computed three ways with no rounding anywhere: fraction-free elimination, elimination over the rationals, and elimination modulo 4 word-sized primes put back together by the Chinese remainder theorem. The three differ by exactly zero — as integers, not to a tolerance. The floating-point LU of the same matrix returns 2.43509112·10⁹, a relative error of 1.329·10⁻¹¹, which is what a determinant of 32 bits does to a significand of 53. The modular route's entries never exceed 26 bits, which is why the number of primes has to be decided in advance: Hadamard's bound says 85 bits are needed and 4 primes supply them.Bareiss40 bitsrationals15 bitsmodular26 bitsthe answer32 bitsHadamard85 bitswidest number formedrelative error against the exact answerfraction-free (Bareiss)0rational elimination0modular, 4 primes0floating-point LU1.3·10⁻¹¹det A = 2435091120three routes, one integerand no tolerance anywhere in the comparison
Fig. 23 Its determinant, where the float route is already gone.
The determinant's length, and the bound that decides how many primes to use before any of them is chosenSolid: Hadamard's bound on |det A|, the product of the row 2-norms, in bits. Dotted: the determinant's actual length. The bound is what a modular determinant budgets against — at n = 9 the random family needs 37 bits, which is 2 word-sized primes at 26 bits each, and that count is fixed before the first residue is computed. On a Sylvester Hadamard matrix of order 8 the bound is 13 bits and the determinant has 13, so the bound is attained rather than merely satisfied. On the unit triangular family the determinant is 1 at every size while the bound grows, which is the gap the budget pays for: a matrix can have a determinant of one and rows that are long.3456789110¹10²nbitsthe budget and what it buysrandom, bound37random, actual25primes needed2Hadamard n = 8, bound13Hadamard n = 8, actual13the count is decided by a theorembefore any arithmetic happens
Fig. 24 The budget for computing exactly the answer that was not wanted.
4 × 4: the invariant factors, computed twice by routes with no algorithm in commonThe Smith normal form of a hilbert matrix of order 4 is the diagonal [1, 7, 7, 105], reached by unimodular row and column operations, with each entry dividing the next — a property the elimination does not give and which has to be enforced and asserted. The same numbers computed from the definition — the gcd of all k × k minors, over the gcd of all (k−1) × (k−1) minors — are [1, 7, 7, 105], and the two agree entry for entry. Their product is 5145, which is |det A| = 5145. The Hermite form of the same matrix reaches 9 bits against the Smith form's 9, and its transform has determinant 1, so the lattice the rows generate is unchanged.s10 bitss23 bitss33 bitss47 bitsinvariant factors, in bitstwo routes, and a conserved quantitydet A5145Π invariants5145SNF widest9HNF widest9det of the transform1an algorithm and a definitionagreeing as integers
Fig. 25 The invariant factors of the same matrix, carrying its determinant.
One 6 × 6 integer matrix, 3 different ranksThe same matrix of integers, its rank computed exactly with no rounding and no threshold anywhere, over the rationals and over the fields with 2, 3, 5, 7, 11, 13, 101, 65537 elements. Over ℚ the rank is 6; over 𝔽2 and 𝔽3 it is 4 and 5. Nothing has been approximated and nothing has been decided by a tolerance — the eliminations are exact in every case, and there is no small number anywhere for a threshold to be compared against. The rank is not a property of the array of numbers; it is a property of the array together with the ring the entries are read in, and a modular algorithm that reports a rank has reported the second one.ℚ6𝔽24𝔽35𝔽56𝔽76𝔽116𝔽136𝔽1016𝔽655376rank, by the ring the entries are read inthe rank of one matrixover ℚ6over 𝔽24over 𝔽35over 𝔽56over 𝔽76nothing is rounded hereand the answer still is not a property of the matrix
Fig. 26 The other quantity exactness leaves undecided.
det A = 30030, and its residue at 30 primes — 5 of which divide itEach dot is det A mod p, drawn as a fraction of p so the primes are comparable. A dot on the floor is a prime at which the elimination reports a singular matrix — and the matrix is not singular: its determinant is 30030. 5 of 30 primes here are unlucky, a rate of 16.7 per cent, which is what it looks like when the primes are small. At the 26-bit primes a modular determinant actually uses, a prime divides a 15-bit determinant with probability of order 2.24·10⁻⁷ — but the consequence is unchanged, and there is no way to see it from one residue. What sees it is the budget: computing more residues than Hadamard's bound requires, and refusing to reconstruct when the extra ones disagree.det mod p, as a fraction of p3713a prime that divides the answerdet A3·10⁴primes swept30unlucky5rate0.17det, in bits15singular mod p is not singularand one residue cannot tell them apart
Fig. 27 And the third, which is a substitution rather than an amplification.
An exact solve of a measured 8 × 8 system, against the error the measurement put thereThe rising curve is the distance from the exact solution of a perturbed system to the exact solution of the unperturbed one, as the perturbation grows from a relative 10⁻¹⁶ to 1. Every point on it was computed with no rounding anywhere: the elimination is over the rationals, the residual of each solve is the zero vector, and the error is entirely the data's. At a measurement accurate to 10^-2 the answer is wrong by 8.798, which is 880 times the data's own error — the matrix's condition number, doing the only job left for it to do. The straight line of slope one is the whole finding: removing the arithmetic error changes nothing about this quantity, because this quantity was never about the arithmetic.10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻⁷10⁻⁵10⁻³10⁻¹10¹relative error in the datarelative error in the answerthe answer's errorthe data's errornothing here is the arithmetic'sdata error0.01answer error8.8amplification880rounding committed0residual0the residual is exactly zeroand the answer is wrong anyway
Fig. 28 A coarse measurement, where the error has saturated.
An exact solve of a measured 8 × 8 system, against the error the measurement put thereThe rising curve is the distance from the exact solution of a perturbed system to the exact solution of the unperturbed one, as the perturbation grows from a relative 10⁻¹⁶ to 1. Every point on it was computed with no rounding anywhere: the elimination is over the rationals, the residual of each solve is the zero vector, and the error is entirely the data's. At a measurement accurate to 10^-4 the answer is wrong by 2.048·10⁻⁴, which is 2.05 times the data's own error — the matrix's condition number, doing the only job left for it to do. The straight line of slope one is the whole finding: removing the arithmetic error changes nothing about this quantity, because this quantity was never about the arithmetic.10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1relative error in the datarelative error in the answerthe answer's errorthe data's errornothing here is the arithmetic'sdata error10⁻⁴answer error2·10⁻⁴amplification2rounding committed0residual0the residual is exactly zeroand the answer is wrong anyway
Fig. 29 The well-conditioned system at a coarse measurement.
An exact solve of a measured 10 × 10 system, against the error the measurement put thereThe rising curve is the distance from the exact solution of a perturbed system to the exact solution of the unperturbed one, as the perturbation grows from a relative 10⁻¹⁶ to 1. Every point on it was computed with no rounding anywhere: the elimination is over the rationals, the residual of each solve is the zero vector, and the error is entirely the data's. At a measurement accurate to 10^-12 the answer is wrong by 0.2955, which is 3·10¹¹ times the data's own error — the matrix's condition number, doing the only job left for it to do. The straight line of slope one is the whole finding: removing the arithmetic error changes nothing about this quantity, because this quantity was never about the arithmetic.10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110⁻⁴10⁻²110²relative error in the datarelative error in the answerthe answer's errorthe data's errornothing here is the arithmetic'sdata error10⁻¹²answer error0.3amplification3·10¹¹rounding committed0residual0the residual is exactly zeroand the answer is wrong anyway
Fig. 30 Order ten, where the conditioning is worse still.
The exact solution of a hilbert system is longer than the systemAx = b with A a hilbert integer matrix and b chosen so the answer is a genuine vector of fractions. At n = 7 the question occupies 931 bits — 7² entries of 19 bits each — and the answer occupies 135, a ratio of 0.145. Every entry is a ratio of two determinants by Cramer's rule, checked here by multiplying each one back by det A and comparing it with the determinant of the column-replaced matrix as an integer — so every denominator divides det A and none of them is longer than its 49 bits, while a numerator can be, at 16 here. The answer IS that long, whatever route produced it. That is a floor no exact solver can get under, and it is why the modular route reconstructs the answer rather than eliminating its way to it.3456710²nbitsthe answerthe question · det Abits in, bits outn7question931answer135det A49widest part16the answer is the floorand no route writes it down more cheaply
Fig. 31 What its difficulty costs in bits.
Three exact eliminations of the same hilbert matrix, and the widest number each one formsEvery route here returns the same determinant exactly, so there is no error to plot and the y-axis is the length of the intermediates in bits. At n = 9 the answer itself is 73 bits and Hadamard's bound allows 203. Fraction-free elimination never forms a number wider than 91 bits, because each of its intermediates is a minor of the original matrix. Rational elimination that reduces every fraction to lowest terms reaches 24 bits and pays a gcd on every arithmetic operation to stay there. Rational elimination that does not reduce reaches 487668 bits — 5360 times the width of the fraction-free route and 6680 times the width of the answer. All three are correct.3456789110¹10²10³10⁴10⁵10⁶nwidest intermediate, in bitsrationals, not reducedfraction-free · rationals reduced · the answerone answer, three widthsn9answer73Hadamard bound203fraction-free91reduced rationals24unreduced4.9·10⁵the error is zero on every curvethe cost is the length of the numbers
Fig. 32 Its intermediates, which carry no sign of the conditioning.
8 × 8: three exact determinants agree to the digit, and the float one does notdet A = 778350798225 on a hilbert matrix of order 8, computed three ways with no rounding anywhere: fraction-free elimination, elimination over the rationals, and elimination modulo 6 word-sized primes put back together by the Chinese remainder theorem. The three differ by exactly zero — as integers, not to a tolerance. The floating-point LU of the same matrix returns 7.7835078·10¹¹, a relative error of 2.322·10⁻⁸, which is what a determinant of 40 bits does to a significand of 53. The modular route's entries never exceed 26 bits, which is why the number of primes has to be decided in advance: Hadamard's bound says 141 bits are needed and 6 primes supply them.Bareiss60 bitsrationals19 bitsmodular26 bitsthe answer40 bitsHadamard141 bitswidest number formedrelative error against the exact answerfraction-free (Bareiss)0rational elimination0modular, 6 primes0floating-point LU2.3·10⁻⁸det A = 778350798225three routes, one integerand no tolerance anywhere in the comparison
Fig. 33 Its determinant, forty bits and beyond the float route.
5 × 5: the invariant factors, computed twice by routes with no algorithm in commonThe Smith normal form of a hilbert matrix of order 5 is the diagonal [1, 3, 6, 42, 504], reached by unimodular row and column operations, with each entry dividing the next — a property the elimination does not give and which has to be enforced and asserted. The same numbers computed from the definition — the gcd of all k × k minors, over the gcd of all (k−1) × (k−1) minors — are [1, 3, 6, 42, 504], and the two agree entry for entry. Their product is 381024, which is |det A| = 381024. The Hermite form of the same matrix reaches 12 bits against the Smith form's 14, and its transform has determinant 1, so the lattice the rows generate is unchanged.s10 bitss22 bitss33 bitss45 bitss59 bitsinvariant factors, in bitstwo routes, and a conserved quantitydet A3.8·10⁵Π invariants3.8·10⁵SNF widest14HNF widest12det of the transform1an algorithm and a definitionagreeing as integers
Fig. 34 Its invariant factors.
The determinant's length, and the bound that decides how many primes to use before any of them is chosenSolid: Hadamard's bound on |det A|, the product of the row 2-norms, in bits. Dotted: the determinant's actual length. The bound is what a modular determinant budgets against — at n = 12 the random family needs 52 bits, which is 3 word-sized primes at 26 bits each, and that count is fixed before the first residue is computed. On a Sylvester Hadamard matrix of order 8 the bound is 13 bits and the determinant has 13, so the bound is attained rather than merely satisfied. On the unit triangular family the determinant is 1 at every size while the bound grows, which is the gap the budget pays for: a matrix can have a determinant of one and rows that are long.3456789101112110¹10²nbitsthe budget and what it buysrandom, bound52random, actual40primes needed3Hadamard n = 8, bound13Hadamard n = 8, actual13the count is decided by a theorembefore any arithmetic happens
Fig. 35 The budget for computing it exactly.

Where this goes next

the problem you posedA = H10b = A·(1, 2, …, 10)the problem it answered exactlyA + δA, b + δb‖δ‖ / ‖A‖ = 2.3·10⁻¹⁷the answer you wantedx = (1, 2, …, 10), exactlythe answer you gotx̂, wrong by 2.7·10⁻⁴ relativebackward error 2.3·10⁻¹⁷forward error 2.7·10⁻⁴κ = 1.6·10¹³κ · η = 3.6·10⁻⁴, and the measured forward error is 2.7·10⁻⁴.The algorithm is not at fault. The problem is.H10, LU with partial pivotingresidual and error differ The exact answer to a nearby problem A good algorithm does not give an approximate answer to your problem. It gives the exact answer to a problem very close to yours — and once that is the definition, a wrong result has two possible authors and they can be measured apart. 110¹10²10³10⁴10⁵10⁶10⁷00.250.50.751amplification of the input perturbationfraction of directions at or belowκ = 10·10⁵worst found 7.6·10⁵6×6, 200 directionsmedian reaches 0.29 of κ The condition number is an amplifier κ is usually introduced as a definition and then quoted. It is a measurement: perturb the input by a known amount, look at how much the output moves, and the largest ratio you can find is the number. 3456789101112110¹10²10³10⁴10⁵10⁶nwidest intermediate, in bitsrationals, not reducedfraction-free · rationals reduced · the answerone answer, three widthsn12answer40Hadamard bound52fraction-free40reduced rationals39unreduced1.4·10⁶the error is zero on every curvethe cost is the length of the numbers An answer with no error in it An integer matrix eliminated over the rationals rounds nothing, so the forward error is zero, the residual is the zero vector, and the identity this site is built on has no terms left. The cost does not vanish with the error. It moves into the length of the numbers, where three correct routes differ by four orders of magnitude.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

Backward errorBit lengthCondition numberExact arithmeticExact ground truthForward errorHilbert matrix