The thread: Claims that can fail — page 8

Elimination, and the swap

A trigger finer than the growth

Threshold pivoting cannot remove the shooting matrix's growth of 1.1·10⁴, because at τ = 1 it is partial pivoting. The proposal was a factorisation that notices growth on a step and searches as rook pivoting does after it, paying for the stricter search only where growth is made. But no step makes much: the largest one-step rise is exactly the growing mode's rate over one shooting interval, 1.284 at a step of 0.3, and 1.133 at 0.15. A trigger finer than that rate holds the growth at 2.00 for about two thirds of rook's extra search; one coarser never fires. And a trigger fine enough searches as rook on a quarter of an ordinary random matrix's steps.

The matrix a constraint makes

The right-hand side that hides the saddle

Refinement against an unregularised saddle-point matrix gives the second-order verdict the pivot signs cannot, from step 62 on the shallowest saddle — for one right-hand side. The verdict depends on how much of the growing direction the right-hand side contains, and it can contain none. Each decade removed delays the verdict by a fixed number of steps, 147 on the shallowest saddle, set by the growth against the minimum's slowest contraction rather than by the growth alone, which predicted 1,611. Rounding stops the hiding at about 2,700 steps — but by then refinement has solved the system to a residual of 2.6 times ten to the minus thirteen, and any stopping test has already accepted it. A random kick to the starting point costs nothing and finds it.

Exact arithmetic, and what it costs instead

What reading the next pivot buys

In a fraction-free elimination every pivot is paid for twice — it multiplies every entry of its own step and divides every entry of the next — and the rule that picks the smallest pivot entry left a median 20 per cent above the least arithmetic any row order reaches. A rule that charges two steps ahead brings the median matrix to within 2.5 per cent, and on one matrix of twenty-four costs 1.87 times the least, worse than the smallest pivot ever does. Charging three steps ahead finds the least of all 40,320 orders on thirteen matrices and is never more than 27 per cent above it. And none of it pays: choosing that way costs forty to two hundred and sixty times the elimination it chooses.

Eigenvalues, singular values, rank

The vector was what was wanted

Nobody who computes a matrix exponential wants the matrix. They want eᴬᵗb — one vector, the state of a system at a later time. Twenty matrix–vector products get it to sixteen digits on a hundred-by-hundred problem, without ever forming a hundred-by-hundred exponential, and the exponential that does get computed is twenty by twenty.

The eigenvalue problem that is not linear

Where a contour's budget should go

A contour method's ceiling is the number of probes times the number of moments, and the moments are free in solves while the probes are not. Four ways of reaching one ceiling come out four orders apart, the ordering is not monotone, and what separates the best two is not the usual draw but the unlucky one.

The arithmetic underneath

The well on the far side of the band

Gradual underflow was said to buy a predicate and not an answer, because a quantity that has decayed into the subnormal range is already lost. A quantity that passes through the band on its way somewhere else is not. The stationary distribution of a two-well chain, computed in half precision across a barrier whose top is two to the minus sixteen of the near well, keeps its far well's probability of 0.2454 to three digits with subnormals and returns exactly zero without them. The normwise backward error calls both answers exact.

Two errors, and whose fault they are

Balanced is not symmetric

The Sylvester–Kac matrix is made of small integers, so a double holds it exactly, and its eigenvalues are the integers from −(n − 1) to n − 1 in steps of two. Every digit an eigensolver loses on it is therefore the solver's own, and it loses them at exactly the rate first-order perturbation theory predicts: the median error is half the prediction across 1,568 eigenvalues. Balancing, the preprocessing libraries apply for this kind of matrix, divides every condition number by about sixty and leaves their growth untouched, and at order 112 the unbalanced solver returns eighteen complex eigenvalues for a spectrum of integers.

The matrix that is a graph

A finer invariant that hears less

The Laplacian spectrum fixes a graph's number of spanning trees and not the group those trees form, so the Smith normal form of the grounded Laplacian is a strictly finer integer invariant — and on the six-vertex pair the spectrum cannot separate, it does: ℤ₁₂ against ℤ₂ ⊕ ℤ₆. Over all 1,022 Laplacian-cospectral pairs of connected graphs on eight vertices it separates 435. The adjacency polynomial, a second spectrum rather than a finer one, separates all of them.

Neither sparse nor dense

The smaller cluster sets the rank

An oscillatory kernel block between two equal clusters needs a rank that grows without limit as they grow. Make the clusters unequal at the same separation ratio and the rank stops following the larger one: a target an eighth long against a source of four needs 8 columns where the square block of side four needs 33, and a target a third long against a source 130 wavelengths long needs 11. What decides the rank is the product of the two lengths over their distance — the Fresnel number, the count optics gives for the waves two apertures can exchange.

