Numerical Linear Algebra
where the algebra stops being the arithmetic
Theme

The thread: Exact ground truth — page 5

Essays 97 to 120 of the 185 on this theme, in the same order.
at rank threelowest across tensors1highest across tensors1at rank fourlowest across tensors0.056highest across tensors0.25234500.20.40.60.81rank fittedagreement among the starts that reach itsix planted tensorsdashed: the true rankeach line one tensor, fitted at ranks two to fivefive starting points at every rank When the index is a tuple

The rank a sweep can vouch for

To decide a tensor's rank, fit it at one rank after another and stop where something changes. Three things can be read off each rank's fits — the error, how nearly parallel the terms are, and whether fits from different starting points agree — and over six planted rank-three tensors at four noise levels they decide it 24, 12 and 15 times out of 24; the ratio of consecutive errors, which needs nothing, decides it 24 times. The error is right every time and has to be told the noise level. The collinearity is a coin toss. Agreement among starts is never wrong and, under noise, cannot decide on nine of the twenty-four — and the rank past the answer, where every decision is made, costs ten times the answer.

 00.250.50.75100.51xuexact & tunedupwindcentralone of these is exacttuned, worst nodal error2.4·10⁻¹⁷upwind, worst nodal error0.14central, points outside [0, 1]16exact at every nodeand only at the nodes Iterating, instead of factorising

The diffusion that makes the answer exact

Upwinding adds h/2 of artificial diffusion. Central differencing adds none. Add ε·ξ·Pe with ξ = coth(Pe) − 1/Pe and the computed solution is the exact one at every grid point, to 2.4·10⁻¹⁷ — at every Péclet number, on the problem it was derived from and on no other.

 a triangle and a square, joinedK₂,₃ with a pendant edge1234560123456indexeigenvaluethe same, and not the samevertices each6edges each7spanning trees12spectra differ by5.3·10⁻¹⁵highest degree, left4highest degree, right3one has a trianglethe other is bipartite The matrix that is a graph

The spectrum is not the graph

Two graphs on six vertices with the same Laplacian characteristic polynomial — as integer polynomials, not to fourteen digits. One contains a triangle; the other is bipartite. Every method in this field that reads only the spectrum is answering about the class.

 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 The eigenvalue problem that is not linear

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.

 110¹10²10³110¹10²10³the accumulating quantity, relative to its first valuethe error, relative to its first valuethe bounds: slope 1what all three do: slope ½three mechanisms, one exponenta left-to-right sum0.49a chain of rotations0.55a residual recurrence0.51every bound's slope1spread of the three0.067a bound is a sum of the roundingsand the roundings have signs The arithmetic underneath

Three walks and one bound

A left-to-right sum, a chain of three thousand rotations and a conjugate gradient residual recurrence share no arithmetic and no vocabulary. Each has a standard bound that is linear in whatever it accumulates against. All three come out at a half — 0.486, 0.554 and 0.507 — and nothing is rescaled.

 each method's best, dimensionconjugate gradients24Tikhonov23truncated SVD21and the error thereconjugate gradients0.14Tikhonov0.14truncated SVD0.140510152025301effective dimensionrelative errorconjugate gradientsTikhonovtruncated SVDdashed vertical: the iteration's bestthe iteration drawn while its dimension still rises Methods that were designed apart

One arc, and what each filter pays to be on it

Conjugate gradients and Tikhonov stop at the same effective dimension, and that could have meant two curves crossing once or one curve. It is one curve over a stretch — on six problems, Tikhonov and truncation reach the iteration's error at the iteration's dimension to within 7.2 per cent from 0.7 of the answer to its top — and the two separate on either side. But the curve is shared by a trade, not by an identical answer: at the same dimension Tikhonov carries 22 to 42 per cent more noise than the iteration and up to five per cent less bias.

 worst draw on any grid, % over the oraclediscrepancy13GCV4·10⁶L-curve291median on 96 points, % overdiscrepancy3.4GCV0.18L-curve282030405060708090100110¹grid pointserror ÷ the oracle's, same drawdiscrepancy, mediandiscrepancy, worstGCV, medianGCV, worstL-curve, mediansolid: the median draw; dashed: the worst of sixteenthe axis stops at twenty times the oracle Regularisation, and the answer that is chosen

