Where one step stops being enough

A zero no twist can step around solved the squared Laplacian — the pentadiagonal band $[1, -4, 6 + s, -4, 1]$, whose symbol $(2 + s - 2\cos\theta)^2$ has a zero of fourth order — through a circulant that matches it except in its corners, corrected for the corners by a rank-four Woodbury update, and found the fast route 18 to 34 times less accurate than elimination. The wrap’s samples cannot stay further than $\pi/n$ from the symbol’s zero, whatever twist is applied to them, so the wrap is as badly conditioned as the band itself and its condition number grows as $n^4$.

One step past the zero repaired that with one step of iterative refinement — form the residual with the band, solve for a correction by the same fast route, add it — and found the refined route within 0.59 to 1.40 times elimination’s error at every size from 16 to 128, with further steps going no lower. Its account: if the fast solve is backward stable to about $\kappa(\text{wrap})\,u$, each step multiplies the error by about that, and one step suffices while the product is well below one. Its prediction, left open: a zero of higher order raises $\kappa(\text{wrap})$ faster — as $n^{2p}$ for the $p$-th power of the Laplacian’s symbol — so higher powers reach the boundary at sizes that can be measured, and there one step should stop being enough.

Five powers of one symbol #

The bands measured are the Toeplitz matrices whose symbols are $(2 + s - 2\cos\theta)^p$ for $p$ from 2 to 6 with $s = 10^{-8}$: bandwidth $p$, the coefficients of $(2 + s - z - z^{-1})^p$, the second power being the earlier essays’ pentadiagonal band. Each is solved at sizes 16, 32, 64 and 128 through its circulant wrap twisted by half a step, which keeps every sample of the symbol off the zero at $\theta = 0$, with the wrap’s $2p$ corner rows removed by a Woodbury correction of rank $2p$ — a small dense capacitance system, solved by complex elimination with pivoting, as the correction lost to its own two-by-two solve found it must be. The corrected solution is then refined six times, each step’s residual formed with the band itself. Five known answers are drawn at each size and the medians reported; elimination with partial pivoting on the same band is the reference.

The wrap’s condition number follows from its samples, $(2 + s - 2\cos\theta_k)^p$ at $\theta_k = (2\pi k + \pi)/n$: the smallest is near $(\pi/n)^{2p}$, the largest $4^p$, so $\kappa(\text{wrap})\,u$ grows by $2p$ decades for each decade of $n$ — from $1.2\cdot 10^{-12}$ to $4.9\cdot 10^{-9}$ across the sizes at the second power, and from $1.3\cdot 10^{-4}$ to $9.5\cdot 10^{6}$ at the sixth.

The grid of steps #

At the second and third powers one step suffices at every size, as the earlier essay found for the second. At the fourth power one step suffices at 16 and 32 points and two are needed at 64. At the fifth power three steps are needed at 16 and 32 points; at the sixth, three at 16. Beyond those, the route has no first solve at all: at the fourth power and 128 points, the fifth at 64 and the sixth at 32, the wrap’s condition number has passed $10^{15}$, the fast solver refuses a circulant that singular, and only elimination still returns an answer — with errors of $10^{-5}$, $3\cdot 10^{-6}$ and $8\cdot 10^{-8}$, poor but not nothing.

So the boundary the earlier essay predicted is there, and it arrives about where the argument placed it: the route stops once $\kappa(\text{wrap})\,u$ reaches about a tenth, and the sizes at which that happens fall from beyond anything measured at the third power to 128 points at the fourth, 64 at the fifth and 32 at the sixth. The rule that one step suffices while the product is small is another matter. Read the grid by its κu values and it contradicts itself: the fifth power at sixteen points, with $\kappa u = 1.3\cdot 10^{-6}$, needs three steps, and the third power at 128 points, with $\kappa u = 3.2\cdot 10^{-5}$ — twenty-five times larger — needs one.

A contraction and a starting point #

The error curves separate the two halves of the account. At the fifth power and sixteen points the first solve’s error is $1.6\cdot 10^{-4}$; one step takes it to $1.2\cdot 10^{-10}$, a factor of $7.5\cdot 10^{-7}$ — about half of $\kappa(\text{wrap})\,u$ — and it then sits a little above elimination’s $4.1\cdot 10^{-11}$, reaching twice that on the third step. At thirty-two points the first solve’s error is 1.7 — no digits at all — and the steps divide it by about $10^{-3}$ each, as κu says they should: $9.5\cdot 10^{-4}$, then $7.7\cdot 10^{-7}$, then $1.2\cdot 10^{-8}$, elimination’s level.

