What is taught, and what the arithmetic does instead

“Conjugate gradients is a direct method: run it n steps and it is exact.”

After exactly n = 30 steps on a κ = 10⁶ matrix the residual is 5.1·10⁻⁴, and the residual basis that was supposed to be orthogonal has ‖RᵀR − I‖ = 5.29. Finite termination is a theorem about exact arithmetic and this is the case that puts it under load: the well-conditioned model problem cannot test it, because convergence arrives long before step n and nothing is left to fail.

Tested in The rate the condition number predicts · the krylov ladder · refused by a claim that CG terminates in n steps

“A randomised method with a probabilistic bound gives you the answer; the probability is a formality.”

The error moves by a factor of 1.60 across seeds at the same oversampling. The bound itself was not violated once in eighty seeds, which is reported rather than tuned — it is loose by 5.43× against the median, and a bound never violated at this sample size is not thereby deterministic. What the seed changes is the answer, not the guarantee.

Tested in A bound that holds with probability · the randomised ladder · refused by the claim that a randomised method returns one answer

“The elimination order affects how long the factorisation takes, not how much memory it needs.”

On the same 12×12 grid: natural order 1,739 entries, RCM 1,354, nested dissection 1,413, minimum degree 1,026. The matrix itself has 408. Every one of those factorisations is equally accurate and one of them is a factor of 1.7 larger than another, counted symbolically from the elimination graph with no arithmetic at all and again by factorising — the two counts agree exactly, as integers.

Tested in The order decides the memory · the ordering ladder · refused by the claim that elimination order does not affect fill

“The components a computation can resolve are the components worth keeping.”

They are not the same set, and the gap is measurable. The Picard crossing — where |uₖᵀb| stops falling and levels at the noise floor — lands at 32, 32, 40 and 45 across noise levels of 1%, 0.1%, 0.01% and 0.001%. The truncation that actually minimises the error is 21, 28, 32 and 38. Every one of the last few resolvable components carries more error than signal.

Tested in Where the answer stops being in the data · the regularisation ladder · refused by the Picard condition claimed for a right-hand side that is noise

“A sketch finds the structure in the data.”

On a matrix with a flat spectrum the randomised rank-10 error is 1.0 — and so is the optimal one. Neither method achieved anything, and the failure belongs to the matrix rather than to the sketch. The figure draws which of three cases a matrix is in first, because every other claim in the field is downstream of the spectral decay.

Tested in Randomisation does not create structure · the randomised ladder · refused by the claim that sketching finds structure that is not there

“A well-spread spectrum means a Krylov method will converge quickly.”

The cyclic shift has every eigenvalue on the unit circle — as well spread as a spectrum can be — and GMRES makes no progress on it for n − 1 steps. The residual is exactly 1 at every step until the last, checked to 10⁻⁹ at every size, and then the method solves the system exactly. A spectrum and a convergence rate are not the same fact about a non-normal matrix.

Tested in The spectrum that predicts nothing · the gmres ladder · refused by a convergence claim made from the spectrum alone

“The QR algorithm converges.”

Without a shift it does not. On [[0, 1], [1, 0]] the subdiagonal entry moves by 1.09·10⁻¹⁴ in two hundred iterations, which is to say it does not move at all — the two eigenvalues have the same modulus and the ratio governing convergence is one. Wilkinson's shift settles the same matrix in a single step. The shift is not an acceleration; it is what makes it an algorithm.

Tested in The algorithm the libraries actually run · the qr algorithm ladder · refused by convergence claimed for the unshifted algorithm

“A symmetric matrix has well-conditioned eigenvectors.”

It has well-conditioned eigen*values*, and the two are different quantities in the same matrix. At a perturbation of 10⁻⁶ the eigenvalue shift is 3.867·10⁻⁷ at every gap; the eigenvector's angle runs from 3.06·10⁻⁶ to half a radian as the gap closes. Fed to the refusal at a gap of 10⁻⁸, the claim reports an angle of a radian and a half.

Tested in The gap decides the eigenvector · the eigen conditioning ladder · refused by the claim that symmetry protects the eigenvectors as well as the eigenvalues