The data count their dimensions, not the step's

Every grid in the deconvolution essays was chosen with the answer in hand, and so was every λ. From the data alone, the discrepancy principle's worst draw is within 16 per cent of the oracle on every grid from 16 points to 96; generalised cross-validation is better on the median draw and, on grids of thirty points and more, has draws thousands of times worse. And the data can say how many dimensions they carry — about 20, 25 and 29 at three noise levels, one number once the grid exceeds it — but not how many more the step needs: the grid that count chooses is 14 to 19 per cent worse than forty points at the lower two.

 6 numbers, coefficients to 30relations, both agree34relations, they differ1accidents, both agree5accidents, they differ88510152025300123decimal digits the numbers are scaled togap, in digitsrelation, both agreerelation, they differaccident, both agreeaccident, they differhorizontal: a gap of one digitdashed vertical: the digits a double has Exact arithmetic, and what it costs instead

Two precisions guard the other edge

Run a lattice relation search at N digits and again at N/10, and accept its answer only if both runs return the same vector. Among six measured numbers, where the gap between the shortest and next vector vouches for one found relation in 35, the two runs agree on 34. Past a double's sixteen digits they never once agree on an accident, 0 of 561. They do agree on 62 accidents at fifteen digits or fewer — approximate relations that really are the shortest vector there — and the gap, which cannot see a relation among six numbers, can see those.

 no noisesweeps to stop49final error2.5·10⁻¹⁴1% noisesweeps to stop6000largest term, ÷ data0.67110¹10²10³10⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1sweeprelative change in the error, per sweepthe stopping test1% noiseno noise: stops at 10⁻¹⁴the clean run stops; the noisy one crawlsits terms stay the size they were When the index is a tuple

A fit that has an answer and cannot stop

Fit a noisy rank-three tensor with four terms and the prediction was that the spare term would find real structure in the noise and stop pairing off with the others. It does not: the largest cosine between two fitted terms has a median of 0.977 at 1% noise against 0.975 without noise. What changes is the solver. Without noise the four-term fit stops in fifty sweeps; with noise it never stops: its error keeps moving by a part in a million a sweep for six thousand sweeps, while on most tensors its terms stand still. The extra term takes exactly its share of the noise, and the error is settled by sweep 150.

 decay 0.8, 400 draws3% target, c = 10.663% target, c = 1.960.9410% target, c = 10.6611.251.51.7522.252.5556065707580859095100margin c on the standard errordraws inside the target, %3% target10% targeta normal tablethe dashed curve is 2Φ(c) − 1what a margin of c promises if the error is normal Randomised, and the guarantee that changes kind

The miss a normal table already priced

A trace estimator that stops when its own standard error reaches a target misses the target on about a third of draws, and the essay that measured it read the loose targets as the worst calibrated. Over 400 draws the loose target is the better covered — 76% at 10% against 64% at 3% — because the warm-up stops most of its runs with probes to spare. Where the criterion decides, the misses are a normal distribution's: a margin of c on the standard error buys what a normal table says, 94.8% at 1.96, and costs c² in probes, 3.86 times.

 heavy row first1 − h at 4³⁰7.4·10⁻¹⁸κ(A) at 4³⁰3.1·10⁸complement's error2.1·10⁻¹⁶110³10⁶10⁹10¹²10¹⁵10¹⁸10⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹weight on the rowrelative error of 1 − h1 − ‖R⁻ᵀa‖²1 − ‖row of Q₁‖²‖row of Q₂‖²κ(A)·uthe rows are the same in every positiononly the order the factorisation meets them changes Least squares, and the road not to take

The weight the factor met first

