True in a limit nobody reaches

“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 series · refused by a circulant with a zero eigenvalue

“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 series · refused by the bound belonging to κ = 1

“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 series · refused by a saving claimed for a matrix that fits in fast memory

“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 series · refused by Szegő's limit claimed as a value at a finite size

“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 series · refused by the claim that a good ordering removes fill rather than limiting it

“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 series · refused by a preconditioner claimed to help at every size

“Circulant preconditioning of a Toeplitz system gives a step count independent of the size.”

On square grids of 16, 36, 64 and 100 unknowns the preconditioned count is 10, 18, 20, 21 — climbing — while the one-dimensional matrices of exactly those sizes give 7, 10, 10, 10. The refusal is fed the claim that the two-dimensional count does not depend on the grid and requires it to fail.

Tested in Two dimensions, and the cluster that thins · the toeplitz series · refused by the one-dimensional clustering result claimed in two dimensions

“Cholesky's growth factor is bounded by one, so it is stable.”

The growth factor is measured at nine combinations of size and condition number and is exactly 1 at every one of them. The refusal is fed the claim that an SPD elimination shrinks the largest entry, and required to fail.

Tested in A factorisation with nothing to pivot for · the cholesky series · refused by Cholesky's growth factor read as a strict inequality

“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 ωₒₚₜ, so even its rate holds only in the mean.

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

“Newton's iteration converges quadratically, so a handful of steps is enough.”

At κ = 10⁶ the unscaled iteration's error falls by a factor of 0.5000 per step for the first several steps — linear, not quadratic — and is still 10³ away after twelve. The refusal is fed the claim that it falls faster than a half a step, and required to fail.

Tested in An iteration that only multiplies · the polar decomposition series · refused by a quadratically convergent iteration claimed to be quadratic before it is close

“Replicating the data c times reduces a matrix multiplication's communication volume by √c — that is what the 2.5D algorithms buy.”

At 576 processors four layers save a factor of 1.44 against the law's 2, and at 64 they cost a factor of 1.14. The refusal is fed the claim that the saving reaches √4 at 576 processors and required to fail.

Tested in Memory bought with messages · the communication series · refused by the asymptotic saving claimed at a size anybody runs

“Bounding the rank of every block makes the representation cheaper.”

At 256 unknowns the strong partition has 112 blocks and a worst rank of 5 and stores 27,008 numbers; the weak partition has 46 blocks and a worst rank of 12 and stores 24,064. The refusal is fed the assertion that the strong one stores fewer and required to fail.

Tested in The test that costs what it saves · the admissibility series · refused by the finer partition is the cheaper one

“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 series · refused by a symbolic fill count offered as a prediction under pivoting

“A contour integral of an analytic function counts the zeros inside the contour, so evaluating it numerically gives an integer and the integer is the count.”

The counting integral is taken on a circle of radius four with an eight-point trapezoidal rule and rounded. The claim that a contour integral is an integer however coarsely it is taken is fed the result and fails: the answer is minus two, where four eigenvalues lie inside.

Tested in A problem with infinitely many eigenvalues · the nonlinear eigenvalue series · refused by an eight-point count of a contour of radius four

“A hierarchical solver is faster than a dense factorisation.”

At 64 unknowns the recursion performs 1.29·10⁵ multiplications against the dense factorisation's 8.74·10⁴ — 1.48 times as many, for an answer at the same backward error. The refusal is fed the assertion that the ratio is below one at every size on the sweep and required to fail.

Tested in Where the format starts paying · the hierarchical solve series · refused by the hierarchical solve is cheaper at every size

“Accuracy gets more expensive as you demand more of it: the first digits are cheap and each further one costs at least as much as the last.”

The counting integral is taken at 8, 16, 32, 64 and 128 quadrature points and the factor by which the error falls at each doubling is computed. The claim that a doubling buys no more than the one before it is fed the four factors and fails at every one of them: the digits gained per doubling are 0.6, 1.5, 3.2 and 6.4.

Tested in The last digit is the cheapest · the nonlinear cost series · refused by a doubling of the quadrature that buys more than the one before it

“A randomised contour method returns the eigenvalues inside its contour, so what it returns is what is there.”

Beyn's moment is formed with a two-column random probe block on a contour containing four eigenvalues, and its rank is measured. The claim that the method returns every eigenvalue inside the contour fails: the rank is two, both of the returned pairs are genuine, and nothing in the result mentions the other two.

