Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Scaling — where it appears

A change of units applied to a problem before it is solved, chosen so that no coefficient is systematically larger than another. It is exact in both directions and therefore approximates nothing, and it decides how many digits of the answer survive.

Named by 16 essays across 6 fields — each of them below, with the objects they name alongside it.

0246810⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹log₁₀ γ, the change of unitsrelative errorforward errorη, the quadraticη, the linearisationagainst a closed formη(linearisation), worst7.6·10⁻¹³η(quadratic), worst1.2·10⁻⁴forward error, worst0.0013coefficient spread4.2·10¹⁵the solver is right at every stopabout a problem nobody asked

A backward-stable answer to a problem nobody asked

One quadratic eigenvalue problem, in nine systems of units, with a change of variable that is exact in both directions. The residual the solver prints stays at the rounding level at every stop. The answer loses eleven orders of magnitude, and the two facts are consistent.

polynomial · Linearisation backward error 0246810⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹log₁₀ γ, the change of unitsforward erroras writtenafter scalingone change of variableunscaled, worst0.0013scaled, worst1.7·10⁻¹³orders recovered10scaled coefficient spread4.5the answer was never the problemthe units were

The scaling that buys ten orders

Two lines computed from three norms, a change of variable that is exact in both directions, and the whole of the loss the previous essay measured comes back — flat, at every stop, because after scaling every stop is the same problem.

polynomial · Polynomial scaling first · leading5.47·10⁻⁶first · trailing4.62·10⁻⁵second · leading4.27·10⁻⁵second · trailing2.23·10⁻⁴symmetric · leading5.47·10⁻⁶symmetric · trailing4.05·10⁻⁵all six are the same algebrabest route5.5·10⁻⁶worst route2.2·10⁻⁴spread across the six41condition of the linearisation8.3·10¹²the spectra agreeand the arithmetic does not

Six routes to one spectrum

Three linearisations of one quadratic, each reduced to a standard eigenvalue problem two ways. All six have exactly the same eigenvalues in exact arithmetic. On a well-scaled problem they differ by noise; on a badly scaled one by a factor of forty; and two of the six are the same matrix.

polynomial · Linearisation backward error 110¹10²10³10⁴10⁵10⁶10¹10²10³10⁴10⁵spread of resistances, largest ÷ smallest possiblecondition number, unit diagonalleast-resistance treebreadth-first treegreatest-resistance treenode equationsspread resistances make the loops easyand the nodes hard

Spread resistances make the loops easy

Scaled to a unit diagonal, the loop equations on the least-resistance tree get easier as a network's resistances spread — from 120 to 5.44 over six decades — and stop depending on the grid's size, while the node equations of the same flow get harder, from 538 to 4.6·10⁴. The spread that ruins the range-space formulation rescues the null-space one, though the loops' density means the work saved is a factor of two, not the factor of nine the iteration counts suggest.

orthogonality · Null-space basis 123456110²10⁴10⁶moments Kκ of the block Hankelintegrated in zin (z − c)/ρone division per pointradius6unscaled, K = 62.3·10⁶scaled, K = 61750the factor between1291the ceiling rises by Kand so did the conditioning

The conditioning that rises with the ceiling

Higher moments multiply a contour method's ceiling by K and grade its block Hankel over ρ to the 2K, so the two knobs are the same knob. One division per quadrature point separates them, and the measurement of what it is worth grows from twenty to twenty thousand.

polynomial · Nonlinear eigenvalue -12-10-8-6-4-2010⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹10¹⁵log₁₀ μcondition number, and relative errorκ₂, augmentedcomponentwise, condensedcomponentwise, augmentederror, augmentedone matrix, two numbersκ₂ at μ = 10⁻¹²3·10¹³componentwise, same matrix13their ratio2.3·10¹²measured error9.4·10⁻¹⁶every library prints the top lineand the error obeys the third

Two condition numbers of one matrix

κ₂ is a worst case over perturbations of a given norm, and a normwise perturbation may put its whole budget on the smallest entry. The componentwise number is a worst case over perturbations proportional to the entries, which is what a backward-stable factorisation actually makes. On one matrix they are 3·10¹³ and 13.3, and the error obeys the second.

error · Scaling the damagewell scaled, nothing done0.9110^±3, nothing done0.095never certified, of 62at 10^±3rows to unit norm0.64rows by right-hand side0.6start at the rows0.43012300.250.50.751rows rescaled by 10ᵏshare that certifiesnothing donestart at the rowsrows to unit normrows by their right-hand sidethe grey line is a well-scaled programme with nothing doneboth equilibrations are flat, and below it