“A Ritz value accurate to eight digits is evidence of an eigenvalue that is there.”

On a 40×40 matrix with forty distinct eigenvalues by construction, eighty Lanczos steps return twenty-five extra copies across thirteen of them — the largest arriving five times, all accurate to 1.9·10⁻⁸ relative. A hundred and twenty steps return seventy-one extra copies with the largest arriving eight times. The accuracy is what makes them undetectable: nothing but the true spectrum separates a copy from a discovery.

Tested in An eigenvalue that arrives twice · the lanczos ladder · refused by the claim that an accurate Ritz value is a distinct eigenvalue

“Between two low-precision formats, the one with more mantissa bits is the more accurate.”

It depends on where the data is, and the block formats are the case that makes it obvious. Across sixteen octaves of range inside a block the 2-norm of the error moves by 1.76× while the median entry's error moves by 62×, ending at exactly 1.00, with 383 of 640 entries deleted outright. A format's competence is a claim about the numbers it is given.

Tested in One exponent for thirty-two numbers · the block formats ladder · refused by the claim that the format with more bits always wins

“Gram–Schmidt produces an orthonormal basis for the column space.”

It does, over the reals, and the derivation is three lines. On H₈ the classical process returns a Q with an off-diagonal inner product of 1.0 — two computed basis vectors that are parallel — while every column is still a unit vector to 10⁻¹². Orthogonality is lost like κ² classically and like κ in the modified order; the same algebra written in a different sequence, and eight decades between them.

Tested in Two Gram–Schmidts · the gram schmidt ladder · refused by the orthogonality check

“Adding a small number to a running total moves the total.”

Below the spacing of the total it does not arrive at all, and it does not arrive again for every subsequent term of the same size — which is how a sum of a million equal terms stops growing before it is half computed. The refusal is fed a sum that has stagnated and required to report that the addend was lost.

Tested in The order they are added in · the summation ladder · refused by the claim that a small addend always arrives

“Reassociating a floating-point computation changes its answer, so a reordering has to be paid for in accuracy.”

It has to be paid for whenever the operation being reassociated amplifies. An orthogonal transformation does not amplify — that is what orthogonal means — and a product of orthogonal transformations is orthogonal however it is bracketed. Measured on a 512×12 matrix at κ = 7,151: the tree at depths 1, 2, 3 and 4 returns 3.38, 4.26, 1.65 and 1.48·10⁻¹⁵, which does not grow with the depth. Classical Gram–Schmidt, whose steps are not orthogonal, returns 4.6·10⁻¹⁰ on the same matrix.

Tested in A reduction that changes the order · the communication ladder · refused by a reduction tree with under-determined leaves

“Every square matrix is orthogonally similar to a triangular one.”

Over the complex numbers, yes — that is Schur's theorem. Over the reals, an orthogonal similarity cannot separate a conjugate pair, and the reachable form carries one 2×2 block per pair. Checked at four prescribed spectra: exactly one block per pair every time, and a real spectrum does come out genuinely triangular. The surviving subdiagonal entry is 2.0 against a matrix norm of 5.8 — the size of the matrix, not of a tolerance.

Tested in The form a real matrix can reach · the real schur ladder · refused by triangular form claimed for a real matrix with a conjugate pair

“Two formats with the same number of significand bits have the same precision, so the same computation gives the same answer.”

They have the same unit roundoff and their largest finite numbers are 33 decades apart. The naive norm of a vector of sixteen 1,000s is an infinity in fp16 and 4,000 in tf32, at identical precision — and bfloat16, the least precise of the three, returns 3,968. This site reported fp16 and tf32 as one format for two phases, because its arithmetic modelled the significand alone.

Tested in The other half of a format · the floating point ladder · refused by fp16 and tf32 treated as one format because their mantissas match

“A shift accelerates the QR iteration, so a good shift is enough.”

A real single shift cannot converge onto a complex conjugate pair at all — there is no real number to shift towards. The double shift is not a faster single shift; it is the construction that makes the problem addressable in real arithmetic, and it is performed without ever forming the complex matrix it is derived from. The implicit step and the explicitly formed product agree to 2.2·10⁻¹⁵ entry by entry in absolute value.

