Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Counterexample — where it appears

A constructed input on which a method fails, which is the only thing that distinguishes a heuristic that usually works from an algorithm with a theorem. It is what separates a heuristic that usually works from an algorithm with a theorem, and constructing one is the only way to establish that a bound is attained.

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

-1012301020304050log₂ of the segment lengthcolumns above 10⁻⁸cos(κr) ⁄ r at κ = 401 ⁄ r, same pointsthe case with no answerq, held fixed0.51/r at L = 0.561/r at L = 86cos(κr)/r at L = 0.512cos(κr)/r at L = 853the geometry did not moveand the rank did

The kernel with nothing to compress

Hold the geometry fixed at q = ½, fix the wavelength, and scale the picture up by sixteen. A smooth kernel needs six columns at every scale. An oscillatory one needs twelve, sixteen, twenty-two, thirty-three, fifty-three, and there is no scale at which it stops.

hierarchy · Off-diagonal rank the estimator maximises this quantity over the columns it visitscolumn 1 ‹visited›12column 2 ‹the answer›114column 311.4column 411.4column 511.4column 611.4column 711.4column 811.4column 911.4column 1011.4column 1111.4column 1211.4estimate 12.0a walk that stopped earlythe estimate returned12the true 1-norm114columns visited1products with the matrix5the walk's own stopping test firedand every column it could see was smaller

An estimate that can be fooled

Nobody computes a condition number, because forming an inverse costs more than the solve did. Every library estimates it instead, from four or five products with a factorisation already in hand. The estimate is exactly right on four random matrices out of five — and there is a matrix, three distinct entries wide, on which it returns a twentieth of the truth.

error · Condition-estimation significand bits10³10⁴10⁵10⁶10⁷10⁸10⁹10¹⁰κ(A)87892634456329625911109435761199127514162024every matrix positive definiteruns producing a false certificate14of runs in total72never above, in significand bits12first κ at eight bits10⁵the comparison was correctand what it proved was not true

Deciding that a zero has arrived

The previous tolerances were offers — accept this much error, save this much work. A detection threshold is not an offer, because both directions are failures. One matrix here has three genuinely near-invariant subspaces, and the constant somebody typed decides which of them the recurrence stops at; at eight significand bits the same kind of constant produces a proof of something false.

error · Deliberate zero 81930415263110²10⁴10⁶10⁸10¹⁰10¹²size of the matrix|rₙₙ| ÷ σₘᵢₙthe two agreec = 0.2c = 0.35c = 0.5no ceilingratio at n = 1021ratio at n = 646.8·10¹⁰interchanges, anywhere0the greedy rule never had a choiceand the gap grows with every row

The cheap rank and what it cannot see

Almost nobody computes singular values to decide a rank. The standard substitute is QR with column pivoting, read off the diagonal of R — and there is a triangular matrix on which the greedy rule makes no interchange at all, has no better column available at any step, and reports a matrix eight orders of magnitude further from singular than it is.

spectra · Rank each bar is a percentage — of the sample, or of the true condition numberexactly right86.0%inside 10%91.0%inside a factor of 291.0%worst in the sample, ×10035.7%the constructed matrix, ×1007.7%usually exactexact share0.86worst of the sample0.36the constructed matrix0.077a routine that is right most of the timeand never wrong in the safe direction

The tail a sample never reaches

Hager's estimator is exactly right on four random matrices in five, and that share is stable — between 80.5 and 87.5 per cent across nine sizes. The worst underestimate is not stable at all: it falls every time more matrices are drawn, from 0.746 at sixty to 0.377 at four hundred, and the matrix built to defeat the estimator sits five times below anything four hundred draws found.

error · Condition-estimation LAPACK's walk, exact83.0% · 5.2 productsLAPACK's walk, worst × 10037.7% · 5.2 productsblock of one, exact84.0% · 4.4 productsblock of one, worst × 10037.7% · 4.4 productsblock of two, exact96.5% · 8.5 productsblock of two, worst × 10059.6% · 8.5 productsblock of four, exact100.0% · 16.8 productsblock of four, worst × 100100.0% · 16.8 productseach bar a percentage — of the sample, or of the truthtwo random vectors close most of the tail

Two columns see what one walk cannot

The condition estimator every library ships walks from the all-ones vector, and a matrix whose largest column cancels against that vector hides from it: at n = 24 it reports five per cent of the truth. The block estimator behind MATLAB's condest walks with two vectors, the second random. On the same matrix at three sizes it is exact on every one of twenty seeds. On four hundred random 8 × 8 matrices it is exact on 96.5 per cent where the single walk is exact on 83.0, and its worst case, 0.596, is reached in the first fifty draws and not lowered by the next 1,550. The single walk's worst was still falling at 1,600. Four vectors are exact on all 400.

error · Condition-estimation pooled over every settingaccidents, one digit apart62accidents, three digits apart5relations lost on the way109110¹10²10³digits between the two searchesruns123relations keptaccidents acceptedlogarithmic vertical axiseach digit apart divides the accidents by three or four

The digits between the two searches

A lattice relation search run at N digits and again at N/10 never agrees with itself on a relation among the rounding, but it does agree on 62 approximate relations at fifteen digits or fewer — accidents that really are the shortest vector there, and that dropping a digit was said to be unable to dislodge, since a combination that cancels to D digits cancels to D − 1. It cancels, but it stops being the shortest. Two digits apart the accepted accidents fall to 17 and three digits apart to 5, while the relations kept fall from 711 of 755 to 652 and 602 — every one of the losses at fifteen digits or fewer. Past a double's sixteen digits the separation costs nothing and buys nothing.

