The circulant that cannot be indefinite

The previous essay in this field ends on a number that should not have been possible. Preconditioning a positive definite Toeplitz system with the circulant nearest to it — the standard method, with a theorem behind it saying the step count stops depending on n — took 109 steps against an unpreconditioned 66 at ρ = 0.95 and n = 64. The preconditioner was making things worse, and the reason was that its smallest eigenvalue was −0.173: the approximation to a positive definite matrix was not positive definite.

That essay left a question open in as many words, and the phase that wrote it recorded the question as a deferral: is an indefinite preconditioner a fact about circulant preconditioning, or about that particular circulant?

It is the second, and the settling takes one line of arithmetic.

Two circulants, and the line between them #

A Toeplitz matrix is constant along each diagonal. A circulant is too, and its diagonals wrap: entry (i, j) depends on (i − j) mod n. So a circulant has n free entries where the Toeplitz matrix has 2n − 1, and building one from the other means deciding what to do with the two diagonals — the kth sub-diagonal and the (n − k)th super-diagonal — that compete for each circulant slot.

Strang’s answer is to choose. Keep whichever of the two is nearer the main diagonal and discard the other; at the halfway point, where neither is nearer, put a zero. It is a projection in the plain sense: keep as much of each diagonal as fits.

T. Chan’s answer is to average, weighted by how many entries each diagonal contributes:

cⱼ  =  ((n − j)·t_j  +  j·t_{j−n}) / n

That formula is not a heuristic and it is worth seeing why, because the reason is the whole essay. The circulants form a linear subspace of the matrices, and the minimiser of a Frobenius distance to a linear subspace is the orthogonal projection onto it — which, entry by entry, averages over each residue class of the index. The weights (n − j)/n and j/n are the counts of entries in each class.

The consequence, in one sentence #

An average of positive quantities is positive; a choice between them need not be.

Every entry of the averaged circulant is a convex combination of entries of T’s own diagonals, and its eigenvalues are the transform of that vector. Measured across the sweep the previous essay used:

The averaged one’s margin shrinks with n, which is asserted rather than glossed: 0.0431 down to 0.0276 across the sweep. It is not comfortable — a preconditioner whose smallest eigenvalue is approaching zero is a preconditioner heading towards trouble — and it is a different situation from crossing.

What the step counts do #

Three things in that table, and the third is the one this field has been waiting for.

The wrapped circulant is worse than useless while it is indefinite. 55 steps against an unpreconditioned 37, 117 against 59, 122 against 99. Conjugate gradients requires a positive definite preconditioner — the derivation uses M⁻¹ to define an inner product, and an indefinite M has no inner product — so what runs in those rows is a method outside its own hypotheses.

It is excellent the moment it becomes definite. 9 steps at n = 256, better than the averaged circulant’s 10. Strang’s construction is a sharper approximation of the symbol where it works, and this table is not an argument that it is a bad idea.

And the averaged circulant delivers, at every size drawn, the thing this field’s organising finding says not to expect. The structure field exists because an asymptotic statement is not a statement about a computation: Szegő’s limit reached to 52% at n = 8, the O(1) step count arriving as 109. Here the O(1) arrives as 7, 8, 9, 10, 10 — at n = 16, where “asymptotically” has no business meaning anything.

That is worth having as a counter-case rather than an exception. The promise was never about circulant preconditioning in general. It was about a circulant that stays definite, and the literature’s habit of stating it without that condition is what made the previous essay’s measurement look like a refutation of a theorem rather than of a sentence.

The honest half: what never failing costs #

At n = 256 both circulants are definite and the wrapped one takes 9 steps against the averaged one’s 10. The trade is one step, it is real, and it is asserted:

the preconditioner that discards half of each diagonal is the sharper approximation where it works, and the one that averages them is the one that always works.

So the choice between them is not a choice between a good method and a broken one. It is the ordinary engineering trade — a slightly better typical case against a guarantee — with the unusual feature that the guarantee costs almost nothing and is available for free from a formula one line long.

And the flattering-looking half is not the one that decides it: the averaged circulant is also the nearer of the two in the Frobenius norm, at every size, since it is the minimiser by construction. That fact is the refusal this essay’s family runs, fed the claim that a nearer circulant is a better preconditioner — which at n = 256 is false by one step, on the same pair of matrices where it is nearer.

What the preconditioned spectrum looks like #

The step counts have to come from somewhere, and the somewhere is the spectrum of C⁻¹T.

Measured across the family, the averaged circulant’s preconditioned spectrum stays inside a range whose lower end barely moves: the smallest eigenvalue of C⁻¹T is 0.68 at ρ = 0.5, 0.56 at 0.8, 0.52 at 0.9 and 0.50 at 0.95, at every size from 16 to 64. The upper end grows — 1.9, 4.7, 8.8, 15.0 at n = 64 — so the preconditioned condition number is not constant either; it climbs slowly, and the step count climbs slowly with it.

