Numerical Linear Algebra
where the algebra stops being the arithmetic
Theme

The thread: Claims that can fail

An assertion is evidence only if it can fail. Every check on this site is fed a counterexample somewhere in the build — the orthogonality test is shown a shear, the reconstruction test is shown the wrong matrix, the growth measurement is shown Wilkinson's matrix — and the build fails if any of them accepts.
051015202530354010⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹singular value, in orderσ ⁄ σ₁eight digitsan independent draw per entry1 ⁄ ra cliff, and a control1/r rank at 10⁻⁸5log r rank at 10⁻⁸5noise rank at 10⁻⁸96σ₂ ⁄ σ₁0.024σ₆ ⁄ σ₁2.8·10⁻⁹the block has full rankand five useful columns Neither sparse nor dense

A block nobody can call sparse

A 96 × 96 block of a kernel matrix has ninety-six nonzero singular values and five that matter. It has no zero entries, it is not described by fewer numbers than it contains, and neither of the two ways this collection already knows to make a large matrix affordable applies to it.

 04812162010⁻¹10⁻⁰.⁵1target rank k‖A − Aₖ‖₂published boundrandomisedσₖ₊₁, optimalhow far apart the three areworst seed spread1.6bound / median at k = 125.9median / optimum at k = 121.960×60, 6 seeds, oversampling p = 5band is best to worst Randomised, and the guarantee that changes kind

A bound that holds with probability

Every other guarantee in this collection is deterministic. The randomised low-rank approximation offers one that holds with a probability, the seed changes the answer, and the honest figure is a band rather than a line.

 110¹10⁴10⁵block size bwords movedthe count: √(M/3) = 5measured best: b = 8words movedat the best block1.6·10⁴at b = 13.9·10⁴at b = 243.9·10⁴derived from M with no measurement, and scannedthe two agree Where the flop count stopped predicting the time

A block size is a property of the machine

Three lines of counting say the best block size is √(M/3). Scanned over every integer at five fast memories, the measured optimum is √M − 2 — exactly, at all five. The count has the right scaling and the wrong constant, low by a factor of 1.56, and the wrong form: the answer is affine in √M rather than proportional to it.

 10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³110⁻⁴10⁻³10⁻²10⁻¹1inner tolerance η, relative residual of the linear solvedistance from the root after the stepd² = 0.00138distance before the step, 0.03721093547231126the number by each point is the iterations it costeleven decades, one landing placedistance before the step0.037its square0.0014where η = 10⁻³ lands0.0025where η = 10⁻¹⁴ lands0.0025iterations for the first354iterations for the second1126the accuracy that is thrown awaymeasured against a root that is known When the problem arrives again

The accuracy that is thrown away

A Newton step is the exact answer to a linearised problem, and the linearisation is wrong at second order. So there is a floor under how close the step can land, the floor is the square of where it started, and eleven decades of inner tolerance below it buy the same four digits at four times the price.

 natural1739reverse Cuthill–McKee1354minimum degree1026nested dissection1413matrix: 408 entries · dense factor: 10440bandwidth 12 · 4.26× the matrixbandwidth 12 · 3.32× the matrixbandwidth 123 · 2.51× the matrixbandwidth 108 · 3.46× the matrixn = 144, five-point stencilevery ordering fills in; none avoids it Sparsity, and what elimination costs

The order decides the memory

Four elimination orderings on one matrix give factors of 1,739, 1,354, 1,413 and 1,026 entries. All four factorisations are exact, all four return the same answer, and the one with the better asymptotics is not the one that wins.

 [ ε 1 ; 1 1 ] x = [ 1 ; 2 ], exact answer (1.000000, 1.000000)with partial pivoting1101U after elimination1.0000001.000000computed xbackward error 0forward error 0without10⁻¹⁷10-1·10¹⁷U after elimination0.0000001.000000computed xbackward error 0.25forward error 0.71no error is raisedgrowth 10¹⁷ Elimination, and the swap

The swap that is not optional

Run elimination without a row interchange on a matrix that needs one and nothing announces a failure. There is no division by zero, no warning, and an answer of the right shape. It is simply wrong, and how wrong depends on a number you did not look at.

 1-2-6-7-474-26-12-5-8-524-394151435A, the matrix as given1-2-6-7-401840552700112217207003943011710017279153after 2 fraction-free steps3 × 3 minors25 divisions, all exactthe intermediates are minorswhich is why the divisions come out whole Exact arithmetic, and what it costs instead

Every intermediate is a minor

Fraction-free elimination divides by the previous pivot at every step and the division is always exact. Not usually, not for these entries — always, because the number being divided is a determinant with that pivot as a factor, which is a theorem and is checked here against the minors themselves.

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

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.

 05101520253010⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹iteration‖RᵀR − I‖ and ‖r‖/‖b‖step n‖RᵀR − I‖residual30×30, run for exactly n stepsexact arithmetic would end here Iterating, instead of factorising