exact · Lattice reduction fraction left after a decademedian, t = 10⁻³ → 10⁻²0.57median, t = 10⁻² → 10⁻¹0.6210⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹1110¹mixing angle terror ÷ σ₁₁median of 80single drawseach draw drops once, somewherethe median's slope is where they drop

A fade made of drops

A one-nonzero sketch's median error fell by about forty per cent for every factor of ten in how far a coherent matrix had been mixed toward an incoherent one, and nothing explained the rate. Followed one draw at a time, no draw fades at that rate. Each holds its coherent error — as large as the singular value of the direction its hash lost — and then drops, within one to three decades of mixing, never faster than one decade of error per decade of mixing. The median's steady slope is where the drops happen to fall. Change the spectrum and they fall elsewhere: at a decay of 0.9 there is no slope, only a cliff.

randomised · Randomised each steering column half the hidden oneone random vector, 34 columns: share fooled0.77block of two, 34 columns: share fooled0.64block of four, 34 columns: share fooled0.390510152025303500.20.40.60.81steering columnsshare of seeds fooledone random vectorblock of twoblock of fourdashed: the single vector's share squared and to the fourthmore columns, more seeds, same factor

Columns that steer a random start

A condition estimator whose first vector is random cannot be built against, and concentrating the hidden column did not hide it: its own entries steer the first sign vector onto it. Give the steering to other columns — each equal on both rows of every pair the hidden column alternates over — and the random start is fooled after all. The prediction was a factor of one over the square root of the number of steering columns, on a share of seeds that falls as they lose to the hidden column, and the block of two fooled as often. The factor is whatever the builder chooses; the share, at a fixed factor of one half, rises with every column added, from 9 per cent with four to 77 with thirty-four. And the block of two is not fooled as often: it is fooled on the square of the single start's share, and the block of four on its fourth power — independent guesses, which is the one thing that still works.

error · Condition-estimation exact share, points apartsize 8: random start less all-ones start0.025size 16: random start less all-ones start0.00570%80%90%100%share of matrices on which the estimate is exactsize 8size 16LAPACK's walk83.0% · 5.2 productsone walk from all ones84.0% · 4.4 productsone walk from random signs86.5% · 4.3 productsblock of two96.5% · 8.5 productsLAPACK's walk83.5% · 5.3 productsone walk from all ones83.5% · 4.4 productsone walk from random signs83.0% · 4.3 productsblock of two96.0% · 8.5 productsbars start at seventy per centthe first vector's sign pattern costs nothing

A first vector nobody can build against

The matrix built to fool a condition estimator is built against one vector, the all-ones vector its walk starts from, and the block estimator escaped it by adding a second, random one. Starting the single walk from random signs instead escapes it on every one of forty seeds at every size from 8 to 48, for the same 4.3 products, and loses nothing on random matrices — 86.5 per cent exact at size 8 against 84.0 from all ones, with tails that cross between sizes. The obvious way to build against a random start, a hidden column on few rows whose signs a random vector cancels half the time, fails on every seed: the hidden column writes itself into the walk's first product and turns the walk towards it. What the block of two's second vector buys is ten points of exact share, not the escape.

error · Condition-estimation -40-27-14-11225380123456789computed eigenvalueseedevery mark has a residual below 10⁻⁸a small residual, and no answercoefficients of det(A − λB)0worst residual over all seeds1.8·10⁻⁹spread of the answers66seeds drawn8the residual is small at every markand none of the marks means anything

A problem with no answer

If two matrices share a null vector then det(A − λB) is identically zero and every λ is an eigenvalue, which means none of them is. Perturb such a pencil by a ten-billionth and a solver returns six numbers with residuals below 10⁻⁹. Change the seed and it returns six different numbers, spread over forty-four, with residuals just as small.

spectra · Pencil ran to the end3173lucky — a subspace closed295serious, cured by a block of two495serious, cured by a longer block29serious, incurable at any length8counted, not estimatedserious, as a fraction0.13of those, cured at two0.93incurable8matrices tried4000measure zero on the realsand an eighth of the integers

The same zero, and nothing was found

Change the recurrence by two lines and the divisor stops being a norm. It becomes an inner product of two vectors from two different sequences, and an inner product of two different vectors is zero on a whole hyperplane — with neither vector anywhere near zero, nothing invariant, and nothing converged. The arithmetic event is identical and the meaning is opposite.

iterative · Breakdown 1611162126313610⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹indexmagnitude|rₖₖ|σₖone factorisation, two verdicts‖AP − QR‖/‖A‖10⁻¹⁵|rₙₙ|1.1·10⁻¹²σₘᵢₙ10·10⁻¹³column interchanges33|rₙₙ| is never below σₘᵢₙso the cheap verdict errs one way only

A good curve and a bad verdict

The diagonal of a column-pivoted R is famous for the one matrix it is wrong about. On that matrix it is right about thirty-nine of its forty entries — every |rₖₖ| within a factor of six of the σₖ it stands for — and wrong by 4·10⁶ at the fortieth, which is the only one a rank verdict ever reads.

spectra · Rank

Named alongside it

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

Condition-estimationLower boundCondition numberWorst-case analysisMatrix normNumerical rankSeeded generatorSilent failureBackward errorCertificateColumn pivotingExact arithmetic

All concepts