The 16 eigenvalues of a circulant, two ways
At its defaults it draws the 16 eigenvalues of a circulant, two ways. A circulant matrix of size 16 has its eigenvalues in closed form: they are the discrete Fourier transform of its first column. Plotted against an eigensolver's answer for the same matrix, the two curves lie on top of each other to 2.6·10⁻¹⁵ relative. The eigenvectors are the same for every circulant of this size and are known before any entry is looked at.
circulant-spectrum is one function in lib/figures/structure.js —
structure — the matrix that is one row, and the solver that cannot see it. 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 circulant matrix of size 16 has its eigenvalues in closed form: they are the discrete Fourier transform of its first column. Plotted against an eigensolver's answer for the same matrix, the two curves lie on top of each other to 2.6·10⁻¹⁵ relative. The eigenvectors are the same for every circulant of this size and are known before any entry is looked at.
n: 32
The arguments are the ones A limit the matrix never reaches passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
A circulant matrix of size 32 has its eigenvalues in closed form: they are the discrete Fourier transform of its first column. Plotted against an eigensolver's answer for the same matrix, the two curves lie on top of each other to 4.4·10⁻¹⁵ relative. The eigenvectors are the same for every circulant of this size and are known before any entry is looked at.
show: "zero-symbols"
The arguments are the ones A zero no twist can step around passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
On logarithmic axes, the symbol of the Laplacian, 2 + s − 2cos θ, and of its square, against θ from 10⁻³ to π, with s = 10⁻⁸. Dots mark the first six samples of the wrap twisted by half a step, at odd multiples of π/64. The nearest sample, at θ = π/64, sees 0.00241 on the Laplacian and 5.8·10⁻⁶ on its square, against largest values of 4 and 16: the wraps' condition numbers are 1660 and 2.76·10⁶.
show: "zero-symbols", n: 32
The arguments are the ones A zero no twist can step around passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
On logarithmic axes, the symbol of the Laplacian, 2 + s − 2cos θ, and of its square, against θ from 10⁻³ to π, with s = 10⁻⁸. Dots mark the first six samples of the wrap twisted by half a step, at odd multiples of π/32. The nearest sample, at θ = π/32, sees 0.00963 on the Laplacian and 9.27·10⁻⁵ on its square, against largest values of 4 and 16: the wraps' condition numbers are 415 and 1.73·10⁵.
show: "zero-twist", n: 64
The arguments are the ones A zero no twist can step around passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
The twist φ as a fraction of a half-step, π, from 0.05 to 1, on the Laplacian with its rank-two correction and on its square with its rank-four one, the capacitance systems solved with pivoting; median relative error over five right-hand sides, beside elimination on each band. On the squared Laplacian the best twist, 0.9 of a half-step, gives 5.58·10⁻¹¹ against elimination's 2.54·10⁻¹², 22 times; on the Laplacian a half-step gives 4.6·10⁻¹⁴ against 1.12·10⁻¹⁴.
show: "zero-law"
The arguments are the ones A zero no twist can step around passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Each filled dot is one twisted case — four sizes at a half-step twist on the Laplacian and its square, and seven twists at n = 64 on the square — its median error against κ(wrap)·u. The error is between 0.08 and 0.30 times κ(wrap)·u in every case. Open dots are the cancellation times u for the same cases, the loss the rank-two and rank-four measurements found to be the whole of it; on the squared Laplacian they sit 25 to 115 times below the error.
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.
106 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.
elimination on T is at rounding at σ = 10^-1, n = 64 — checked 36 times
the anti-periodic correction holds at σ = 10^-1, n = 64 — checked 12 times
the error is the cancellation times κ(S) times u at σ = 10^-5, n = 64 — checked 5 times
κ(S) is κ(C)/n at σ = 10^-5, n = 64 — checked 5 times
the transform and the eigensolver agree at n = 16 agree — checked 4 times
and by σ = 10⁻¹⁰ it has lost at least four digits elimination did not, n = 64 — checked 3 times
the correction is at rounding where C is well conditioned, n = 64 — checked 3 times
a double or a simple zero
a landed-on pair leaves the capacitance matrix perfectly conditioned
a landing twist the figure is drawn at
a power and size the sweep draws
a power the dial draws
a power-of-two size from 8 to 256 the transform takes and the sweep can afford
a power-of-two size the transform can take
a reading of the circulant this generator draws
a single landed-on mode does not
a size the refinement is measured at
a size the twist sweep measures: 16, 32, 64 or 128
a twist inside one turn
a way of solving the two-by-two capacitance system
and the first pass contracts by about the error itself
and the pair is the one whose two landing twists coincide
and the single mode costs three orders more at the same κ
and the spectrum is real
at σ = 10⁻¹⁰ refinement diverges, n = 64
at σ = 10⁻⁸ refinement reaches rounding in three passes, n = 64
at σ = 10⁻⁸ the two solves differ by more than four orders
both pairs landed leave κ(S) at one
every landing's error is within a hundred times the cancellation's
few enough samples to see
Jacobi needs a symmetric matrix
LU is for square matrices
no sample sits exactly on the zero — the picture is of a nearly singular wrap, not a singular one
one pass settles the pivoted solve and not Cramer's
the band elimination meets no zero pivot
the best twist is at least as well conditioned as T
the best-conditioned twist on the grid is the one read off the symbol
the circulant is not singular
the Dirichlet samples give T's condition number agree
the fast transform is given a power-of-two length
the forward error or the capacitance matrix's κ
the pair's determinant does not cancel
the pivoted solve's error is the cancellation's at every landing
the twisted circulant is not singular at this φ
the two simple-zero wraps are matched in κ at each distance
Against the rule
It draws a decomposition and prints its residual. It calls
jacobiEigSym, circulantSolve,
and every figure above carries the badge — which residualcheck verifies by looking
for it in the emitted SVG rather than by finding the call that builds one. A badge that is
constructed and then left out of the body is the failure that check exists for.
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.
A limit the matrix never reaches
Szegő's theorem gives a Toeplitz family's condition number in closed form — ((1+ρ)/(1−ρ))², which is 81 at ρ = 0.8. The 8×8 section reaches 52% of it, the 128×128 reaches 98.9%, and none of them ever arrives. A statement about a family is not a statement about the matrix in front of you.
Structure, and the solver that cannot see itA zero no twist can step around
Solved through its circulant wrap with the small capacitance system factorised stably, a banded matrix was found to lose only what the cancellation in the correction costs, and a twist of half a step kept that cancellation near one. That holds only while the cancellation is large. With it kept small, the corrected solve's error is a quarter of the wrap's condition number times u on every case measured — and on a symbol with a zero of fourth order, the square of the Laplacian, no twist can keep the wrap well conditioned, because the nearest sample any twist can reach sees (π/n)⁴. At n = 64 the corrected solve is 34 times less accurate than elimination, where the Laplacian's is four.
Structure, and the solver that cannot see itOne step past the zero
The squared Laplacian, solved through its twisted circulant and a rank-four correction, lost 6 to 34 times more accuracy than elimination, because its symbol's fourth-order zero keeps the wrap as ill conditioned as the matrix whatever the twist. One step of iterative refinement — a residual formed with the band itself, a second solve by the same route — takes it to 0.59, 0.68, 0.73 and 1.40 times elimination's error at n = 16, 32, 64 and 128, and the second and third steps go no lower. The loss the zero imposed was the solver's, and a solver's loss is what refinement removes.
Structure, and the solver that cannot see itThe circulant the problem did not contain
A matrix that differs from a circulant in two corner entries can be solved through the circulant, by a transform and a two-by-two correction, and the cost claim is exact. The accuracy claim is not. On tridiag(−1, 2 + σ, −1), whose condition number stops at 1,712, the correction is wrong by 1.2·10⁻⁴ at σ = 10⁻⁸ while elimination is right to 1.1·10⁻¹⁴ — because the periodic neighbour is singular at σ = 0 and the two-by-two system inherits that. Solved by Cramer's rule, as here, the two amplifications multiply; a later measurement found that a pivoted solve of the same two-by-two system removes the second.
Structure, and the solver that cannot see itThe correction lost to its own two-by-two solve
Solving a band matrix through a circulant and a small correction was measured losing the answer to 10⁻⁴ where elimination kept it to 10⁻¹⁴, and a wrap that landed one sample on a zero was measured costing four orders more than one that landed a pair. Both measurements solved the two-by-two correction system by Cramer's rule. Solved with a row interchange, the corrected solve on the same matrix loses 2.9·10⁻¹⁰ — the cancellation, and nothing multiplied onto it — and the single landing costs what the pair costs. The loss was in the determinant.
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⁻¹⁵.
Structure, and the solver that cannot see itTwo near-zeros cost less than one
Solve a well-conditioned tridiagonal matrix through a nearly singular wrap and the correction's accuracy is not set by how singular the wrap is. At κ = 4·10⁷ one wrap returns the answer to 8.8·10⁻¹¹ — better than κ·u — and another, at κ = 3.8·10⁷, returns it to 3.3·10⁻⁶. The difference is how many of its samples sit near the symbol's zeros. A real wrap lands on a conjugate pair, a rank-two correction absorbs the pair exactly, and its two-by-two system has condition number 1.00 — which mattered because that system was solved by Cramer's rule; solved with pivoting, the single landing costs what the pair costs.
Structure, and the solver that cannot see itWhere one step stops being enough
One step of iterative refinement took the squared Laplacian's circulant-wrap solve to elimination's accuracy at every size, and the account was that each step multiplies the error by the wrap's condition number times the rounding, so one step suffices while that product is small. Raised to higher powers, the band tests the account and half of it holds: each step does contract by about κ(wrap)·u. The other half fails. The fifth power at sixteen points needs three steps with κ(wrap)·u near 10⁻⁶, where the third power at 128 points needs one with thirty times more, because the first solve starts up to a thousand times further from the answer than κ(wrap)·u says.