The thread: Claims that can fail — page 7
A margin the factorisation records
Partial pivoting finds the second-largest candidate in every column it scans, and throws it away. Keep it, divide the gap by the growth reached at that step, and take the smallest over the steps before half the final growth has arrived. That one number, recorded by the factorisation that is already running, predicts the dense noise that halves the growth to within a factor of 0.92 to 2.4 on shooting matrices whose growth runs from 75 to 1.3·10⁵ and whose fragility spans three and a half decades — and on Wilkinson's matrix it is exactly zero.
Randomised, and the guarantee that changes kindA sketch that finds the columns it can see
A sparse sketch with one nonzero in each row is twenty times cheaper to apply than a Gaussian one, and on a matrix whose important directions are spread across its columns it finds the same range: a median error of 0.45 against 0.43. Put the same ten directions into ten particular columns and it is eight times worse — 3.33 against 0.41, with a worst draw of 7.1 — because two important columns hashed to one bucket are one direction. Three nonzeros a row repair it at a sixth of the Gaussian's cost, and a randomised Hadamard transform never had the problem.
When the problem arrives againThe degree the history chooses
A sequence of solves can start each member from the line through its last two answers or the parabola through its last three, and which is better depends on how much its path bends — which a code does not know. Over thirty runs of bend and tolerance, always taking the line costs 456 inner steps more than the better choice; always taking the parabola costs 33. A free rule reading the stored answers closes that to 11. A rule that evaluates the residual at both starts picks the better one on 29 runs of 30, and pays 135 steps for the evaluations.
Reduction, and what a model is forA certificate written in coordinates
Every one-sided reduced model of the convection–diffusion system was stable, because its poles cannot leave the numerical range and the range sat in the left half plane. Rescale the state by a diagonal matrix and nothing about the system changes — not its eigenvalues, not its transfer function, not one pole of any two-sided model — but the numerical range moves. At Péclet 40 a rescaling with condition number 260 pushes its edge to +6.6 and ten placements of nineteen return unstable one-sided models. Projecting in the inner product of a Lyapunov solution puts the certificate back in any coordinates.
Sparsity, and what elimination costsHow few columns the search needs
A full row-and-column pivot search is quadratic in the active submatrix at every step, and no library performs one. Looking at a single sparsest column takes the median fill from 244 to 136 where the full search reaches 109 — four fifths of the benefit for a linear scan — and that share is 79, 83, 80, 89 and 92 per cent across five thresholds. The worst growth appears to favour the narrow search by a factor of six, and on the next draw it favours the wide one by two.
Eigenvalues, singular values, rankA spectral radius that grows first
ρ(A) below one guarantees that the powers of A go to zero and says nothing about what they do on the way. Here they rise by a factor of twenty thousand before turning over, and the peak is bracketed above and below by a constant computed from the resolvent norms outside the unit circle — two routes to one number, one through the plane and one through the powers.
Elimination, and the swapA threshold that holds the growth still
Partial pivoting's large growth on the shooting matrix rests on a margin of 5.6·10⁻³, and Wilkinson's rests on exact ties, which a perturbation at rounding breaks. A sparse code pivots with a threshold instead, taking the sparsest row among candidates within a factor τ of the largest. At every threshold from 1 to 0.1 both matrices grow by exactly as much as under partial pivoting. But the growth is now held by row counts, which no perturbation of the values can reverse: at τ = 0.1 it survives noise on the stored entries up to 0.56 on the shooting matrix, three hundred times more, and 0.18 on Wilkinson's, where partial pivoting's goes at 10⁻¹⁶. The margin that predicts it is the chosen candidate's height above the threshold line, and it needs no division by the growth.
The matrix a constraint makesA loop that asks the null space why
An inertia-correction loop sees only an integer, and two different faults produce the same wrong one: curvature that needs a shift, and a constraint too weak for the count to see. One QR of the constraint matrix on a wrong count tells them apart — it shifts none of the 22 weak-constraint minima the ordinary loop shifted by up to 2,621 — and its reduced eigenvalue gives the shift a saddle needs in one step, twice the need exactly, where the schedule overshoots by up to 17,783 times. But at κ(A) = 10⁸ the loop still certifies 57 saddles of 152, because a false certificate is a count that read right, and a check made only on wrong counts never sees it. Asking every time leaves five, all shallower than 2·10⁻⁸.
Two errors, and whose fault they areThe 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.
Eigenvalues, singular values, rankA 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.
The matrix that is a graphA 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.
Neither sparse nor denseA prediction that arrives a decade late
A rougher kernel raises every rank, a higher rank raises the side at which compressing a block stops paying, so the leaf that stores least should rise. Across four kernels whose largest rank runs 5, 5, 9 and 10, it is 16 on three of them and a tie between 8 and 16 on the fourth. The prediction is right in sign and out by a decade of tolerance, and the reason is a ceiling: an oscillation multiplies the rank by exactly two — 3 and 6, 4 and 8, 5 and 10, 6 and 12, 7 and 14 — at any frequency, because a cosine of a difference is a rank-two function.
Orthogonality, measuredEight blocks and sixty-four reflections
One block of sixteen reflectors, assembled as I − Y T Yᵀ, departed from orthogonality five times as far as a single reflection, and the question was whether a factorisation of many blocks multiplies that factor. It does not. On 96 × 64 matrices eight blocks of eight end at 1.42·10⁻¹⁴ — within a fifth of the root-sum-square of their own departures, and less than half their sum — while the same factorisation taken one reflector at a time ends at 2.91·10⁻¹⁴. A block departs more than a reflector, and there are an eighth as many of them. And a nearly dependent column that swells the triangle's entries to 10²⁶ costs the product nothing.
Randomised, and the guarantee that changes kindThe leverage that did not move
A one-nonzero sketch fails on a matrix whose leading directions sit on ten particular columns, and coherence — the largest column leverage — is the statistic that names the failure. Turn the directions away from their columns by a hundredth of a radian and the sketch's median error falls from 3.47 to 1.23 times σ₁₁ while the coherence stays at 6.40 to three figures. Giving the heaviest columns buckets of their own repairs the rest, but only when it reserves more buckets than the rank: ten reserved leave 1.16, sixteen reach 0.36, below the Gaussian's 0.41.
When the index is a tupleA still error is not a settled one
A CP fit with one term too many on a noisy tensor never meets the usual stopping test, and its error has settled by sweep 150. A test that asks only whether the error has moved by less than δ of itself over ten sweeps stops those fits by sweep 25, and over twenty-four noisy tensors it names the same rank as the usual test every time, at δ = 10⁻² for 30,250 sweeps against 311,458. But δ = 10⁻² is the tolerance a rank decision states, and on a slow fit that converges it stops five starts of six on a plateau ten orders above the answer and names the wrong rank for four tensors of six. A tenth of the decision's tolerance keeps every decision on both families.
The matrix that is a graphA conductance the arcs do not measure
Symmetrising a directed Laplacian with respect to its walk recovers everything the arrows took — a real spectrum, a sweep cut, a Cheeger inequality. What it does not recover is the quantity: the inequality bounds the probability that a step of the walk crosses the cut, which on one graph here is three times the weight of the arcs that do.
The eigenvalue problem that is not linearThe number that moves when the problem does
Two quantities are offered as the condition number of one eigenvalue. One is unmoved to eight digits by a change of variable that is exact in both directions, and grows like the square root of the chain's length. The other is inflated by ten orders by that change of variable, and is ten times too large before anything has been done at all.
The answer that depends on the machineThe licence is not the boundary
Cholesky QR is licensed by κ²u ≪ 1, which reaches equality at κ = 9.5·10⁷ in double precision. At 10⁸ the factor it returns is already 0.37 away from orthogonal, and it goes on returning factors as far as 10¹³ — refusing at scattered condition numbers in between, at different ones for eight columns and for six.
The arithmetic underneathNine steps of pessimism
A proved bound is 8 to 26 times the error it bounds, at every precision from 16 to 40 significand bits. A carried interval is (√2)ᵐ times too wide after m re-enclosures. The two cross between eight and nine, so the method everybody warns against is the tighter of the two for a short computation.
Eigenvalues, singular values, rankThe series that has to be squared back
The Taylor series for the matrix exponential is not wrong — every term is computed correctly — and on Moler and Van Loan's two-by-two its largest term is 5.4 million times the answer it sums to. The method that replaces it scales the matrix down and squares the result back, and both halves of that sentence cost: too few squarings and the approximant is out of range, too many and each one doubles the rounding.
Two errors, and whose fault they areTwo 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.
Neither sparse nor denseA quarter of the leaf
The leaf that stores a hierarchical matrix most cheaply had been read off a table of nine points, with the suggestion that it depends on the mean rank alone. Across six kernels at five tolerances — thirty cells — it does, once the mean rank is read in the right place. Plotted against the mean rank at a fixed leaf of 16, two cells a tenth of a rank apart want leaves of 8 and 16. Plotted against the rank of the blocks a halving would create, one rule — halve the leaf while that rank is below a quarter of the leaf — predicts the best leaf on 28 of the 30, and the two it misses are the two whose rank sits within three per cent of the threshold. The fractional power the last measurement expected to be rough is smoother than 1/r.
Randomised, and the guarantee that changes kindA spread measured on probes it does not average
A trace estimator that stops on its own standard error misses its target a few points more often than a normal table says, because the runs that stop earliest are the ones that underestimated their noise. Spend a pilot of probes only on the spread, fix the number of probes to average in advance, and the selection is gone: with Student's margin the two-stage rule covers 64.8 to 73.3 per cent at one standard error where the table says 68.3. With the normal's margin and a pilot of four it covers 58.5. At one standard error it recovers one to five points for a fifth to two fifths more probes; at 1.96 there was nothing to recover, and the guarantee costs a tenth to double.
Exact arithmetic, and what it costs insteadThe 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.