Two repairs for one symptom

Rescale a quadratic programme's constraint rows over six decades and the crossover that certified its answer at iterate 1.5 first certifies at 69.8, with two of six programmes never certifying at all. Normalising the rows removes the spread completely — the same numbers at 10¹, 10² and 10³ either way. Starting the method at the magnitudes the rows imply repairs the iteration count completely and the identification only halfway. They are two repairs and they fix different halves.

constraint · Interior-point conditioning 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

Three errors and one number

This site's identity has two factors and a division of blame between them. Two fields have now added a third party and a fourth, and only one of the four is a property of anything — the others are decisions, made before the arithmetic, reported by nothing.

error · Backward error 11.31.610⁻¹110¹10²10³log₁₀ ntropical root ÷ actual modulusexactsmallest moduluslargest modulusthree norms, two endslarge root, n = 40.96large root, n = 320.94small root, n = 45.4small root, n = 32230a maximum predicts a maximumand says nothing about a minimum

An estimate that does not move

The tropical roots are said to miss the bottom of a spectrum by a factor growing like n². The estimate does not get worse. It changes by four per cent between four masses and sixty-four while the modulus it names falls by a factor of a hundred and sixty, and an estimate that is constant in the variable the answer depends on is a different defect from an inaccurate one.

polynomial · Polynomial scaling 02468101201change of units, by exponent10⁰10¹10²10³10⁴10⁶10¹⁰10¹⁶10¹⁹10²⁰10⁴⁰10¹⁵⁰as writtenafter scalinga range questionlargest finite value3.4·10³⁸predicted boundary γ1.8·10¹⁹last γ that forms10¹⁹stops where scaling fails0not a poor answerno answer at all

The units that overflow before the answer does

A change of variable that is exact in the algebra requires γ² times a matrix to be a number the format can hold. In binary64 that is a bound nobody meets by accident. In binary32 it arrives at 10¹⁹ and in fp16 at 256, and past it there is no answer rather than a poor one.

arithmetic · Overflow 012345610⁻¹10²10⁵10⁸10¹¹log₁₀ γ, the change of unitscondition numberthe linearisationthe quadraticone problem, two amplifiersκ(quadratic), first6.6κ(quadratic), last6.6κ(linearisation), last10¹²how far the first moved1the problem is as well conditioned as everand the method is not

The number that moves when the problem does

Two quantities are offered as the condition number of one eigenvalue. One is unmoved to eight digits by a change of variable that is exact in both directions, and grows like the square root of the chain's length. The other is inflated by ten orders by that change of variable, and is ten times too large before anything has been done at all.

polynomial · Linearisation backward error small group, worst backward errorleading, at 4·10¹¹2.7·10⁻⁷flv, at 4·10¹¹7.1·10⁻⁷tropical, at 4·10¹¹10⁻⁵trailing, at 4·10¹¹7.1·10⁻¹⁶both, at 4·10¹¹7.1·10⁻¹⁶10¹10⁵10⁹10¹³10¹⁷10²¹10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²separation ‖C‖²/(‖M‖‖K‖)backward errorleading reductionleading, FLV scalingleading, tropical scalingstrailing reductionboth reductionsdotted grey: u times the separationonly the trailing reduction keeps the small group

Two groups need two reductions

When a quadratic eigenproblem's tropical roots are far apart its eigenvalues fall into two groups, and the remedy offered is a second scaling — one per tropical root, each run keeping the group its root predicts. Raise the damping on an eight-mass chain until the roots are 10²³ apart and measure every eigenvalue: no scaling rescues the small group. Its backward error grows as the unit roundoff times the separation under Fan–Lin–Van Dooren's scaling, under both tropical scalings and under none, to 10⁻⁵ at a separation of 4·10¹¹. What rescues it is the other reduction of the same pencil — inverting the constant term instead of the leading one — which keeps the small group at rounding at every separation and loses the large one instead. Both reductions, each keeping its own group, give all sixteen eigenvalues to 10⁻¹¹ at worst. On the way, the closed form that served as the exact answer turned out to lose the small roots to cancellation, from the same separation.

polynomial · Polynomial scaling 0102030405060first barrier depth at which the far well is wrong by half, octavesfp16E4M3E5M2gradual underflow, from onegradual, from the topcounter, floor and ceiling9 of 9counter, window from the rates9 of 9gradual underflow, from onegradual, from the topcounter, floor and ceiling1 of 9counter, window from the rates8 of 9gradual underflow, from onegradual, from the topcounter, floor and ceiling1 of 9counter, window from the rates1 of 9ring: chains that keep the far well past sixty octavesthe window is the unbounded exponent