Tested in Two shifts that are never formed · the francis ladder · refused by convergence claimed for the single-shift algorithm on a conjugate pair

“If x − y computes to zero then x and y are the same number.”

With gradual underflow it is true, and it is one of the reasons subnormals exist. With flush-to-zero it fails on ten of ten distinct neighbouring pairs immediately above fp16's smallest normal: the difference is representable only as a subnormal, the subnormal is flushed, and the test for equality returns true for two different numbers.

Tested in The numbers below the smallest one · the subnormals ladder · refused by flush-to-zero treated as leaving subtraction faithful

“The Galerkin coarse operator RAP is the discretisation of the same problem on the coarser grid.”

This site asserted it, and still does — in one dimension it holds to a relative difference of exactly zero at every level of a six-level hierarchy. In two, a five-point operator produces a nine-point coarse one, with four diagonal couplings carrying a sixth of the row, so every level below the first solves a different discretisation. The method converges at 0.20 a cycle regardless, which is the interesting half.

Tested in The coarse problem is a different problem · the multigrid ladder · refused by the one-dimensional Galerkin identity carried into two dimensions

“Scaling a set of numbers by a power of two changes no value, so it changes no result.”

The scaling is exact and what it changes is which numbers share a block. Sorting the same values — which alters no value at all and no scale factor's exactness — takes the count of entries quantised to zero from 310 to 22. The order is not a presentational choice once one exponent is shared across a group.

Tested in One exponent for thirty-two numbers · the block formats ladder · refused by the claim that a block format is order-independent

“Interval arithmetic gives rigorous bounds, so carrying intervals through an algorithm gives a rigorous answer.”

It gives rigorous bounds and they become useless. Rotating an interval box by 45° twenty times — an isometry, so the true set does not change size at all — leaves an enclosure 1,024 times too wide, growing by exactly √2 a step: measured at 1.4142137 against √2 = 1.4142136. No rounding error is responsible for any of it and a higher precision does not touch it.

Tested in A bound that is proved · the interval ladder · refused by the claim that interval arithmetic can be carried through an algorithm

“Two implementations with the same operation count cost the same.”

At n = 48 with 144 words of fast memory both orderings perform exactly 72,568 operations, choose exactly the same pivots and return a factorisation whose residual agrees to the last bit. One moves 41,332 words between fast and slow memory and the other 19,476 — a factor of 2.12, and the ratio does not fall with size. The refusal is fed the claim that equal flop counts mean equal data movement and requires it to fail.

Tested in The same arithmetic at a different price · the blocking ladder · refused by the claim that a flop count predicts the cost

“The answer came back wrong, so the algorithm was unstable.”

A Householder least-squares solve of a 48-point deconvolution returns a relative error of 5.5·10⁸ with a residual at the level of rounding. The algorithm did everything that can be asked of it. κ is 5.7·10¹², the singular values decay exponentially with no gap anywhere, and the data is consistent with a range of answers differing by orders of magnitude. The refusal is fed the claim that a backward-stable method answers an ill-posed question accurately and requires it to fail.

Tested in When the answer is a choice · the regularisation ladder · refused by the claim that a stable algorithm answers an ill-posed question

“The residual came back at 10⁻¹⁶, so the answer is accurate.”

A 13×13 Hilbert system whose exact answer is the integers 1 to 13 solves to a backward error of 2.2·10⁻¹⁷ and returns 0.049 where 8 belongs and −2.58 where 10 belongs. The algorithm is blameless and κ is 1.7·10¹⁸. The residual measures the algorithm; the error is the residual times the problem's own sensitivity, and only the second is what anybody sees.

Tested in A small residual is not a small error · the backward error ladder · refused by a usable answer inferred from ‖PA − LU‖ alone

“Pick the regularisation parameter from the corner of the L-curve.”

Scored against the λ that actually minimises the error, on a 64-point deconvolution at 0.1% noise: the L-curve's corner gives a relative error of 0.2406 against the oracle's 0.1051 — 2.29 times. Generalised cross-validation on the same problem lands on the oracle's λ exactly and the discrepancy principle costs 6%. The corner is a real feature and picking it is not the same as picking the best parameter.