The route to one minus a leverage through the orthogonal factor was said to lose a digit for every decade of the condition number, whatever else it does. Put a weight on one row and it does not. With the heavy row first, the complement keeps every digit at κ(A) = 2.5·10⁹ while both subtractions return nothing. With the same row last it loses digits as the row's scale grows. And two heavy rows that leave κ(A) at 3.1 still lose six digits when the light rows come first. The law was about the order the factor met the rows, and the condition number had been standing in for it.

 noise none, mediansthe answer's step0fresh start, corrected6.2·10⁻⁹carried start, corrected1.3·10⁻¹¹0200400600800100010⁻¹²10⁻¹⁰10⁻⁸steps along the streamlargest relative coefficient errorfresh solve, one correctioncarried answer, one correctionfresh solve, two correctionsHouseholder on the rowseach correction contracts its start by the same factorthe nearer start wins When the problem arrives again

The answer the last window left

A sliding window that corrects its least-squares answer at every step could start each correction from the previous step's corrected answer instead of from a fresh solve: the two windows share all but one row. On a stream with any noise in it, that start is three orders worse. The window's exact answer moves by 0.79 of itself in one step at κ(A) = 3·10⁶, a fresh seminormal solve is wrong by only 1.8·10⁻⁴, and one correction contracts either start by the same factor — so the fresh start ends at 2.2·10⁻⁸ and the carried one at 3.7·10⁻⁵. Only on data that agree exactly does carrying win.

 three seeds, medianblock MGS, Qᵀb, κ 10⁸0.23block MGS, b as a block1.1·10⁻⁹Householder2.8·10⁻⁹10²10⁴10⁶10⁸10¹⁰10¹²10⁻¹⁶10⁻¹²10⁻⁸10⁻⁴110⁴10⁸κ(A)relative error of xblock MGS, Qᵀbblock CGS, either routeblock MGS, b as a blockHouseholderthe same Q in both block MGS routesonly the order in which b meets it differs Orthogonality, measured

What the appended block inherits

Modified Gram–Schmidt on [A b] solves least squares as well as Householder, although its Q is not orthogonal. A block code appends b as one more block. Block modified Gram–Schmidt inherits the rescue at every placement of the ill-conditioning: at κ = 10⁸ the appended block gives 6.9·10⁻¹⁰ where the same Q through Qᵀb gives 8.9·10⁻³. Block classical Gram–Schmidt gets the same wrong answer both ways, to the last bit. And the variant whose Q is orthogonal to 10⁻¹⁵ — two passes with Cholesky QR inside — is a hundred thousand times worse than Householder when the ill-conditioning is inside the blocks, because its R is wrong.

 κ of the suma component of b − Ax8.09·10¹⁷ad − bc, near-degenerate3.6·10¹⁶qᵢᵀqⱼ, an orthogonality check3.26·10¹⁶zᵀAz, a trace probe95.7pᵀAp, a curvature73.7rᵀr, a residual norm1measured, not assumedhighest8.1·10¹⁷lowest1above 10¹⁰3terms128sums of squares are safeand nobody decides anything from one The answer that depends on the machine

Two machines, one certificate

Nothing a solver returns says which of its answers you got. Four things could be reported instead — the summation condition number, the partition count, an exactly accumulated residual and a directed-rounding interval — and each costs about one pass over data the routine already has in hand.

 finite eigenvalues (degree of det Q)13at infinity (2n − degree)1at infinity, by the rank of M12n, if M were nonsingular14a degree, not a decisiondegree of det Q13at infinity1by the rank of M1singular-value gap∞the count is a degreeand the other route is a judgement The eigenvalue problem that is not linear

One mass removed, and one eigenvalue gone

A coordinate with no inertia reads like a coordinate that has been deleted, and a chain of eight masses with one of them removed would then be a chain of seven, with fourteen eigenvalues. It has fifteen. The massless coordinate is still there, still carrying a damper, and it contributes a first-order equation rather than none.

 10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²10⁻¹⁴10⁻¹10¹²10²⁵10³⁸10⁵¹10⁶⁴δ, the gap between consecutive eigenvaluesrelative error in eᴬan answer with no correct digitsV f(Λ) V⁻¹scaling and squaring‖A(δ) − A₀‖exact eigenvalues throughoutκ(V) at the smallest δ3.3·10⁸²eigen route2.9·10⁶⁵scaling and squaring4.1·10⁻¹²distance to the limit7·10⁻¹²the eigenvalues are the diagonaland they are exact at every stop Eigenvalues, singular values, rank

