Numerical Linear Algebra
where the algebra stops being the arithmetic
Theme

The thread: Claims that can fail — page 12

Essays 265 to 278 of the 278 on this theme, in the same order.
longest ÷ shortesttwo rows, 12²1.5two rows, 24²1.311.11.21.31.41.5longest ÷ shortest critical path12²16²20²24²12²16²20²24²g1g2g312²16²20²24²grid, one rowgrid, level setgeometric graphgrid, two rowsdashed: every shuffle gives the same factorfree unless the separator is thick Sparsity, and what elimination costs

A clique has no order

Ordering a dissection's pieces with their separator in view cut the critical path by a quarter, and the next proposal was to order the separator's own vertices by how much fill each carries in. On every separator the dissections here produce — the grid's rows, its level-set diagonals, and the level sets of three irregular graphs of 300 vertices — twenty-four shuffles of the separator's order give the same factor to the last entry. The reason is one line of graph theory: once the pieces are eliminated, a separator whose vertices all touch one connected piece is a clique, and a clique's order changes nothing. The order matters only on a separator that is not a clique, and the one built here to be that — two grid rows thick — loses to a separator of one row under every order tried. The separator's size is the decision; its order is not one.

 at ε = 10⁻⁴tread at one, separable ÷ mixture7.7-6-5-4-3-210⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹1fraction of the isotropic kernel, log₁₀relative width of the treadtread at one, separable symboltread at one, mixturetread near 6.5, separabletread near 6.5, mixtureevery line has slope one: width in proportion to εthe width moves to the crowded tread Structure, and the solver that cannot see it

The part a circulant can cancel

A separable kernel with a small isotropic part was preconditioned by the circulant sampled from the whole mixture's symbol. The cheaper choice keeps only the separable part's symbol and leaves the isotropy as error, and the prediction was that it widens the same treads by about the same amount — the same step count to a thousandth of isotropy — and falls behind past a hundredth. The step count is the same to within one on every grid up to ε = 10⁻³, and the cheaper preconditioner is behind on every grid from ε = 0.1. But it does not widen the same treads. It puts its error on the tread at one, where sixty-four of the hundred eigenvalues sit, widening it 7.6 times as fast as the mixture's symbol does, and it leaves the tread the mixture widens most nine times narrower. The counts agree because conjugate gradients pays for the widest tread's logarithm, not for which tread it is.

 1251020shifted symmetricsmallest pivot, plainsmallest pivot, diagonal firstharmonic mean of the spectrumGram, 48 rowssmallest pivot, plainsmallest pivot, diagonal firstharmonic mean of the spectrumGram, 30 rowssmallest pivot, plainsmallest pivot, diagonal firstharmonic mean of the spectrumover the smallest eigenvaluethirty matrices a family, logarithmic axisthe pivot follows the mean, not the bottom Elimination, and the swap

A definite pivot sits at the mean

On a positive-definite matrix every Cholesky pivot is at or above the smallest eigenvalue, so a shift read off the smallest pivot always has to be pushed down, and it was predicted to need a median of four pushes and to be usable unpushed on none. The second half holds on all ninety matrices measured. The first does not: shrinking by a quarter at a time takes a median of six to ten steps, because the smallest pivot sits within a factor of two of the spectrum's harmonic mean, and the harmonic mean sits four to nine times above the smallest eigenvalue. The push was a device for the indefinite case, which has no floor to aim at. A definite matrix does, and halving towards zero gets below the spectrum in a median of two to four.

 0816243240485664reflectors appliedworst ‖Qᵀ(Qx) − x‖02·10⁻¹⁵4·10⁻¹⁵6·10⁻¹⁵8·10⁻¹⁵96 rows192 rows384 rowsmedian of five matrices, 64 columns eachlonger vectors, a higher plateau, reached as soon Orthogonality, measured

The plateau is set by the length

A Householder factor applied through its reflectors, never formed, loses orthogonality over its first twenty or so reflectors and then stops. The saturation was predicted to be a property of the vector length: on 384-long vectors the growth should continue longer before it stops. It does not. On 96-, 192- and 384-long vectors the departure reaches nine-tenths of its plateau within twenty reflectors, and on the longest it gets there soonest. What the length sets is the plateau itself — 3.6, 5.0 and 6.7·10⁻¹⁵ — which is the unit roundoff times the square root of the length, times a constant between 3.1 and 3.4. Twice the reflectors on the same length move it by nine per cent.

 λ = 105 timesλ = 9.55 timesλ = 95 timesλ = 8.55 timesλ = 2.952 timesλ = 2.92 timeseigenvalues that arrived more than once — the matrix has 40 distinct onesa spectrum with the wrong multiplicitiesextra copies, no reorthogonalisation25extra copies, full reorthogonalisation0worst relative error among the copies1.9·10⁻⁸steps taken of 80 asked for, full40no arithmetic error was madeevery one of these is right to eight digits Eigenvalues, singular values, rank

An eigenvalue that arrives twice

A matrix with forty distinct eigenvalues, handed to Lanczos for eighty steps, returns twenty-five extra copies of thirteen of them — the largest arriving five times. Every copy is accurate to 1.9·10⁻⁸ relative. No arithmetic error was made, nothing overflowed, and a caller counting eigenvalues gets the wrong multiplicity from a computation in which no individual number is wrong.

 01428425670849811210⁻²²10⁻¹⁸10⁻¹⁴10⁻¹⁰10⁻⁶10⁻²conjugate gradient iterationrelative residualthe unit roundoff, 1.11·10⁻¹⁶the answer's residualthe residual reportedtwo residuals, one runreported, at its best6.9·10⁻²¹the answer's, at its best5.1·10⁻¹⁰unit roundoff1.1·10⁻¹⁶largest iterate on the way9.3·10¹³iterations drawn110the recurrence remembers every roundingand the stopping test is written in it Iterating, instead of factorising