Least squares, and the road not to take

The degree that is safe to overshoot

The rules that choose a Tikhonov parameter miss by factors of millions on one draw in twenty. Transplanted to the degree of a polynomial fit, in a basis orthonormal on the data, the same rules never cost more than 2.7 times the best degree's error in three hundred draws. The reason is the shape of the valley they search: six degrees too few costs from 44 to 16,000 times the best error, forty degrees too many costs about twice it. The one rule with a tail, the discrepancy principle, has its threshold half a standard deviation above the residual it is waiting for.

Elimination, and the swap

Where the multipliers go

Bunch–Kaufman bounds the growth in D and not the entries of L, and the warning attached to that is that everything which later uses the factors inherits the size of L. On a matrix built to make those entries 1.2 over ε, they reach 1.2·10¹⁰ while the solve's backward error stays at 1.6·10⁻¹⁶, |L||D||Lᵀ| stays at 6.7 times ‖A‖, and a step of refinement changes nothing. The large multipliers are where the rule has put the matrix's ill-conditioning. A direction of negative curvature read from those factors finds 7·10⁻¹⁶ of the curvature that is there; the bounded rule's finds 13%.

Exact arithmetic, and what it costs instead

The field decides it, usually

A matrix whose rank depends on the field it is read over was built, the first time, from its invariant factors outward, because random integer matrices never seemed to show the effect. Random 0/1 matrices show it at almost every size that is not tiny. At twenty rows, 99.8% of them are invertible over the rationals, 29% modulo two, 56% modulo three — and 71% of the ones the rationals call invertible are singular modulo two. Modulo two they obey, corank by corank, the law for uniformly random matrices over that field; modulo three and five, which their entries cannot fill, they converge to that field's law anyway.

Randomised, and the guarantee that changes kind

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.

Regularisation, and the answer that is chosen

A third penalty on a flat floor

Two penalties at once were worth three per cent at most, and the explanation offered was that one penalty already does the work — which predicts that a third buys less still and that the best choice sits on a face of the parameter cube. The third buys a median of exactly nothing on all five signals and 0.66% on its best draw. But on twelve draws of forty the best triple does use all three, and on every one of them the nearest point with a penalty switched off is within that same 0.66%. The minimum is not on a face; it is on a floor so flat that where it lands is noise. Choosing the right single penalty is worth a factor of two.

Structure, and the solver that cannot see it

Where one step stops being enough

One step of iterative refinement took the squared Laplacian's circulant-wrap solve to elimination's accuracy at every size, and the account was that each step multiplies the error by the wrap's condition number times the rounding, so one step suffices while that product is small. Raised to higher powers, the band tests the account and half of it holds: each step does contract by about κ(wrap)·u. The other half fails. The fifth power at sixteen points needs three steps with κ(wrap)·u near 10⁻⁶, where the third power at 128 points needs one with thirty times more, because the first solve starts up to a thousand times further from the answer than κ(wrap)·u says.

Where the flop count stopped predicting the time

The circle between two eigenvalues

A contour count's error is not approximately governed by the nearest eigenvalue; it is exactly one closed-form term per eigenvalue, and summing those terms reproduces the quadrature to a millionth at 1,720 radius and point pairs. Three things follow. The rate is the ratio of the two moduli the circle sits between, not a distance, so two circles 0.2 from their nearest eigenvalue converge three times apart. Ten digits cost about 21 points divided by log₁₀ of that ratio, 71 points with twelve eigenvalues inside and 3,476 with six. And the best circle is not halfway: at the geometric mean of two eigenvalues on one ray their two terms are equal and opposite, and ten digits cost 27 points where the midpoint needs 84.

Orthogonality, measured

The factor nobody forms

A blocked Householder factorisation's orthogonal factor, multiplied out, departs from orthogonality half as far in blocks of sixteen as one reflector at a time, and that was read as blocking buying a factor of two. Libraries do not multiply it out. Applied to vectors through its stored blocks — which is how every caller uses it — the same factor departs by 3.1 to 4.0·10⁻¹⁵ at every block size from one to sixty-four, and stops growing after about twenty reflectors instead of adding them up. The factor of two was the price of forming the product, and a factor that is never formed never pays it.

Sparsity, and what elimination costs

Pieces ordered blind