That half of the account holds everywhere it can be tested. Where a single step does not land on elimination’s floor — at the fourth power and 64 points, the fifth at 32, the sixth at 16 — it multiplies the error by 0.08, 0.41 and 0.15 of $\kappa(\text{wrap})\,u$. A step is a solve by the same route, the route is backward stable to about $\kappa(\text{wrap})\,u$, and the correction it computes is accurate to that fraction of itself. The earlier essay’s mechanism for the contraction is right.

What it assumed without measuring was the starting point. The number of steps is how many contractions of size $\kappa u$ it takes to go from the first solve’s error to elimination’s, and one step is enough only if the first solve’s error times $\kappa u$ is already below elimination’s error. The earlier essay found the first error at a tenth to three tenths of $\kappa(\text{wrap})\,u$ on the second power, which made the first solve’s error and the contraction the same number and hid the difference between them.

The arithmetic can be checked on the cell the rule got most wrong in the other direction. The third power at 128 points has $\kappa u = 3.2\cdot 10^{-5}$ and a first error of $3.6\cdot 10^{-4}$, eleven times $\kappa u$ and three and a half digits. One contraction by about $\kappa u$ takes that to about $10^{-8}$, and elimination’s own error on that band is $3.2\cdot 10^{-8}$ — so one step lands on the floor, and it does: $4.3\cdot 10^{-8}$ after the step. A larger $\kappa u$ than the fifth power’s sixteen-point cell, a smaller first error relative to the target, and one step instead of three. The count is a ratio of logarithms — of the distance from the first error to the target, over the contraction per step — and $\kappa u$ is only its denominator.

The first solve departs from κu #

The first solve’s error is not $\kappa(\text{wrap})\,u$ at higher powers, and it departs from it more the higher the power and the larger the size. At the second power it is 0.16 to 0.35 of $\kappa u$ — the earlier finding. At the third, 2 to 11 times $\kappa u$. At the fourth, 10, 101 and 219 times. At the fifth, 127 and 1,246 times; at the sixth, 564 times at sixteen points. The departure is what the grid’s apparent contradiction is made of: the fifth power at sixteen points starts 127 times above its $\kappa u$, three steps’ worth of distance at a contraction of $10^{-6}$ each once elimination’s own floor is taken into account, while the third power at 128 points starts eleven times above a larger $\kappa u$ and one contraction covers it.

Where the departure comes from is the Woodbury correction, which is where the higher powers differ from the second in kind and not only in degree. The correction’s rank is twice the bandwidth — four for the second power, twelve for the sixth — and the wrap’s intermediate solution, before the correction removes the corners’ effect, is larger than the answer by a factor that grows steeply with the power: the median ratio is 72 to $1.1\cdot 10^5$ at the second power across the sizes and $1.5\cdot 10^{10}$ at the sixth power’s sixteen points. The correction subtracts two large vectors to leave a small one, and the rounding of the large ones is what the first error carries. The error measured is far below what that cancellation would permit in the worst case — the rounding of the large vectors mostly lies in directions the correction removes along with them — so the ratio bounds the departure without predicting it; a measure of the departure itself is left open.

Where the route stops #

The boundary itself is the part of the prediction that holds cleanly. The product $\kappa(\text{wrap})\,u$ rises by $2p$ decades per decade of $n$ — the slopes of the lines are 4, 6, 8, 10 and 12 — and the route has no first solve once it passes a tenth, the level at which the circulant’s own eigenvalue solve refuses. The second power never approaches it at these sizes and would not before $n$ in the tens of thousands; the sixth crosses it between sixteen and thirty-two points.

The refinement never helps near the boundary either, even where a first solve exists: at the fourth power and 64 points $\kappa u$ is $8.4\cdot 10^{-4}$, each step buys three decades, and two steps are needed only because the first solve started at 0.18, with barely one correct digit. At that point elimination’s own error is $3.6\cdot 10^{-8}$ and the fast route reaches it — refinement recovered six decades the first solve had lost — but a route that needs two full solves plus two residuals to match one elimination has lost the reason it was faster.

The arithmetic of refinement with an inexact solver #

