Coarsening in one direction only

The mode that breaks point relaxation on the anisotropic problem oscillates across the weak direction and is smooth along the strong one. The previous essay repaired that by changing what the smoother inverts. The other repair leaves the smoother exactly as it was and changes what the coarse grid is asked to hold.

The mode is smooth in y. A grid that keeps every x-position and takes every second y-position can represent it perfectly — it has all the resolution it ever had across x, and the mode does not need any across y. So coarsen only in y, and the mode that no smoother could damp is handed to a coarse grid that still has it.

The smoothing factor comes out 0.3340 at ε = 10⁻³ with the point smoother untouched. That is the same number line relaxation achieved, and the sameness is not approximate: across six values of ε and five weights, the largest disagreement between the two repairs’ smoothing factors is 4.4·10⁻¹⁶.

What semi-coarsening is, as an operator #

The transfer operators for full coarsening are the tensor product of the one-dimensional ones: bilinear interpolation, whose stencil is the outer product of (½, 1, ½) with itself, and full weighting, which is its transpose scaled by a quarter so that a constant restricts to a constant.

Semi-coarsening in y replaces one factor of that product by the identity:

P = I ⊗ P₁ᴰ,     R = ½ Pᵀ

so a coarse point interpolates to the fine point directly above and below it with weight a half, to itself with weight one, and to nothing else. Every fine x-position survives. The normalisation is a half rather than a quarter, because only one direction is being averaged over — getting that wrong scales the coarse correction rather than breaking it, which shows up as a convergence factor of 0.4 where 0.1 was expected and never as a failure.

The coarse grid is 31×15 rather than 15×15, so the hierarchy sheds unknowns half as fast and is the same depth. The coarse operator is built by the Galerkin product, as it is in every hierarchy in this phase, and for the same reason: there is no rediscretisation to compare against once the mesh spacings in the two directions differ.

Why the smoothing factor is the same number #

The region a coarsening leaves for the smoother is different in the two repairs and the answer is the same, which is the sort of coincidence worth either explaining or reporting as unexplained.

Under full coarsening the smoother is responsible for every mode with max(θx, θy) ≥ π/2 — three quarters of the square. Under y-semi-coarsening it is responsible only for θy ≥ π/2 — half of it, and a different half, containing every θx.

For the semi-coarsened method the damping factor is the point smoother’s, 1 − ω·A/(2ε + 2), and its extremes over that half-square are attained at (0, π/2) and at (π, π):

at (0, π/2):   A = 2,        D = 2ε + 2   →   1 − ω/(1 + ε)
at (π, π):     A = 4ε + 4,   D = 2ε + 2   →   1 − 2ω

For line relaxation under full coarsening the extremes sit at different frequencies — (0, π/2) and (π, 0) — and evaluate to the same two expressions, because at θy = π/2 the line splitting’s symbol 2ε + 4sin²(θy/2) equals the diagonal 2ε + 2 exactly, and at (π, 0) the line ratio is 2 just as the full-coarsened point ratio is at (π, π).

So both repairs have

μ = max( |1 − ω/(1 + ε)| , |1 − 2ω| )

identically, against the broken method’s max(|1 − ωε/(1+ε)|, |1 − 2ω|). Two mechanisms with nothing in common — one changes the smoother, the other changes the grid — produce the same symbol because each replaces the same ε by a one, in the same place. The scan confirms it at twelve digits and the closed form says why.

And then the convergence factors disagree #

At ε = 10⁻³ on a 31×31 grid the two repairs converge at 0.0370 and 0.1074 — a factor of 2.9 apart, from smoothing factors that agree to twelve digits.

This is the essay’s most useful result and it is a caution rather than a discovery. A smoothing factor is a statement about the smoother alone: how much of the error the coarse grid cannot see survives a sweep. A V-cycle is two components, and the two repairs give the coarse grid completely different jobs. Under full coarsening it handles a quarter of the frequency square and gets a correction with a nine-point operator on a grid a quarter the size; under semi-coarsening it handles half the square, on a grid half the size, with a different operator. Nothing in μ knows any of that.

