Which Directions to Leave Wrong

Sixty-four directions, each with a name

Everything on this page happens inside one matrix — the suite's 1-D stiffness-and-precision operator, here at $n=64$ interior nodes, $h=\tfrac1{65}$. Small enough to print whole (at $n=8$):

$$h^2A\big|_{n=8}=\begin{pmatrix}2&-1&&&&&&\\[-2pt]-1&2&-1&&&&&\\[-2pt]&-1&2&-1&&&&\\[-2pt]&&-1&2&-1&&&\\[-2pt]&&&-1&2&-1&&\\[-2pt]&&&&-1&2&-1&\\[-2pt]&&&&&-1&2&-1\\[-2pt]&&&&&&-1&2\end{pmatrix}$$

Report 02 derived its eigenpairs from the three-term recurrence, in closed form:

$v_k(i)=\sin\dfrac{ik\pi}{n+1},\qquad \lambda_k=\dfrac{4}{h^2}\sin^2\!\dfrac{k\pi h}{2},\qquad k=1,\dots,n.$

Verified here to $1.4\times10^{-14}$ against the matrix and to $5.4\times10^{-16}$ against eigh: the modes are pure sine waves pinned at both walls, and the eigenvalues run from $\lambda_1=9.8677$ (a whisker under $\pi^2=9.8696$) to $\lambda_{64}=16890.13$ (a whisker under $4/h^2=16900$). Their ratio is the suite's villain: $\kappa=\lambda_{64}/\lambda_1=1711.66$.

The reason the whole suite keeps meeting these vectors: one number, $\lambda_k$, plays four different characters depending on which report you are standing in.

What gradient descent actually does: 64 races at once

Run Richardson / gradient descent on $\tfrac12x^\top Ax-b^\top x$ with a single step size $\alpha$: $x_{m+1}=x_m+\alpha(b-Ax_m)$. The error obeys $e_{m+1}=(I-\alpha A)e_m$, and because the sines diagonalize $A$, the iteration never mixes modes. Each coefficient runs its own private race,

$c_k(m)\;=\;(1-\alpha\lambda_k)^m\,c_k(0),$

and "convergence rate" just means the worst racer. The optimal single step is $\alpha=2/(\lambda_1+\lambda_{64})=1.183\times10^{-4}$, which balances the two extremes at $\rho=(\kappa-1)/(\kappa+1)=0.998832$. We ran it — actual GD from a known error mix with unit amplitude in every mode, every iterate projected onto the modes by the DST — and the measured coefficients sit on the predicted $(1-\alpha\lambda_k)^m$ to $4.0\times10^{-14}$, all 64 modes, all 400 iterations:

So $\kappa$ is not an abstract condition number; it is the length of the race between $\lambda_1$ and $\lambda_{64}$. Everything a preconditioner does on this page will be visible as surgery on this picture: move some $\lambda$'s, shorten the race.

Rotate all the way, and the problem falls apart

In mode coordinates $\hat x=V^\top x$ the energy is $\sum_k\bigl(\tfrac12\lambda_k\hat x_k^2-\hat b_k\hat x_k\bigr)$ — verified: $V^\top AV$ is diagonal to $3.9\times10^{-15}$ (relative), with the $\lambda_k$ on the diagonal. Sixty-four independent one-dimensional parabolas; nothing couples to anything. The whole solve is one division per axis, $\hat x_k=\hat b_k/\lambda_k$, and the rotation itself is the DST-I, a real-signal FFT costing $O(N\log N)$: transform, divide, transform back matches spsolve to $1.7\times10^{-15}$. In the probability column this same move is PCA whitening in the bridge's Karhunen–Loève basis (09 §4.3): independent components, rescaled.

That is the luxury option, and it is worth being clear about why the rest of the suite exists at all: the full rotation is only for sale on special matrices. The chain's eigenvectors are sines because the chain is translation-invariant with clean walls; perturb a coefficient (variable_poisson_2d), move to an irregular mesh, or just present a matrix you have never seen, and there is no fast transform waiting. A dense eigendecomposition costs $O(N^3)$ — more than the solve it would enable. Off the chain you cannot afford to be right about all $N$ directions. The honest question becomes: right about which ones?

Deflation: buy $p$ directions, damp the rest

Suppose the budget covers only $p$ eigenvectors — the $p$ floppiest, since §2 showed the slow lane is where GD bleeds. Solve exactly inside $\mathrm{span}(V_p)$, and on the orthogonal complement fall back to the best single scalar step for what remains:

$M_p^{-1}\;=\;V_p\Lambda_p^{-1}V_p^\top\;+\;\dfrac{2}{\lambda_{p+1}+\lambda_{64}}\,\bigl(I-V_pV_p^\top\bigr).$

The measured spectrum of $M_p^{-1}A$ is exactly the promised surgery: $p$ eigenvalues sitting at $1$ (exact to $10^{-14}$) and the tail rescaled to $\alpha_p\lambda_k$, already optimally centered. The effective condition number collapses to $\kappa_{\mathrm{eff}}=\lambda_{64}/\lambda_{p+1}$, and since $\lambda_k\approx\pi^2k^2$ at the bottom of the spectrum, each unit of rank pays quadratically: $\kappa_{\mathrm{eff}}\approx\kappa/(p+1)^2$ (measured ratio 1.0000 at $p=0$ drifting only to 1.0580 at $p=16$). Drag the budget yourself:

Sixteen directions out of sixty-four — a quarter of the basis — and the bill drops from 18224 iterations to 67, a factor of 272. Every row is a measured run, and every row obeys the same sentence: be exactly right about the $p$ directions you paid for, be honestly, symmetrically wrong about the rest.

The same surgery under gradient noise

One deliberately narrow detour toward optimization. Take the identical chain quadratic, but hand GD a noisy gradient: $g_m = Ax_m - b + \sigma\xi_m$ with $\xi_m\sim\mathcal N(0,I)$, $\sigma=1$, fixed seed, constant steps. Two runs, both measured. Plain: the optimal scalar step $\alpha$. Head-solved: each step, project the (noisy) gradient onto the $p=4$ floppiest modes and take the exact Newton step there — i.e. apply $M_4^{-1}$ from §4 — and the damped step on the tail.

Every preconditioner, audited in the same currency

The bridge explainer ends with a sentence this page exists to expand. Quoted exactly:

So: same chain, same starting error, same optimally damped Richardson/GD outer iteration, and six strategies run as preconditioners. Three measurements each: iterations to $10^{-10}$; the effective condition number $\kappa_{\mathrm{eff}}$ of $M^{-1}A$; and directions left wrong — how many of the 64 eigenvalues of the (optimally rescaled) $M^{-1}A$ land farther than 10% from $1$. The last column re-runs each method under CG, because the two solvers price wrongness differently (13): Richardson pays for the range of the spectrum, CG pays roughly one iteration per cluster.

Spectral deflation is the gold standard the others imitate. For a rank-$p$ correction aimed at Richardson, fixing the $p$ smallest eigenpairs is the best you can do — it is literally the surgery of §4, and the ledger shows everything else as an approximation to it. Its "56 wrong" is honest bookkeeping, not failure: the tail is deliberately spread across $[0.03,1.97]$, centered so its range, not its count, is optimized. That is why it wins the GD column at every rank while barely denting the CG column.

Coarse averages are cheap imitations of low modes — measurably good ones. Replace the four true sine modes with four flat block-averages (blocks of 16) in the same deflation formula, and the principal angles between the block-average space and the true bottom-4 eigenspace are $12.5^\circ,\,23.5^\circ,\,26.2^\circ,\,36.5^\circ$: never orthogonal, never exact. The price of imitation is precise: $\kappa_{\mathrm{eff}}$ 144.97 instead of 68.79, iterations 1640 instead of 733 — call it a factor of 2.2 for skipping the eigensolve. At $p=8$ (blocks of 8, largest angle $41.2^\circ$): 518 vs 229. This is the whole two-grid idea of 11/12 in one row: piecewise-constant functions approximately span the smooth end of the spectrum, and "approximately" costs a small constant, not the asymptotics.

Nyström leaves the wrong end wrong. The randomized sketch (python/nystrom.py, rank 8, seed 0) faithfully does its job: it captures the top of the spectrum — its eigenvalue estimates undershoot the true top eight, as Lemma 2.1 promises, with $\hat\lambda_8=9782.3$ — and deflates it. But on the Laplacian the top is the harmless end: $\kappa_{\mathrm{eff}}$ falls from 1711.66 to 1704.62, iterations from 18224 to 18156, and at rank 4 the run measures 18250 — slightly worse than nothing, transient noise included honestly. The bottom modes, where GD actually bleeds, stay exactly as wrong as before ($k=1$ is still the first wrong direction by the Rayleigh diagnostic). This is report 07's lesson relocated to 1-D and priced in the same currency as its competitors: Nyström is built for spectra that decay fast from the top (regularized ridge problems), and the chain is its adversarial case.

Domain decomposition leaves the fewest directions wrong — and the wrongest. Two exact half-solves (block-Jacobi on nodes 1–32 and 33–64) leave exactly two eigenvalues off $1$: the pair $1\pm\tfrac{32}{33}$ generated by the single severed bond, the smallest separator the suite's report 14 story ever meets. CG names those two exceptions and finishes in 3 iterations. Richardson cannot name anything: it pays the full range $\kappa_{\mathrm{eff}}=(1+\tfrac{32}{33})/(1-\tfrac{32}{33})=65=n+1$, and grinds for 663 iterations at rate $\tfrac{32}{33}=0.9697$. Same preconditioner, 221× apart — the sharpest clustering-versus-range contrast in the ledger.

IC(0) leaves nothing wrong — here. On the chain, zero-fill incomplete Cholesky is Cholesky: a path is a tree, elimination creates no fill, and the measured factor satisfies $LL^\top=A$ to $2.2\times10^{-16}$. Zero directions wrong, one iteration, by either solver. The honest caveat is that this perfection is a property of the 1-D graph, not of the method: on the 2-D grid the same pattern truncation discards real fill-in and IC(0) rejoins the imperfect field — 11 and 15 (step 5) measure exactly what that truncation costs.

Read down the "wrong" column and the coda stops being a slogan: 60, 60, 59, 58, 58, 56, 52, 2, 0 — every method is an answer to the same budget question, and where two counts tie (Nyström rank 4 against doing nothing, the two coarse ranks at 58) the "which directions" column is what still separates them. The two solver columns are two different prices for the same answer.

Where the suite has already met these directions