Room for the step, not the value

Starting a recurrence at the top of an eight-bit format's range spends its headroom once. An exponent counter beside the stored value was predicted to spend it at every step, remove every range failure and leave only the precision. Rescaled on the value — back to one whenever it nears the bottom or the top — it does not: E4M3 still loses its far well on seven or more chains of nine, because one climbing step multiplies the value by forty and E4M3 clips silently at 448. Rescaled into a window read off the chain's own rates, it reproduces the unbounded exponent bit for bit on all 531 runs of every format, and what is left of E4M3's limit is nothing.

arithmetic · Subnormals predicted against measuredproblems49worst relative difference4.4·10⁻¹⁶1.522.533.5coupling, from one to ten to the minus twelveswitching scale11e-21e-41e-61e-81e-101e-12repeatedconsistentstrainedrings: predictedevery dot inside its ringone elimination tells the switch

The switch is read before the solve

Scaling the constraint rows of a saddle-point system rescued the route to a constrained least-squares fit by changing which row partial pivoting takes at the second step. The scale at which it changes can be read before anything is solved: scaling multiplies every constraint row's candidate by s and leaves every other row's alone, so one unscaled elimination, recording the two kinds of candidate at each step, gives the switch exactly — on all forty-nine problems, to within one part in 10¹⁵ of what bisection finds, decided at the second step everywhere but at a coupling of one. A scale just past it removes the catastrophe where there was one. It does not make the route as good as eliminating the constraints first: on four problems every scale tried is thirty to thirty-nine times worse, and they are the problems where the unscaled route was too.

leastsquares · Constrained least-squares 1e-161e-121e-81e-41e0worst backward error over the groupleading reductiontrailing reductionscaled at the middle root, leadingscaled at the small root, leadingsmall groupmiddle grouplarge groupsmall groupmiddle grouplarge groupsmall groupmiddle grouplarge groupsmall groupmiddle grouplarge groupdots: worst over five cubicsthe middle group comes with the large one

The middle group needs no reduction of its own

A quadratic whose two groups of eigenvalues sit far apart needs two reductions, one per end. A cubic can have three groups, and the middle one is inverted by neither reduction, so the worry was that it would need a third route — a shift-and-invert at the middle tropical root. Build order-four cubics with three groups up to eight decades apart and measure every eigenvalue: the leading reduction keeps the middle group at 10⁻¹¹ or better at every separation, the trailing reduction loses it to 5·10⁻⁹ by eight decades, and the reversed polynomial's leading reduction, which inverts the same constant coefficient as the trailing one, keeps it at 2·10⁻¹⁴. The middle group's loss belongs to the pencil, not to the end. Two reductions still give all twelve eigenvalues to 2·10⁻¹¹. And the tropical scaling at the small root, which rescues the small group when every coefficient shares one diagonal form, does nothing for it once the coefficients are perturbed out of that form.

polynomial · Polynomial scaling the same in every columnleast squares0.32total, weighted0.11total, c → 00.16total, c → ∞0.1710⁻⁴10⁻²110²10⁴00.050.10.150.20.250.30.35factor c the first column's units are changed byrelative error, medianreverse regressionrecorded unitsleast squarescolumn 1 exactweighted by the noisedots: plain total least squaresthe units choose the answer

A unit is a statement about the noise

Total least squares minimises one Frobenius norm over every column of [A b], so the unit a column is written in is a claim about how noisy it is. On a 60-row fit with two measured regressors, rewriting one column in units from 10⁻⁴ to 10⁴ times the recorded ones leaves ordinary least squares exactly where it was and moves total least squares by half again, continuously, between two estimators with their own names: the reverse regression of that column on the others, and the fit that treats it as exact. Its correction is split among the columns as the squares of the coefficients, which the units set and the noise never enters. Dividing each column by its noise level makes every unit give one answer, the best of five estimators on all three placements of the noise tried, and two replicate readings a column are enough to get most of the way there when the recorded units were badly wrong.

leastsquares · Total least-squares

Named alongside it

The objects these essays reach for when they reach for this one.

Condition numberExact ground truthMatrix polynomialBackward errorQuadratic eigenvalue problemLinearisationForward errorTropical rootsAsymptotic analysisCompanion formFrobenius normA-priori bound

All concepts