So a reader given only the smoothing factors would have no way to prefer either repair, and there is a preference. The measured factors are what decide it, and the standard practice of comparing smoothers by their smoothing factor is a comparison of one component in a method with two.

The cost accounting pushes the same way and by less than the rate does, and it is worth having the numbers rather than the direction.

A semi-coarsened hierarchy on the 31×31 grid runs 31×31, 31×15, 31×7, 31×3, 31×1 — it sheds half its unknowns a level where full coarsening sheds three quarters. Its grid complexity is 1.839 against full coarsening’s 1.296, and its operator complexity 2.361 against 1.483. So a semi-coarsened cycle costs about 60% more than a fully coarsened one of the same depth, and line relaxation’s sweeps cost about twice a point sweep. The two penalties are the same size to within a factor of about 1.3, and the factor of 2.9 in the convergence rate is not.

The bottom of the hierarchy differs in kind rather than in degree, which is easy to miss. Full coarsening ends at a single unknown, so the “exact solve” at the bottom of every V-cycle in the isotropic essays is a division. Semi-coarsening ends at 31×1 — a one-dimensional problem with thirty-one unknowns, which has to be solved properly. Here that is a dense elimination on a tridiagonal-shaped matrix and costs nothing at these sizes; on a grid where the fine direction has a thousand points it is a thousand-unknown solve at the bottom of every cycle, and a hierarchy whose coarsest level grows with the problem is not obviously an O(N) method any more. The standard repair is to switch to full coarsening once the anisotropy has been coarsened away, which is a real design decision this phase does not make.

What each repair actually removed #

The two repairs have the same symbol and they do not do the same thing, and the difference is visible in what is left after a sweep rather than in any summary number.

Line relaxation removes the troublesome mode. After one y-line sweep the error’s component along θx = π, θy ≈ 0 has been multiplied by −⅓, so by the time the residual is restricted to the coarse grid that component is small, and the coarse grid never sees it. The hierarchy below is doing the job it does on the isotropic problem, on an error that looks the way isotropic errors look.

Semi-coarsening relocates it. After one point sweep the same component is still there at 99.87% of its size, and it is restricted to the coarse grid intact — where, because the coarse grid kept every x-position, it is represented exactly and the coarse operator can act on it. One level down, the same thing happens again: the mesh spacing in y has doubled, the effective anisotropy has therefore changed, and by two or three levels the problem the coarse operator poses is no longer anisotropic at all.

That is worth stating as the mechanism, because it is the one that generalises, and it is measurable: read the ratio of the horizontal to the vertical coupling out of each level’s Galerkin operator and watch it climb. On the 31×31 grid at ε = 10⁻³ it runs

a factor of about 3.7 per level, which is the h² the vertical direction is losing as its spacing doubles, arriving in the operator. Semi-coarsening works by making the anisotropy disappear down the hierarchy, and it reaches the bottom of this grid before the ratio reaches one. On a taller grid it would get there first, and the levels below that point are ordinary isotropic levels carrying an unnecessarily fine x-direction — which is exactly the design decision the previous paragraph flagged, arriving from the other side.

Both repairs are aimed, and this is what that costs #

Take the anisotropic problem and turn it through a right angle: put the ε on ∂²u/∂y² instead of ∂²u/∂x², so the strong direction runs along x. On a square grid that is the same problem reflected in the grid diagonal. Every eigenvalue is the same, the condition number is the same, and the matrix is a symmetric permutation of the original.

The y-line smoother goes from 0.0370 to 0.9667. Semi-coarsening in y goes from 0.1074 to 0.9663. Both repairs fail completely, on a problem they solve when it is presented the other way up.

That is the sharpest statement this sequence can make about what has actually been achieved. What the repairs encode is not “cope with anisotropy” but “cope with anisotropy along y”, and the direction was supplied by whoever typed the string. It is not read off the operator, nothing checks it, and the method converges either way — at 0.037 or at 0.967 — so the only symptom is a residual history somebody has to look at.