An orthogonalisation nobody calls one

Conjugate gradients are derived as a minimisation and behave as an orthogonalisation, which is why the finite-termination property in every textbook is not a property the method has in floating point.

 45678903691215log₂ of the points a sidecolumns above 10⁻⁸two intervals that touchtwo that do notthe measurement that is a null resultadmissible, n = 325admissible, n = 2565touching, n = 329touching, n = 25613stored ⁄ dense at largest0.039the rank belongs to the geometryand not to the sampling Neither sparse nor dense

The size the rank does not notice

Sample a kernel block at 32, 64, 128 and 256 points a side and it needs five columns, five, five and five. Sample the touching block next to it at the same four sizes and it needs nine, eleven, twelve and thirteen. Same kernel, same accuracy, one number and a logarithm.

 the matrix43 entriestip eliminated first253 entriestip eliminated last43 entries‖A − LLᵀ‖/‖A‖, tip first1.4·10⁻¹⁶‖A − LLᵀ‖/‖A‖, tip last0dense factor is n(n+1)/2 = 253 · sparse factor is 2n − 1 = 43one row swapped to the endnothing numerical chose between them Sparsity, and what elimination costs

Two ends of the same arrow

One matrix, one row moved from the front of the elimination order to the back, and the factor goes from completely dense to no fill at all. Both factorisations are exact to rounding, and nothing numerical chose between them.

 0816243240110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴matrix size ngrowth factor max|u| / max|a|the 2ⁿ⁻¹ boundworst of 30 randommedian randomWilkinson's matrix sits on the bound30 Gaussian matrices per sizeat n = 40: bound 5.5·10¹¹, worst 4.8 Elimination, and the swap

The bound that is never attained

Partial pivoting's stability guarantee permits the entries to double at every step — a factor of 5.5·10¹¹ at n = 40. The measured growth on random matrices of that size is about three. The gap is eleven orders of magnitude, and the guarantee is still worth having.

 110¹10²10³10⁻³10⁻²10⁻¹110¹10²10³n‖Aₙ − A‖ and the largest term's norm‖Aₙ − A‖the larger of its two termsan infimum that is not attainedn1024‖Aₙ − A‖0.0017largest term1024their product1.7√31.7the distance goes to zeroand nothing reaches it When the index is a tuple

A nearest point that is not there

Eckart and Young guarantee that a matrix has a best rank-k approximation and that the truncated SVD is it. For three indices the guarantee is false in the strongest available way — there are tensors whose distance to the rank-two set is zero and which no rank-two tensor equals.

 10²110¹10²size niterations to 10⁻¹⁰λₘᵢₙ(C) changes signno preconditionerStrang's circulantthe preconditioner's own spectrumλₘᵢₙ(C) at n = 16-0.4λₘᵢₙ(C) at n = 32-0.14λₘᵢₙ(C) at n = 640.016λₘᵢₙ(C) at n = 1280.051λₘᵢₙ(C) at n = 2560.053left of the line the repair costs stepsright of it, the count stops counting n Structure, and the solver that cannot see it

A preconditioner that changes sign

Strang's circulant preconditioner takes Toeplitz conjugate gradients from 179 steps to 10 at n = 256. At n = 64 on the same family it takes 66 steps to 109 — worse than doing nothing. Between those rows the preconditioner's smallest eigenvalue crosses zero, and nothing in the published account of the method mentions that it can be negative.

 10⁻²10⁻¹110¹10²10³10⁴‖Ax − b‖‖x‖the oraclediscrepancyL-curvegeneralisedscored against a truth none hasoracle, relative error0.11discrepancy principle, as a multiple1.1L-curve corner, as a multiple2.3generalised cross-validation, as a multiple1the oracle needs the exact answer and is not a methodit is the reference the others are scored on Regularisation, and the answer that is chosen

Choosing without knowing

Three published rules for choosing a regularisation parameter, scored against an oracle that requires the exact answer and is therefore not a method. Generalised cross-validation lands on the oracle's λ exactly; the discrepancy principle costs 6%; the L-curve costs 129%. And told a noise level ten times too small, the discrepancy principle's error goes from 0.112 to 10,449.

 04812162010⁻¹10⁻⁰.⁵1target rank k‖A − Aₖ‖₂published boundrandomisedσₖ₊₁, optimalhow far apart the three areworst seed spread1.1bound / median at k = 1211median / optimum at k = 12160×60, 6 seeds, oversampling p = 5band is best to worst Randomised, and the guarantee that changes kind

