Numerical Linear Algebra
where the algebra stops being the arithmetic
Generator

Multiplications in a 3-dimensional model solve, through the eigenbasis against a dense factorisation

One function in the tensor library, called 7 times across 2 essays. Below: what it draws at its defaults, what it draws at every value an essay asks for, the 17 claims it put to the test while drawing them, and where it stands against the rule this site is named for.

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.

Multiplications in a 3-dimensional model solve, through the eigenbasis against a dense factorisationA 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⁻¹⁵.10¹10²10⁴10⁶10⁸10¹⁰n, points along one axismultiplicationsa dense factorisationthrough the eigenbasis3 decompositions of an n × nunknowns1728multiplications1.2·10⁵dense factorisation3.4·10⁹fitted exponent4‖Ax − b‖ ⁄ ‖b‖8.4·10⁻¹⁵nothing of size n^dis ever factorised

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 nobody placed would be a picture no essay asked for and no claim was ever checked against.

Multiplications in a 2-dimensional model solve, through the eigenbasis against a dense factorisationA 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⁻¹³.10¹10²10⁴10⁶10⁸n, points along one axismultiplicationsa dense factorisationthrough the eigenbasis2 decompositions of an n × nunknowns1024multiplications1.3·10⁵dense factorisation7.2·10⁸fitted exponent3‖Ax − b‖ ⁄ ‖b‖1.4·10⁻¹³nothing of size n^dis ever factorised

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⁻¹³.

d: 6

The arguments are the ones Five indices are cheaper than two passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

Multiplications in a 6-dimensional model solve, through the eigenbasis against a dense factorisationA Kronecker sum's eigenvectors are the Kronecker products of its factors' eigenvectors, so the change of basis that diagonalises an operator with 15,625 rows is 6 changes of basis along 6 indices. The whole solve is a transform, 15,625 divisions and a transform back: 9.38·10⁵ multiplications at n = 5, against a dense factorisation's 2.54·10¹², a factor of 2.71·10⁶. The fitted exponent is 7.00 against 3d = 18. The only decompositions taken are of the 6 one-dimensional factors, which on the model problem are the same matrix — so there is exactly one, of size 5. Every solve reproduces its right-hand side to 1.77·10⁻¹⁵.110¹10²10⁴10⁶10⁸10¹⁰10¹²n, points along one axismultiplicationsa dense factorisationthrough the eigenbasis6 decompositions of an n × nunknowns1.6·10⁴multiplications9.4·10⁵dense factorisation2.5·10¹²fitted exponent7‖Ax − b‖ ⁄ ‖b‖1.8·10⁻¹⁵nothing of size n^dis ever factorised

A Kronecker sum's eigenvectors are the Kronecker products of its factors' eigenvectors, so the change of basis that diagonalises an operator with 15,625 rows is 6 changes of basis along 6 indices. The whole solve is a transform, 15,625 divisions and a transform back: 9.38·10⁵ multiplications at n = 5, against a dense factorisation's 2.54·10¹², a factor of 2.71·10⁶. The fitted exponent is 7.00 against 3d = 18. The only decompositions taken are of the 6 one-dimensional factors, which on the model problem are the same matrix — so there is exactly one, of size 5. Every solve reproduces its right-hand side to 1.77·10⁻¹⁵.

d: 3

The arguments are the ones Five indices are cheaper than two passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

Multiplications in a 3-dimensional model solve, through the eigenbasis against a dense factorisationA 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⁻¹⁵.10¹10²10⁴10⁶10⁸10¹⁰n, points along one axismultiplicationsa dense factorisationthrough the eigenbasis3 decompositions of an n × nunknowns1728multiplications1.2·10⁵dense factorisation3.4·10⁹fitted exponent4‖Ax − b‖ ⁄ ‖b‖8.4·10⁻¹⁵nothing of size n^dis ever factorised

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: 4

The arguments are the ones Five indices are cheaper than two passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