One level of nested dissection followed by minimum degree lengthened the factorisation's critical path, and the blame moved from the separator to the halves: minimum degree's path through a 12 × 24 half was longer than through the whole 24 × 24 grid. A 12 × 24 grid on its own has a path of 12,913, a third of the square's. What made the half expensive is that it was ordered as if the separator were not there. Count the separator's vertices in every degree and number them last, and the depth-one path falls from 53,508 to 41,050 — minimum degree's own — while the pieces' own arithmetic does not change at all. At depth two the same ordering beats full dissection.

Methods that were designed apart

The first step's filter, kept for the whole run

Conjugate gradients' first step applies a ramp — Tikhonov's slope up to a corner, then one — and the essay that found it proposed the ramp as a fixed method, predicting that it would match the iteration below half the answer better than any sharpened Tikhonov and lose the match near the answer. The first half holds by more than predicted: 0.044 from the iteration below half, where the best member of the family was 0.106. The second does not: near the answer the ramp is within 0.016, closer than any filter measured. And two numbers read off the iteration's own Ritz values — its tail's slope and its smallest Ritz value — reproduce it past the top as well, where every fixed filter falls ten to seventeen per cent below it.

Reduction, and what a model is for

Where a ringing mode stops being a pair

A lightly damped mode puts two nearly equal Hankel singular values into balanced truncation, and the reduction error was read as twice the larger of the first pair cut — right to two per cent at damping 0.01, wrong by half at 0.1. Read instead as the pair's two values added, the error is right to within six per cent at every order up to damping 0.05, and the pair's split turns out to be twice the damping. What it cannot do is say when the reading fails. The split predicts nothing: the widest split at damping 0.1 has the best reading. The failures come from somewhere the pair does not look — the other dropped modes' response under the peak, and a cut between two singular values that agree to under one per cent, which left a reduced model with a pole a thousand times closer to the axis than any pole of the system it came from.

Where the flop count stopped predicting the time

The short leaf belongs at the bottom

A recursive LU that cuts every dimension at a multiple of the cache's edge moves 14 to 21 per cent fewer words than the pure recursion, except where one leaf per dimension has to be short — and the one-column leftovers cost the most. Moving the short leaf to the top, where it becomes a thin strip of a large product, was predicted to cure that. It makes it worse on all twenty-nine sizes that have a leftover, by up to three hundredths. The measurement that matters more is the edge itself: one column under it the aligned cut keeps most of its saving, one column over it every size costs two and a half to three times the pure recursion. Halving to the same base case barely notices either mistake.

Neither sparse nor dense

One build tells the leaf

The rule that picks a hierarchical matrix's cheapest leaf — halve it while the rank at half the leaf is below a quarter of the leaf — reads ranks that exist only after the matrix has been built at every candidate leaf. Fed instead the rank a code can guess from the tolerance alone, one rank per two decades, it names the best leaf on twenty-three cells of thirty, and on the rank-one kernel it cannot see it stores up to seventy-two per cent too much. Doubling the guess for an oscillation, as earlier measurements suggested, makes it worse: eighteen of thirty. Building once, at a single leaf, and holding that build's mean rank fixed names the best leaf on twenty-nine — one more than the rule that builds at all five — and never stores three per cent more than the least.

When the index is a tuple

A fit with no answer to find

Half of all random 3 × 3 × 2 tensors, and most larger ones, have no rank-three decomposition, because their pencil has a complex pair. A rank-n fit to one of them does not wander and does not stall. Two starts settle at the same error to five digits, and that error is the distance from the tensor to the surface where its pencil has a double eigenvalue — found with no fitting at all, and matched to within one and a half per cent. Meanwhile the fit's terms grow without limit, like the square root of the sweep count, while the fitted pencil's two closest eigenvalues close on each other at exactly the rate the terms grow. The error has an answer; the decomposition does not.

The matrix a constraint makes

One hyperplane hides nothing

Iterative refinement against a saddle-point matrix gives its verdict when the growing direction overtakes the minimum's slowest decay, and a right-hand side with that direction removed delays it by a fixed number of steps a decade. With two negative curvatures, the prediction was that hiding both is paid for by the faster, and that hiding only the faster leaves the slower one's race to run. The first half holds to half a per cent on three pairs, and to one and a half on two whose curvatures differ by a factor of two and of 1.2. The second does not: hiding either direction alone moves the verdict by a fixed handful of steps, the same at two decades as at sixteen, because the direction left in view is already growing. Only the intersection of the two hyperplanes hides anything — and it hides less than either curvature can alone, 1,127 steps at worst against 2,907, with random right-hand sides' slowest at 79 against 417.