The residual the method reports

Conjugate gradients prints a relative residual of 6.9·10⁻²¹. The unit roundoff is 1.1·10⁻¹⁶, so that is not a small residual and not a large one — it is not a residual. The vector the method is holding at that step has ‖b − Ax‖/‖b‖ = 5.1·10⁻¹⁰, and nothing in the run says so.

 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 Eigenvalues, singular values, rank

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.

 081624324010⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²conjugate gradient steprelative residualabove, on their own scale: rank asked 5, rank kept 3solid: the budgeted residual · light: no budgetbudget 3rank asked for5rank kept3residual, budgeted3.8·10⁻⁴residual, unbudgeted1.6·10⁻¹⁴numbers stored150the step asks for moreat every step Iterating, instead of factorising

An iterate that must be made smaller

Applying a Kronecker-sum operator to a low-rank iterate multiplies its ranks by d and adding two of them adds their ranks, so a solver in a compressed format cannot keep what it produces. Every step is followed by a truncation — and whether that truncation is a floor on the residual depends on the right-hand side rather than on the truncation.

 01020304050607010⁻⁶10⁻³110³10⁶10⁹k‖Aᵏ/k!‖‖e^A‖ = 2.6largest term 1.4·10⁷what the series throws awaylargest term1.4·10⁷‖e^A‖2.6digits cancelled away5.4·10⁶error after the sum5.2·10⁻⁹every term is computed correctlyand the sum has lost seven digits Eigenvalues, singular values, rank

The error the method already knows

Summing the exponential's Taylor series throws away a known number of digits, and the number is on the machine while the sum is being formed. The largest term divided by the answer, times the unit roundoff, tracks the relative error that comes out — to within a factor of nine, across fourteen orders of magnitude of it — and nothing reports it.

 012345678910⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹rank budgetresidual the run stalls atb with no structure at allb constant: the answer is a traintwo ladders, one truncationstructured, rank 10.12structured, rank 45.5·10⁻⁶structured, rank 85.9·10⁻¹⁴unstructured, rank 10.97unstructured, rank 80.47the floor is not the truncation'sit is the answer's Iterating, instead of factorising

A run that is over at step five

A conjugate gradient whose every iterate is cut to a rank budget reaches the floor that budget allows at step 5, 36, 42 or 59, and then does nothing for the rest of the run. Four times the iterations move the floor by a factor of 1.8, and past the answer's own rank they move it the wrong way.

 10⁻¹100.20.40.60.8strength threshold θresidual reduction per cycleθ = εsemi-coarseningkept whole rowsfull coarseningone parameter, two methodsbest factor above ε0.053best factor below ε0.1the ratio across the switch231×31 anisotropic operatora switch, not a dial Iterating, instead of factorising

The switch does not know which side is better

The strength threshold moves the coarsening from full to semi at θ = ε exactly, at every anisotropy. Which of the two converges faster is a separate question with a separate answer, and it changes sign between ε = 0.33 and ε = 0.34 — where nothing whatever happens to the switch.

 10⁻³10⁻²10⁻¹1024681012size of the negative eigenvalue, −λproducts before the test firesharder to find, and milder8 spectra, n = 50products at the largest λ3products at the smallest10smallest share of λ recovered0.14largest0.34the one that hidesis the one that matters least Iterating, instead of factorising

A proof that does not ask how large the matrix is

Proving a Hessian indefinite costs three matrix–vector products when the negative eigenvalue is 3 and nine to eleven when it is a thousandth, and that pair of numbers barely moves across a fourfold range in n. The factorisation that settles the same question costs a third of n³, which grows by a factor of sixty-four over the same range.

 10³10⁶10⁹10¹²10¹⁵10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1largest iterate on the way, ‖x‖difference between the two residualsthe bound, linear in ‖x‖what it does, slope 0.46a bound of one, a walk of a halffitted slope0.46the bound's slope1smallest gap measured3.9·10⁻¹⁵largest gap measured1.5·10⁻¹⁰share of the bound, near end9.1·10⁻⁴share of the bound, far end3.4·10⁻⁹the bound is rightand loose by a square root Iterating, instead of factorising

A walk needs a length

The gap between the two residuals grows as the square root of something, and a square root needs a length. Two quantities are candidates — how far the iterates travelled and how many steps were taken — and only a second sweep separates them. Across a fourfold change in size the iteration count goes from 39 to 96 and the gap goes from 5.04·10⁻¹⁵ to 5.33·10⁻¹⁵.

 110¹00.30.60.91.2trust-region radius Δshare of the exact model decreasethe exact subproblem7 radii, n = 60share at the smallest radius0.95share at the largest0.3products, at most8radii stopped by the curvature4a few products against an eigendecompositionand most of the decrease Iterating, instead of factorising

The certificate that arrives soonest is worth least

The more negative a Hessian's smallest eigenvalue, the sooner conjugate gradients meets a direction of negative curvature — and the less of the exact trust-region decrease that direction turns out to be worth. At λₘᵢₙ = −10 the step arrives after two products and gets 39.6 per cent; at −10⁻³ the same two products get 89.8, and the whole sweep costs eight.

All themes