Tested in Counting what is inside a circle · the trace estimation series · refused by two probes for four eigenvalues

“The saving from circulant preconditioning grows with the problem size.”

The saving is a ratio whose numerator stops. At ρ = 0.5 the unpreconditioned count reads 15, 22, 29, 28, 30, 30 across n = 16 to 512 and then 29, 28, 26, 27, 25 out to n = 16,384, against an averaged-circulant count of 8, 8, 7, 6, 6, 5 — so the ratio peaks at 6.0 and falls to 5.6. The refusal is fed the comparison at ρ = 0.05, where the family has no conditioning in it for a preconditioner to remove and the ratio of two step counts is a ratio of two constants, and requires it to fail.

Tested in A speedup with a ceiling of its own · the preconditioning series · refused by a preconditioner comparison on a family with no conditioning in it

“Rook pivoting costs a small constant multiple of partial pivoting's search, so it is always far cheaper than complete pivoting.”

On Gaussian matrices the rook compares 3.2 to 3.4 times partial pivoting's entries at every size from 8 to 80. On a matrix whose entries rise along a staircase it compares 1,976 entries at n = 16, about 14,700 at 32 and 113,376 at 64, against complete pivoting's 1,496, 11,440 and 89,440. The refusal is fed the claim that the rook never compares more than complete pivoting and required to fail.

Tested in A pivot that searches one row and one column · the pivoting series · refused by a rook search claimed never to cost more than a complete one

“A stationary iteration with spectral radius below one converges, and the radius tells you how fast.”

A 6×6 with ρ = 0.8 has ‖Aᵏ‖ rising to 1.98·10⁴ at step 24 before it turns over. The refusal is fed the claim that the powers decay from the start, and required to fail.

Tested in A spectral radius that grows first · the Non-normality series · refused by a spectral radius read as a statement about every power

“The exponential series converges for every matrix, so summing it until the terms are negligible computes the exponential.”

On the 2×2 with eigenvalues −1 and −17 and a norm of 64, the largest term of the series has norm 1.4·10⁷ and the sum has norm 2.6 — a cancellation of 5.4·10⁶ — and the computed answer has a relative error of 5.2·10⁻⁹ where scaling and squaring returns 8.5·10⁻¹⁴. The refusal is fed the claim that the cancellation is negligible, and required to fail.

Tested in The series that has to be squared back · the matrix function series · refused by the Taylor series offered as a method for the matrix exponential

“A random real tensor with two typical ranks takes each of them a substantial share of the time, as a 2 × 2 × 2 tensor takes rank two with probability π/4 and rank three with probability 1 − π/4.”

For real n × n × 2 tensors with standard normal entries the typical ranks are n and n + 1 at every n. Over 10,000 draws at n = 6 the tensor has rank 6 on 385, 3.85 per cent; over 4,000 at n = 8, on 16; at n = 10, on none. Every draw counted as rank n was decomposed into n rank-one terms with a relative residual below 10⁻¹¹. The refusal is fed the claim that rank n is taken on more than a fifth of draws at n = 6, and required to fail.

Tested in The rank that stops being typical · the tensor rank series · refused by the lower typical rank read as a substantial share at every size

“Computing eᴬᵗb means computing eᴬᵗ and multiplying. The exponential is the hard part and the multiply is free.”

On a 100×100 matrix whose exponential is known in closed form, twenty matrix–vector products give the vector to 4.3·10⁻¹⁶ — the accuracy of the full dense exponential — at 0.40 against 2.00 megaflops. The refusal is fed a dimension at which the dense route cannot be run at all, so the comparison the claim assumes does not exist.

Tested in The vector was what was wanted · the matrix function series · refused by a Krylov comparison drawn where the dense route cannot be run

“GMRES converges in at most n steps, and that is the bound worth knowing.”

On a 30×30 matrix with m distinct eigenvalues, the recurrence stops at step m for every m from 2 to 16 — never at 30 — with a relative residual below 6·10⁻¹⁶ there and at least 3·10¹⁰ times that one step earlier. The refusal is fed a recurrence with no first basis vector at all, where every subsequent step would divide by zero and the basis would orthogonalise perfectly against itself.

Tested in The zero that means it is finished · the breakdown series · refused by an Arnoldi recurrence started from the zero vector