Multiplications in a 4-dimensional model solve, through the eigenbasis against a dense factorisationA Kronecker sum's eigenvectors are the Kronecker products of its factors' eigenvectors, so the change of basis that diagonalises an operator with 2,401 rows is 4 changes of basis along 4 indices. The whole solve is a transform, 2,401 divisions and a transform back: 1.34·10⁵ multiplications at n = 7, against a dense factorisation's 9.23·10⁹, a factor of 6.86·10⁴. The fitted exponent is 5.00 against 3d = 12. The only decompositions taken are of the 4 one-dimensional factors, which on the model problem are the same matrix — so there is exactly one, of size 7. Every solve reproduces its right-hand side to 3.71·10⁻¹⁵.110¹10²10⁴10⁶10⁸10¹⁰n, points along one axismultiplicationsa dense factorisationthrough the eigenbasis4 decompositions of an n × nunknowns2401multiplications1.3·10⁵dense factorisation9.2·10⁹fitted exponent5‖Ax − b‖ ⁄ ‖b‖3.7·10⁻¹⁵nothing of size n^dis ever factorised

A Kronecker sum's eigenvectors are the Kronecker products of its factors' eigenvectors, so the change of basis that diagonalises an operator with 2,401 rows is 4 changes of basis along 4 indices. The whole solve is a transform, 2,401 divisions and a transform back: 1.34·10⁵ multiplications at n = 7, against a dense factorisation's 9.23·10⁹, a factor of 6.86·10⁴. The fitted exponent is 5.00 against 3d = 12. The only decompositions taken are of the 4 one-dimensional factors, which on the model problem are the same matrix — so there is exactly one, of size 7. Every solve reproduces its right-hand side to 3.71·10⁻¹⁵.

d: 5

The arguments are the ones Five indices are cheaper than two passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.

Multiplications in a 5-dimensional model solve, through the eigenbasis against a dense factorisationA Kronecker sum's eigenvectors are the Kronecker products of its factors' eigenvectors, so the change of basis that diagonalises an operator with 7,776 rows is 5 changes of basis along 5 indices. The whole solve is a transform, 7,776 divisions and a transform back: 4.67·10⁵ multiplications at n = 6, against a dense factorisation's 3.13·10¹¹, a factor of 6.72·10⁵. The fitted exponent is 6.00 against 3d = 15. The only decompositions taken are of the 5 one-dimensional factors, which on the model problem are the same matrix — so there is exactly one, of size 6. Every solve reproduces its right-hand side to 1.73·10⁻¹⁵.110¹10²10⁴10⁶10⁸10¹⁰n, points along one axismultiplicationsa dense factorisationthrough the eigenbasis5 decompositions of an n × nunknowns7776multiplications4.7·10⁵dense factorisation3.1·10¹¹fitted exponent6‖Ax − b‖ ⁄ ‖b‖1.7·10⁻¹⁵nothing of size n^dis ever factorised

A Kronecker sum's eigenvectors are the Kronecker products of its factors' eigenvectors, so the change of basis that diagonalises an operator with 7,776 rows is 5 changes of basis along 5 indices. The whole solve is a transform, 7,776 divisions and a transform back: 4.67·10⁵ multiplications at n = 6, against a dense factorisation's 3.13·10¹¹, a factor of 6.72·10⁵. The fitted exponent is 6.00 against 3d = 15. The only decompositions taken are of the 5 one-dimensional factors, which on the model problem are the same matrix — so there is exactly one, of size 6. Every solve reproduces its right-hand side to 1.73·10⁻¹⁵.

What it checked while drawing

Every figure above checked its own claims on the way to being drawn, and a claim that failed would have stopped the picture rather than shipped a wrong one. Those checks 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.

17 distinct claims across 6 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 — checked 12 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 217 of 397 generators — 199 print a residual and 18 are exempt with a published reason; 180 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.

When the index is a tuple

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.

 When the index is a tuple

Five indices are cheaper than two

The same 4,096 unknowns cost 1.049·10⁶ multiplications indexed as a 64 × 64 grid and 1.966·10⁵ indexed as six axes of four. The dense factorisation that ignores the indexing costs 4.581·10¹⁰ at every one of them, and the residual improves in the same direction as the cost.

The whole library · All essays · What must fail