A function of a matrix is not a function of its entries

Everybody learns that f(A) means diagonalise, apply f to the eigenvalues, undiagonalise. That is a definition, not a method. On a matrix seven picometres from a defective one — with exact eigenvalues and eigenvectors from a closed form — the definition returns an answer wrong by sixty-five orders of magnitude, and a method that never mentions an eigenvalue returns the right one.

 Re λIm λwhat survives the arrowsvertices18arcs18worst row sum0worst column sum0largest |Im λ|0.98asymmetry1the null vector is still exactand nothing else about the spectrum is real The matrix that is a graph

A Laplacian that is not symmetric

Point the edges and the matrix stops being symmetric. Its row sums are still exactly zero, so the null vector survives; everything built on the quadratic form does not, and the eigenvalues need a plane rather than a line. Asymmetry permits that and does not force it, which the smallest case here demonstrates by being asymmetric and real.

 heavy row firstresidual at 4³⁰-2.8·10⁻¹⁰complement's error9.1·10⁻¹⁶110³10⁶10⁹10¹²10¹⁵10¹⁸10⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹weight on the rowrelative error of its residualb − Axb − Ax, exactlyQ₂Q₂ᵀbu·wthe same rows, the same data, in every positionthe solution misfits the heavy row by its own rounding Least squares, and the road not to take

The residual the solution cannot hold

Sorting a weighted fit's rows heaviest first gave every digit of one minus the heavy row's leverage back. It gives nothing back to the heavy row's residual, if that residual is computed the way every textbook computes it — as the datum minus the fitted value. The fitted value is a double, and a double cannot resolve a misfit smaller than its own last digit times the weight: at a weight of 4²⁴ the residual formed from the solution is wrong in its second digit in every order, and forming the subtraction exactly changes nothing. Taken from the same orthogonal factor as the divisor, the residual keeps fifteen digits, and so does Cook's distance at 3.4·10¹⁷.

 sum with overshoot clippedwidest departure, 1.1 to 1.30.17widest departure, 0.3 to 0.50.690.30.50.70.91.11.30.7511.251.51.7522.252.5clipped sum ÷ the answer'serror ÷ the iteration'sTikhonovtruncated SVDshaded column: 0.7 to 1.0 of the answerthe axis decides the band above the top Methods that were designed apart

The overshoot was the lead

Past its best, conjugate gradients' error rose more slowly than Tikhonov's at the same effective dimension — on the narrow blur at 0.1% noise Tikhonov was 2.35 times worse at 1.3 of the answer — and the reading was that the iteration spends its dimension where the data has content. Count admitted directions instead of summing factors, so that a factor of 1.81 counts once, and the lead is gone: 0.96 on that problem, and within 0.17 of one on all six from 1.1 to 1.3. Tikhonov now carries less noise than the iteration there. Below half the answer, where the three filters also disagree, the count changes nothing.

 worst draw on any grid, ÷ the oracleGCV4·10⁴rightmost minimum1.6discrepancy1.1draws more than twice the oracleGCV10rightmost minimum02030405060708090100110¹10²10³10⁴grid pointsworst error ÷ the oracle'sGCV, worst drawrightmost minimumdiscrepancythe worst of sixteen draws on each gridthe axis stops at ten thousand times the oracle Regularisation, and the answer that is chosen

The minimum on the right