On a problem with spatially varying coefficients, no single direction is right everywhere and there is nobody to choose. Alternating line relaxation, which sweeps both directions, is the standard production answer and costs twice as much; it removes the need to choose and does not remove the premise that the strong direction is one of the two grid axes.

Forty-five degrees, where all of it stops #

Rotate the anisotropy properly — not by a right angle, but to 45°, so the strong direction runs along the grid diagonal. The operator becomes

−(a u_xx + 2b u_xy + c u_yy)

with a = c = (1 + ε)/2 and b = (ε − 1)/2, and its discretisation needs nine points rather than five. It is still symmetric to the bit. Two of its off-diagonal entries are positive, which puts it outside every M-matrix theory the field has, and outside the strength measure the next essays use.

Neither repair applies. A y-line inverts the vertical couplings, and the strong direction crosses them at 45°; coarsening in y throws away half of a direction that matters. Measured on the same 31×31 grid at ε = 10⁻³: line relaxation 0.784, semi-coarsening 0.883, against 0.037 for the same method on the aligned problem.

That is where this sequence stops and where the algebraic method begins — and the honest ending is that the algebraic method does not rescue it either. It manages 0.844, which is worse than the geometric line smoother it was brought in to replace, and the reason is locatable: the nine-point discretisation of the rotated operator has axis couplings of −0.5005 and a strong-direction coupling of −0.2498. The matrix’s largest entries are not in the equation’s strong direction. A method that reads the matrix cannot recover an anisotropy the discretisation did not encode.

Which repair to reach for #

The measurements support a rule, and it is worth stating because neither repair dominates.

If the strong direction is known and fixed, use line relaxation. It converges three times faster per cycle, its hierarchy is the cheaper of the two in both complexities, and it degrades gracefully towards the isotropic method as ε rises. Its cost is a sweep that is about twice as expensive and an implementation that has to solve tridiagonal systems.

If the anisotropy is strong enough that the smoother becomes a solver, notice. At ε = 10⁻³ the line smoother alone converges at 0.083 a cycle, so the hierarchy is contributing a factor of two and not the method’s usual factor of ten. That is a sign that the problem has decoupled, and a one-dimensional direct solve along each line may be the honest answer rather than a multigrid one.

If the strong direction varies in space, neither of these is the answer and the next two essays are. What both repairs share is that a human chose the direction, and the whole content of the algebraic construction is that the choice can be read out of the matrix instead — which is worth two essays because it turns out to be both achievable and expensive.

What is asserted, and what refuses #

The two repairs have the same smoothing factor, at six values of ε and five weights, to 4.4·10⁻¹⁶, with each checked against its own closed form to 10⁻⁹.

Both are aimed. The four numbers — 0.0370 and 0.9667, 0.1074 and 0.9663 — are asserted as a pair, so that “it works” and “it stops working when the problem is turned over” are one check rather than two.

The algebraic method is not aimed, asserted in the same call: 0.0484 and 0.0485 for the two orientations, agreeing to a thousandth.

And the two convergence factors differ, asserted as ratio > 2 rather than left as a remark, so that a change which accidentally made the two repairs identical would fail rather than pass more easily.

Semi-coarsening in the weak direction is refused. The claim that coarsening x repairs the smoother is fed to rejects() and reports 0.9993 — the same number the broken method gets.

What is left #

Alternating line relaxation and alternating semi-coarsening, both of which remove the choice of direction at a factor of two in cost and neither of which is measured here.

The rotated operator, at 0.784 for the best method in this essay and 0.844 for the best in the next two. The phase’s honest stopping point.

Convection. An operator with a first-derivative term large enough to matter is not symmetric, and every Fourier argument in these four essays assumes a symmetric stencil. That is a different subject and it deserves its own measurements rather than a paragraph borrowed from this one.