Randomisation does not create structure

On a matrix whose singular values are all equal, a rank-ten randomised approximation has error 1.0 — and so does the optimal deterministic one. Neither achieved anything, and only one of them is usually sold with the implication that it might.

 the matrix105 entriescorner first — sparsest227 entries, growth 1.9·10¹¹largest first — safe242 entries, growth 1.19the middle factor is the smaller one, and its answer has no correct digitsboth factorisations reproduce the matrix‖PA − LU‖/‖A‖, sparsest3.8·10⁻¹⁷‖PA − LU‖/‖A‖, pivoted5.4·10⁻¹⁷forward error, sparsest3·10⁻⁵forward error, pivoted4.8·10⁻¹⁶red marks are entries elimination createdthe fill argument and the stability argument disagree Sparsity, and what elimination costs

Structure and stability stop being separable

The sparsest variable to eliminate on this matrix has a diagonal entry of 10⁻¹². Eliminating it produces the smaller factor, reproduces the matrix to 3.8·10⁻¹⁷ — better than pivoting does — and returns an answer wrong in the fifth digit.

 0357010514017521024528010⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹iteration|subdiagonal entry|no shiftRayleighWilkinsontwo routes to one raterate, from the spectrum0.9rate, measured0.9iterations, none / Wilkinson45symmetric 4×4, spectrum 8, 4, 2, 1.8the dashed line is the prediction Eigenvalues, singular values, rank

The algorithm the libraries actually run

Factorise, multiply the factors back in the other order, repeat. That description is complete and correct and produces something nobody would use — on a matrix with eigenvalues +1 and −1 it does not converge at all, and the subdiagonal entry does not move by so much as a rounding error.

 036912151821242700.250.50.7511.25index kweight appliedonebidiagonalArnoldiis it a function of σmisfit, even fit1.6·10⁻¹²misfit, general fit0.063‖A − Aᵀ‖/‖A‖0.086one method's weights do not notice the operatorand the other's stop being a function of σ Regularisation, and the answer that is chosen

The basis decides what a filter is

The vocabulary of regularisation is spectral — a method keeps a component or discards it, and the weights are a function of the singular value. Row-normalising a symmetric blur so that it preserves a constant makes it 8.6% asymmetric, and that is enough to move GMRES's weights from 7·10⁻¹⁴ off a function of σ to 4.4·10⁻².

 -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 Neither sparse nor dense

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.

 0481216202428321rank keptrelative errormedianthe answer movesspread at rank 81.8spread at rank 241best median error0.14widest where the method is worstand the bound does not say so Methods that were designed apart

An answer that changes with the seed

A randomised rank-k solve is a truncation computed in a random subspace, and it reaches the same floor as the deterministic ones. What it does not do is return the same answer twice — a factor of 1.84 across four seeds at rank 8, and 1.02 at the rank where the method is best.

 34567891011110¹10²nbitsthe budget and what it buysrandom, bound47random, actual33primes needed2Hadamard n = 8, bound13Hadamard n = 8, actual13the count is decided by a theorembefore any arithmetic happens Exact arithmetic, and what it costs instead

How many primes the answer needs

Work modulo a word-sized prime and no intermediate can exceed twenty-six bits, whatever the matrix does. The catch is that the answer must be reassembled from several such computations, and the number of them has to be fixed before the first one runs — by a theorem about how large a determinant can be, not by trying more until it settles.

 024681012141618202210⁶10⁷10⁸members served by one factorisationmultiplications for the whole sequencedoes not convergethe contraction ruledrift 0.01 a memberevery member1.6·10⁷every 5 members9.3·10⁶contraction rule9.2·10⁶its factorisations4cliff at a period of20a factorisation has a shelf lifeand the cliff is past the optimum When the problem arrives again

A factorisation kept past its date

One Cholesky factor can serve five members of a drifting sequence and save 44 per cent of the work. Kept for twenty it does not lose accuracy — it stops converging altogether. The optimum and the cliff are four members apart, both move with the drift, and a rule written in a ratio the iteration has already computed finds them without being told what the drift is.

 1112131415193111.365129.731148.096166.461probes takenrunning estimate of the tracenormal±1one probe, no errorthe exact trace99±1 variance, this matrix0±1 variance, rotated57normal variance545the same spectrum in a general basiscosts the ±1 probe its whole advantage Randomised, and the guarantee that changes kind

Counting what cannot be looked at

The trace is n additions and one of the most expensive quantities in the subject to estimate, because the matrices whose trace is wanted are never stored. Hutchinson's estimator is unbiased with one line of algebra — and its variance depends on which random vector is used, by a factor that is a property of the matrix, and on a diagonal matrix one choice is exact from the first probe and the other is not.

All themes