Numerical Linear Algebra
where the algebra stops being the arithmetic
Generator

circulant-spectrum

One function in the structure library, called 5 times across 3 essays. Below: what it draws at its defaults, what it draws at every value an essay asks for, the 7 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 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.

The 16 eigenvalues of a circulant, two waysA 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.024681012141610⁻¹1index kλthe transformthe eigensolverC = F* Λ F is a factorisationworst relative disagreement2.6·10⁻¹⁵‖Cx − b‖/‖b‖ from the transform solve4.7·10⁻¹⁶imaginary part of a real spectrum1.2·10⁻¹⁶n = 16, and the whole matrix is 16 numberseigenvectors known in advance

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 drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.

The 32 eigenvalues of a circulant, two waysA 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.04812162024283210⁻¹1index kλthe transformthe eigensolverC = F* Λ F is a factorisationworst relative disagreement4.4·10⁻¹⁵‖Cx − b‖/‖b‖ from the transform solve9.6·10⁻¹⁶imaginary part of a real spectrum1.9·10⁻¹⁶n = 32, and the whole matrix is 32 numberseigenvectors known in advance

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.

n: 16

The arguments are the ones The factor is not sparse 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.

The 16 eigenvalues of a circulant, two waysA 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.024681012141610⁻¹1index kλthe transformthe eigensolverC = F* Λ F is a factorisationworst relative disagreement2.6·10⁻¹⁵‖Cx − b‖/‖b‖ from the transform solve4.7·10⁻¹⁶imaginary part of a real spectrum1.2·10⁻¹⁶n = 16, and the whole matrix is 16 numberseigenvectors known in advance

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.

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.

7 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 transform and the eigensolver agree at n = 16 agree — asserted 2 times

a power-of-two size the transform can take

and the spectrum is real

Jacobi needs a symmetric matrix

the circulant is not singular

the fast transform is given a power-of-two length

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 52 of 99 generators — 37 print a residual and 15 are exempt with a published reason; 47 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.

Structure, and the solver that cannot see it

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.

 Sparsity, and what elimination costs

The 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 it

The 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⁻¹⁵.

The whole library · All essays · What must fail