Tested in Choosing without knowing · the parameter choice ladder · refused by a rule that beats the truth it is scored against

“Refinement has not converged yet — run more steps.”

Past its threshold the method is inert rather than slow. With the residual computed in single precision the same code ends at 8.80·10⁻⁵ having improved by a total factor of 1.51 across six steps; each step is doing exactly as much as the first, which is almost nothing. The step count is not the parameter and the precision the residual is computed in is.

Tested in Buying the accuracy back · the mixed precision ladder · refused by more refinement steps claimed to help past the threshold

“Iterative refinement recovers double-precision accuracy from a low-precision factorisation.”

It recovers it below κu ≈ 1 and not above, and the three hardware formats straddle that threshold at κ = 10³. bfloat16 at κu = 3.91 ends at 1.04·10⁻³ having recovered a factor of 412 — which looks like the method working hardest, and is the confounding this figure exists to remove. The shortfall against a full double solve of the same system is not confounded.

Tested in Where the hardware went · the mixed precision ladder · refused by refinement claimed to converge past its threshold

“Multigrid works because the smoother removes the error.”

The smoother removes the oscillatory part and leaves the rest almost untouched: weighted Jacobi's own convergence factor climbs 0.981 → 0.998 as the grid refines, each value checked against cos(πh). The V-cycle's stays at 0.1002 ± 0.001 over the same range. A rate belonging to two components attributed to one of them is a claim that predicts the wrong number by a factor of ten.

Tested in The error smoothing cannot reach · the multigrid ladder · refused by the multigrid rate claimed for the smoother on its own

“Overflow is a very large rounding error, so a more careful algorithm loses a few more digits.”

It is the loss of the number rather than of digits, and no subsequent arithmetic recovers from it. The naive √(Σx²) is correct over 18 of fp16's 30 normal exponents, because squaring doubles the exponent; the scaled form is correct at every normal exponent of all three formats tested. Same precision, same algebra, and one of them returns an infinity where the answer is 4,000.

Tested in A norm that overflows before it is a norm · the overflow ladder · refused by overflow described as a rounding error

“Multigrid is grid-independent, so it converges at the same rate on any second-order elliptic problem.”

Give the operator a strong direction and the V-cycle's convergence factor goes from 0.10 to 0.9565 while the grid-independence claim stays true. And the problem did not get harder: the anisotropic operator's condition number is cot²(πh/2) for every ε, measured at 103.08686891981742 across four decades with a relative spread of 2.8·10⁻¹⁶. Only the method is worse.

Tested in A direction the smoother cannot see · the anisotropy ladder · refused by the claim that a point smoother copes with anisotropy

“The computed eigenvector is badly wrong, so the computation failed.”

At a gap of 10⁻⁹ the returned eigenvector is decided by the perturbation rather than by the matrix — four seeds give 0.483, 1.466, 0.536 and 0.167 radians — and every one of them satisfies Ax = λx to 5·10⁻¹⁵. Nothing failed. The quantity that is a property of the matrix is the plane the two vectors span, and it moves by 7.63·10⁻⁸ and does not move with the gap at all.

Tested in The plane survives what its vectors do not · the invariant subspace ladder · refused by measuring a subspace by one of its vectors

“The solution came back oscillating, so the solver did not converge.”

The oscillating vector is the exact solution of the linear system: ‖Ax − b‖/‖b‖ = 4.6·10⁻¹⁸. It alternates at every point and leaves [0, 1] at 16 of 31 grid points, by as much as 0.515, while the continuous problem it discretises is monotone from 0 to 1. No iteration, no preconditioner and no precision changes it, because nothing about the solve is wrong.

Tested in The stencil that is not symmetric · the convection ladder · refused by an oscillation blamed on the solver

“The number of conjugate gradient iterations is set by √κ.”

Asymptotically. At step 20 a κ = 10⁶ problem sits inside the bound belonging to κ = 100 — 1.7·10⁻² against 3.6·10⁻² — because early convergence is governed by how the eigenvalues cluster and only the tail by κ. The bound holds at every step and is loose by an order of magnitude: 400 iterations permitted on the model problem, 40 taken, closest approach 43%.