That is the honest account of “O(1)”: not a constant, but a quantity growing so slowly that a factor of sixteen in the problem size costs three iterations. Compare the unpreconditioned column, which grows by a factor of 7.5 over the same range.

The measurement also says which quantity the step count follows, and it is not the one the theorems are stated about. At ρ = 0.95 and n = 64 the averaged circulant clusters nothing within a tenth of one — and takes 9 steps. What it does is keep the whole spectrum away from zero and inside a modest range. The clustering is what makes the asymptotic argument work; the boundedness is what makes the finite-size count small.

Why the wrapped one is indefinite at all #

One paragraph on the mechanism, because “it discards a diagonal” is not by itself an explanation.

A circulant’s eigenvalues are the discrete transform of its first column. The wrapped column is the Toeplitz decay ρ^k run up to the halfway point and then the mirror ρ^(n−k) — a sequence with a kink in the middle, and at even n a zero dropped in at exactly n/2 because two diagonals compete for one slot and Strang’s definition declines to choose. The transform of a sequence with a discontinuity has large oscillating components, and at the frequencies where those components exceed the smooth part the eigenvalue goes negative.

The averaged column has no kink: it decays from ρ⁰ towards the middle and back, continuously, because each entry is a weighted blend of the two competing values with the weights themselves varying continuously. Its transform is the transform of a smooth positive sequence.

So the two constructions differ by exactly the treatment of one seam, and the eigenvalue that goes negative is the one belonging to the frequency that seam excites.

What this settles about the previous essay #

Three things, and they are worth stating separately because only one of them was in doubt.

The measurement stands. 109 steps against an unpreconditioned 66 was correct, is reproducible, and is what the wrapped circulant does at that ρ and n.

The blame moves. It was recorded there as a property of circulant preconditioning, with the verdict asymptotic — a method whose promise holds in a limit and not at the sizes anybody runs. Half of that survives: the promise is asymptotic. The other half does not — the failure was one construction’s, and a different construction of the same kind, at the same sizes, delivers the promise in full.

And the site’s own habit is what found it. The whose-fault-is-it thread is normally about separating the algorithm’s contribution to an error from the problem’s. Here it separates a method’s contribution from a variant’s, which is the same move one level down, and it needed a second construction to be written and measured rather than an argument.

Why the averaged circulant is the minimiser, and why that is checked #

The formula in the second section is stated as the nearest circulant in the Frobenius norm, which is a claim rather than a definition, and this site’s habit is to compute a claim by a second route rather than to quote it.

The derivation is short. The circulants of a given size form a linear subspace of the matrices — closed under addition and scaling, with n free parameters. The Frobenius norm comes from an inner product. The nearest point of a linear subspace in an inner-product norm is the orthogonal projection onto it, and the projection here is an average: entry (i, j) of a circulant is determined by (i − j) mod n, so the entries of A that a single circulant entry has to represent are exactly those whose index difference lies in one residue class, and the least-squares choice is their mean.

The weights (n − j)/n and j/n are then a count rather than a design: of the n entries in residue class j, exactly n − j come from the jth sub-diagonal and j from the (n − j)th super-diagonal.

Two routes are computed and compared. optimalCirculant applies the weighted-average formula; nearestCirculantByFitting sets up an n²-row least-squares problem for the n free entries and hands it to this site’s own Householder QR, knowing nothing about diagonals. They agree to 2.2·10⁻¹⁶, 3.3·10⁻¹⁶ and 1.0·10⁻¹⁵ at three sizes. That is what makes “the minimiser” a measured claim here, and it is what would catch the plausible error in this construction — weights that are right in form and wrong at the ends, which no eyeball on a decaying sequence would see.

What the preconditioned spectrum does, and what it does not #

The step counts have to come from somewhere, and the somewhere is the spectrum of C⁻¹T. Measured across the family:

The lower end barely moves — it is near a half at every ρ and every size from 16 to 64 — and the upper end grows with ρ. So the preconditioned condition number is not constant either; it climbs slowly, and the step count climbs slowly with it. That is the honest account of “O(1)”: not a constant, but a quantity growing so slowly that a factor of sixteen in size costs three iterations, against an unpreconditioned count that grows by a factor of 7.5 over the same range.

The measurement also says which quantity the step count follows, and it is not the one the theorems are stated about. At ρ = 0.95 and n = 64 the averaged circulant clusters nothing within a tenth of one, and takes 9 steps. What it does is keep the whole spectrum away from zero and inside a modest range. Clustering is what makes the asymptotic argument work; boundedness is what makes the finite-size count small, and on this family the second arrives long before the first.

What is left #

The other circulant-like preconditioners. The ω-circulant and skew-circulant families, and the band-Toeplitz preconditioners, are the obvious neighbours; each replaces the wrapping convention with another and each has its own definiteness story.

A non-symmetric Toeplitz system, where conjugate gradients does not apply and the whole apparatus has to be restated for GMRES — at which point the definiteness question becomes a question about the field of values, and the clean sign argument above has no analogue.

And the second dimension, which is the next essay and where the averaged circulant survives and the theorem does not.