Generalised cross-validation's worst draws on a fine grid were all one mistake: a second dip in its function at λ near zero, deeper than the real minimum. The proposed repair was a residual threshold, one number, refusing any λ whose residual falls too far below the real minimum's. Measured over 528 draws, a threshold of one half still lets two hundredfold misses through; only the extreme value, which is no threshold at all but the rule 'take the rightmost local minimum', removes all eleven. It costs nothing on the coarse grids where the dip is the right answer, and on the collection's own problem over five thousand draws it turns 243 tenfold misses into 17.

 7 tensors, 60 networksτ = 2, networks exact46constant 8, networks exact4210²0102030405060pairings pricednetworks exacttie-widened, τ 0 to 8constant width 1 to 8wide late, two ratesup and to the left is betterwidth spent where the ranking is uncertain Where the flop count stopped predicting the time

A near-tie is a factor of four

A beam over contraction orders spends its width by level — wide late was the best schedule, finding the exhaustive order on 37 of 60 seven-tensor networks for 78 pairings priced. The alternative was to widen only where the ranking is a near-tie. Measured, near-ties buy nothing: keeping every candidate within a quarter of the best changes nothing at all, because the pairing the exhaustive order wants is almost never tied with the ranking's first choice. It sits a factor of two to four further down. Widen to keep everything within a factor of three and the beam finds the exhaustive order on 46 networks for 150 pairings, and at nine tensors has a median of 1.007 where every schedule tried before had 1.056 or worse below 1,380 pairings.

 ties broken by 10⁻¹²one step ahead, n = 248.4·10⁶two steps ahead, n = 2424812162024110¹10²10³10⁴10⁵10⁶10⁷matrix size ngrowth factorgreedyone step aheadtwo steps aheadone step ahead lies exactly on greedythe damage is done a step before it shows Elimination, and the swap

One step ahead is one step short

Partial pivoting takes the largest entry in the column and, on Wilkinson's matrix, walks into growth of 2^(n−1) that a cyclic shift of the rows avoids entirely. A rule that chose instead the pivot whose elimination leaves the smallest trailing submatrix was expected to see the good order at the first step. It sees nothing there: every first pivot leaves a largest entry of exactly 2, and with the ties broken by 10⁻¹² it prefers the greedy row by 10⁻¹². It attains 2^(n−1) at every size. Looking two eliminations ahead, the greedy row scores 4 and every other row 2, and the growth is 2 at every size up to 24. On random matrices one step of look-ahead helps below n = 16 and is worse than greedy on more than half of them by n = 32.

 largest pivot, area1.037largest pivot, cost1.293smallest pivot, area0.969smallest pivot, cost0.704shortest row, original, area0.966shortest row, original, cost0.841shortest row, current, area0.964shortest row, current, cost0.760over the natural order: below one is cheaperthe rules agree on area and part on cost Exact arithmetic, and what it costs instead

The pivot is in every product

A fraction-free elimination's intermediates are minors, and Hadamard bounds a minor by the lengths of the rows it is made of — so the rule that picks the smallest pivot entry looked like a proxy for a rule that picks the shortest row. Measured, the two keep the bit-length profile equally low: 0.969 and 0.966 of the natural order's area. They part on what the arithmetic costs. Counting every multiplication and division at the product of its operands' lengths, the smallest-pivot rule costs 0.70 of the natural order and the shortest-row rule 0.84, because the pivot multiplies every entry of the step and divides every entry of the next. Three per cent of area is thirty per cent of arithmetic.

 tol 10⁻⁸unguarded inner iterations1109c = 1, error ÷ unguarded497910⁻²10⁻¹110¹10⁻¹110¹10²10³10⁴10⁵c, the floor's constantover the unguarded runerror ÷ unguardedinner iterations ÷ unguardedopen dots: the run did not convergea trade with no knee, and then a cliff When the problem arrives again

A floor with a cliff at one

Inexact Newton's adaptive forcing rule is used with a floor: never ask the inner solve for less than c times the outer tolerance, relative to the current residual, with c a half. Swept from a hundredth to ten, the constant trades with no knee at all — the forward error rises in proportion to c, the inner work falls by a few per cent a decade — and then, just past one, the run stops converging: at c = 3 it hits the outer limit on four problems of five, having asked every step for less than the stopping test needs. And the accuracy the floor gives up at c = ½ is no planning number: across five problems and four tolerances it runs from nothing to a factor of 48,000.

All themes