kron-solve
At its defaults it draws multiplications in a 3-dimensional model solve, through the eigenbasis against a dense factorisation. A Kronecker sum's eigenvectors are the Kronecker products of its factors' eigenvectors, so the change of basis that diagonalises an operator with 1,728 rows is 3 changes of basis along 3 indices. The whole solve is a transform, 1,728 divisions and a transform back: 1.24·10⁵ multiplications at n = 12, against a dense factorisation's 3.44·10⁹, a factor of 2.76·10⁴. The fitted exponent is 4.00 against 3d = 9. The only decompositions taken are of the 3 one-dimensional factors, which on the model problem are the same matrix — so there is exactly one, of size 12. Every solve reproduces its right-hand side to 8.36·10⁻¹⁵.
kron-solve is one function in lib/figures/tensor.js —
an index that is a tuple — a matrix that is d small ones, and the inverse that is nearly one. Everything below came out of it during this build, at
arguments taken from the essays rather than invented for this page. A figure here is the
figure a reader meets in an essay, and if the generator changes, this page changes with it.
At its defaults
Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.
A Kronecker sum's eigenvectors are the Kronecker products of its factors' eigenvectors, so the change of basis that diagonalises an operator with 1,728 rows is 3 changes of basis along 3 indices. The whole solve is a transform, 1,728 divisions and a transform back: 1.24·10⁵ multiplications at n = 12, against a dense factorisation's 3.44·10⁹, a factor of 2.76·10⁴. The fitted exponent is 4.00 against 3d = 9. The only decompositions taken are of the 3 one-dimensional factors, which on the model problem are the same matrix — so there is exactly one, of size 12. Every solve reproduces its right-hand side to 8.36·10⁻¹⁵.
d: 3
The arguments are the ones A solve that is d decompositions passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.
A Kronecker sum's eigenvectors are the Kronecker products of its factors' eigenvectors, so the change of basis that diagonalises an operator with 1,728 rows is 3 changes of basis along 3 indices. The whole solve is a transform, 1,728 divisions and a transform back: 1.24·10⁵ multiplications at n = 12, against a dense factorisation's 3.44·10⁹, a factor of 2.76·10⁴. The fitted exponent is 4.00 against 3d = 9. The only decompositions taken are of the 3 one-dimensional factors, which on the model problem are the same matrix — so there is exactly one, of size 12. Every solve reproduces its right-hand side to 8.36·10⁻¹⁵.
d: 2
The arguments are the ones A solve that is d decompositions passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.
A Kronecker sum's eigenvectors are the Kronecker products of its factors' eigenvectors, so the change of basis that diagonalises an operator with 1,024 rows is 2 changes of basis along 2 indices. The whole solve is a transform, 1,024 divisions and a transform back: 1.31·10⁵ multiplications at n = 32, against a dense factorisation's 7.16·10⁸, a factor of 5461. The fitted exponent is 3.00 against 3d = 6. The only decompositions taken are of the 2 one-dimensional factors, which on the model problem are the same matrix — so there is exactly one, of size 32. Every solve reproduces its right-hand side to 1.44·10⁻¹³.
What it checked while drawing
Every figure above asserted its own claims on the way to being drawn, and a claim that failed
would have failed the build rather than drawn a wrong picture. Those assertions used to leave
no trace at all: a passing one returned true and the only evidence the figure had
checked anything was that nothing crashed. The list below is what they actually said, collected
by running this generator with an observer installed — not a description of
what it is believed to check.
13 distinct claims across 3 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.
the solve at n = 4 solves — asserted 8 times
a number of indices the sweep is run at
and costs less than a dense factorisation
at an exponent near d + 1 rather than 3d
Jacobi needs a symmetric matrix
matmul shapes agree
Against the rule
The rule does not apply to it. It factorises nothing, so there is no residual it could be withholding. That is worth stating rather than leaving blank: a site that reported the rule as satisfied by every generator would be counting mostly generators the rule never reached.
Across the library: the rule bites on 146
of 287 generators —
131 print a residual and
15 are exempt with a published reason;
141 factorise nothing.
Read from lib/residual-rule.js, which is the same body the gate enforces from,
and the gate's last check fails the build if this page and it disagree about any generator.
Where it is called
Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.
A solve that is d decompositions
A Kronecker sum is closed under nothing useful — its inverse is not a Kronecker sum and no factorisation of it is one. What it has instead is eigenvectors that are Kronecker products, so a solve with 1,728 unknowns takes one decomposition of a 12 × 12 matrix and nothing else.
Structure, and the solver that cannot see itAn equation whose unknown is a matrix
AX + XB = C is linear in X, so it has a coefficient matrix, and writing it down is the obvious thing to do. At n = 100 that matrix has a hundred million entries for a problem with ten thousand unknowns, and the algorithm everybody uses instead never forms it. Its conditioning is not the eigenvalue gap either, which is the number a reader is invited to consult.
Iterating, instead of factorisingAn 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.
Iterating, instead of factorisingAn operator with no entries
At the sizes where linear algebra is expensive the matrix does not exist. What exists is a subroutine that returns Av. Every Krylov method survives that unchanged; every algorithm that reads an entry disappears. And the derivative such a code computes is accurate to ten digits instead of sixteen, which turns out to cost nothing at all.
Sparsity, and what elimination costsThe factor is not sparse
A sparse matrix has a factor that is not sparse, and the gap between them is the entire reason iterative methods exist. The entries elimination creates can be counted before any arithmetic runs, from the graph alone.
Structure, and the solver that cannot see itThe matrix that is one row
A circulant of size 16 is sixteen numbers, has no zero entry anywhere, and hands over its entire spectrum in closed form — the discrete Fourier transform of its first column, exactly. An eigensolver spends a sweep of Jacobi rotations over 256 entries arriving at the same answer, and agrees to 1.2·10⁻¹⁵.