Tested in The rate the condition number predicts · the krylov ladder · refused by the bound belonging to κ = 1

“A dense matrix costs n³ to factorise.”

It costs n³ if the only thing known about it is that it is dense. A circulant of size n has no zero entry and is described by n numbers, and its factorisation is a transform: A = F* Λ F, with F known in advance and Λ one transform away. The residual printed on the figure — 4.7·10⁻¹⁶ — is the same quantity an elimination's badge carries, from a factorisation that never formed a factor.

Tested in The matrix that is one row · the circulant ladder · refused by a circulant with a zero eigenvalue

“Nested dissection is the ordering to use; it has the better asymptotics.”

It loses to minimum degree at every size this site draws — 1,413 entries against 1,026 on the 12×12 grid — and minimum degree is the cheap heuristic. A complexity class is a statement about a limit, and the fill exponent fitted across grid sizes 6 to 12 is 1.488 for the factor against 1.044 for the matrix, which is the quantity the asymptotics are about.

Tested in The order decides the memory · the ordering ladder · refused by the claim that a good ordering removes fill rather than limiting it

“The condition number of this Toeplitz family is ((1+ρ)/(1−ρ))².”

That is the limit as the size grows, and every section is strictly below it. At ρ = 0.8 the limit is 81.000 and the measured κ is 42.35 at n = 8, 59.98 at n = 16, 72.20 at 32, 78.05 at 64 and 80.14 at 128 — 52%, 74%, 89%, 96% and 98.9% of it. The refusal is fed the claim that the 16×16 section attains its own asymptotic value and requires it to fail.

Tested in A limit the matrix never reaches · the toeplitz ladder · refused by Szegő's limit claimed as a value at a finite size

“Blocking makes an elimination communication-optimal.”

It buys a constant, not an exponent. Fitted across n = 16 to 64, the blocked traffic grows at n^3.182 and the unblocked at n^3.185 — the same exponent to within the fit's own noise — and the ratio between them is 2.19, 2.11, 1.98, 2.17, 2.17. Against the Hong–Kung floor of n³/√M the blocked traffic sits at 1.50, 2.03, 2.25, 2.05, 2.04 times, which is a constant above the floor rather than a match to it.

Tested in A block size is a property of the machine · the blocking ladder · refused by a saving claimed for a matrix that fits in fast memory

“Circulant preconditioning makes Toeplitz conjugate gradients converge in a number of steps independent of n.”

It does, once the preconditioner is positive definite, and at ρ = 0.95 that has not happened by n = 128. Measured on the same systems: 21 steps against 21 at n = 16, 55 against 40 at n = 32, 109 against 66 at n = 64, 134 against 111 at n = 128, and then 10 against 179 at n = 256. Four of those five rows are the method costing steps rather than saving them.

Tested in A preconditioner that changes sign · the preconditioning ladder · refused by a preconditioner claimed to help at every size

“Gauss–Seidel converges twice as fast as Jacobi.”

Its spectral radius is the square of Jacobi's, which is a statement about the rate rather than about the count, and at n = 24 the counts are 1,574 against more than 3,000 — a ratio that is not two and would not be two at any other size either. Optimally relaxed SOR takes 128, and its iteration matrix is defective at ω_opt, so even its rate holds only in the mean.

Tested in A rate that is known in advance · the stationary ladder · refused by Jacobi's rate against Gauss–Seidel's

“The symbolic phase computes the structure in advance, so the memory can be allocated before any arithmetic runs.”

Without interchanges the symbolic count is exact as an integer — 233 and 233 on the same grid. With partial pivoting it is 233 predicted against 242 measured, and the George–Ng structural bound that does hold gets looser as the problem grows: 1.39× at 4×4 to 1.68× at 7×7. A bound that loosens with size cannot be allocated from, which is the practical conclusion.

Tested in What the symbolic phase can only bound · the sparse pivoting ladder · refused by a symbolic fill count offered as a prediction under pivoting