None of this is peculiar to circulants. Refinement with a solver that is accurate only to some level ε — a factorisation in lower precision, an approximate preconditioner, a fast transform with a correction — contracts the error by about $\kappa\,\varepsilon$ per step, where κ is the condition number the solver’s own backward error is amplified by, and the number of steps is the number of such contractions between the first solve’s error and the target. The part of a solver that may be rounded measured the mixed-precision version: a preconditioner computed with a three-bit significand still reached thirteen digits, at the cost of extra iterations, because the contraction per step was small enough even with so crude a solver. The standard theory of that version takes the first solve’s error to be about $\kappa\,\varepsilon$ as well, and then the steps needed are set by $\kappa\,\varepsilon$ alone.

The measurement here is a case where that last assumption fails. The fast route’s contraction is governed by the wrap, but its first error is governed by something else — the correction’s cancellation — and the two separate as the power grows. Doing it twice found a second pass of Cholesky QR repairing a first pass whose error was far larger than the second’s contraction would suggest; it is the same division between what a step contracts by and where the steps start, seen from the repair’s side. A rule for the number of steps that reads only the contraction will undercount whenever the starting error has a source of its own.

What the account should say #

The rule the earlier essay gave was one number: one step suffices while $\kappa(\text{wrap})\,u$ is small. The measurement replaces it with two.

The contraction per step is about a tenth to a half of $\kappa(\text{wrap})\,u$, as the account said, and this is what makes refinement converge at all; near $\kappa u \approx 0.1$ it stops being a contraction worth having and the route stops.

The first solve’s error is its own quantity, a tenth of $\kappa u$ at the second power and up to a thousand times $\kappa u$ at the fifth, set by the correction’s cancellation rather than by the wrap alone. The steps needed are the number of contractions between that error and elimination’s, and nothing about $\kappa u$ by itself predicts them.

The practical reading follows directly: measure the first solve’s residual, not the wrap’s condition number. The residual of the first solve against the band is computable at the cost of one band multiplication, and together with the contraction factor it says how many steps the route will need before any of them is taken. The matrix that is one row solved a circulant in one transform with nothing to correct; at the sixth power the same transform needs a rank-twelve correction and three refinement steps, and the arithmetic that was the reason to use it has been spent.

What the steps cost #

The route’s appeal is its cost: a band of width $p$ solved by elimination costs about $np^2$ operations, the twisted circulant by two transforms of $n \log n$, and the correction adds $2p$ further wrap solves — one per corner row — and a capacitance system of order $2p$. Those $2p$ solves do not depend on the right-hand side and can be kept for every refinement step, so a step costs one band multiplication, one wrap solve and a small dense solve. At the second power the whole refined route is one solve plus one step; at the sixth it is twelve kept solves, the first solve and three steps, against an elimination whose cost grows only as $p^2$. The circulant the problem did not contain priced the tridiagonal case as a transform and a two-by-two correction and found the cost claim exact; at higher powers the claim survives in its asymptotic form and loses its constant.

What five bands do not show #

Five powers of one symbol, four sizes, one twist, one shift. The powers of the Laplacian’s symbol have one zero, at $\theta = 0$; a band whose symbol has zeros at several frequencies would put several samples near zeros at once, which two near-zeros cost less than one found could help as well as hurt. The criterion “within twice elimination” is a choice, and at the fifth power and sixteen points the first three steps land at 2.8, 2.2 and 1.7 times elimination, so a criterion of three times would count one step there. The departure of the first error from $\kappa u$ is measured and bounded, not derived. Every number is the median of five known answers drawn at each size; the draws do not agree exactly, so a single cell’s step count could move by one with a different set of answers, while the grid’s pattern — one step at low powers, three at high ones, no route past the boundary — does not.

Still open: predicting the first error, and splitting the power #

A measure of the first error. The first solve’s error departs from $\kappa(\text{wrap})\,u$ by up to a thousandfold, below what the correction’s cancellation permits. The prediction with a sign is that the departure is the condition number of the rank-$2p$ capacitance matrix times $u$, which grows with the power for the same reason the wrap’s does; it is one extra number per solve to compute and compare.

Splitting the power. The $p$-th power’s band is nearly the product of $p$ tridiagonal Laplacians, each of which the twisted route solves to within a few times elimination with a rank-two correction. Solving the product as $p$ successive fast solves, with the boundary rows corrected at the end, compounds $p$ small errors instead of inheriting a zero of order $2p$; whether that stays within one refinement step at the sixth power and 128 points, where the single wrap has no first solve, is the direct comparison.

A shift that grows with the size. Every band here is shifted by $10^{-8}$, so the symbol’s minimum is set by the samples’ distance from zero. A shift of order $(\pi/n)^2$ — what a discretised operator with a physical length scale would carry — would hold $\kappa(\text{wrap})$ constant as $n$ grows, and should hold the steps needed constant with it.