The switch does not know which side is better

An algebraic hierarchy begins with one number. Before any coarse variable is chosen, before any interpolation weight is computed, a threshold θ is applied to the ratio of each matrix entry to the largest off-diagonal entry in its row, and every coupling that survives is called strong. Everything downstream reads that verdict and nothing downstream revisits it.

On the anisotropic model operator — the five-point Laplacian with its horizontal couplings scaled by ε — the verdict is completely determined. A horizontal coupling has ratio ε and a vertical one has ratio 1, so a threshold below ε calls both strong and a threshold above ε calls only the vertical ones strong. The coarsening that follows takes exactly two forms: a chequerboard when everything is strong, and whole rows kept or dropped when only the vertical couplings are. The step is at θ = ε, at every anisotropy, and it is a step rather than a slope because ε and 1 are the only two ratios in the matrix.

That much the essay that first drew it already says, and says approvingly: on a matrix with a scale in it the threshold is a decision about that scale, where on an unstructured graph it is a number somebody guessed. This essay is about the case that argument calls the good one, and it finds a second failure inside it.

The switch is exact. What the switch does not carry is which of the two methods it is switching between is the better one — and that ordering reverses, at an anisotropy the switch itself passes through without any change at all.

The switch is exact and the two sides are two methods #

The scan behind that figure is built around ε rather than at fixed thresholds, because a fixed list run against a moving anisotropy spends most of its stops on one side and reports no switch at all. Nine multiples of ε are tried, from a tenth of it to forty times it, and each one is put through a complete hierarchy build and V-cycle solve.

At ε = 0.02 the thresholds below the switch return 0.4440, 0.4435, 0.4425 and 0.4502, and the thresholds above it return 0.1548, 0.1549, 0.0457, 0.0534 and 0.0556. Each side is flat to within its own noise and the two sides are nowhere near each other. The coarse sets confirm what the factors imply: below the switch the hierarchy keeps 481 of the 961 unknowns in a chequerboard, and above it 465 in whole rows. Those are the two objects the coarsening that reads the entries is choosing between, and the choice is made entirely by whether θ sits above ε or below it.

They are not two settings of one method. Full coarsening halves the unknowns in both directions and leaves a smoother that cannot damp error along the strong lines; semi-coarsening halves them in the strong direction only, which is the repair the geometric method has to be told about and this one infers. The coarse operators differ in shape as well as in size, so what the recursion solves below the top level is a different discretisation in the two cases — the effect the Galerkin product produces at every level, here arriving twice over from one threshold.

At this anisotropy the ordering is not in doubt. Reducing the residual by ten decimal digits takes 28.2 cycles on the full-coarsened side and 7.5 on the semi-coarsened one. The factor of 9.7 is the whole reason the strength test exists: it is what an unrepaired point smoother loses to anisotropy, recovered by a threshold that costs one pass over the entries.

The ratio is not a property of the method #

The 9.7 is a property of ε = 0.02, and swept across the anisotropy it does not hold. The best factor on each side of the switch, at nine anisotropies:

The semi-coarsened side barely moves across the whole sweep: 0.0490, 0.0481, 0.0469, 0.0457, 0.0525, 0.0482, 0.0839, 0.0818, 0.1279. It is the full-coarsened side that improves, from 0.51 to 0.06, and it improves for a reason that is not about the method at all. As ε rises the operator stops being anisotropic. At ε = 1 it is the isotropic Laplacian, on which full coarsening is the textbook method and a smoother has no direction it cannot see.

So the ratio collapses because the problem the repair was for is going away, and the repair keeps being applied.

The collapse is not smooth, and the reason is worth stating #

Read down the ratio column and the fall looks orderly. Filled in at every anisotropy that was run, it is not: 3.8 at ε = 0.10, then 3.34, 2.93, 2.41, 1.76 at 0.11 through 0.14, then 1.51 at 0.15 and 2.59 at 0.20, then 1.99 at 0.25 and 1.11 at 0.30. The trend is unmistakable and the sequence is not monotone, and a reader entitled to the trend is not entitled to the individual step.

The cause is in the scan and not in the method. The thresholds tried are multiples of ε, so the sample moves with the anisotropy, and each side’s best is a best-of-sample rather than a minimum over θ. At ε = 0.15 the two sampled thresholds above the switch are 0.24 and 0.45, returning 0.0983 and 0.0839; at ε = 0.20 they are 0.32 and 0.60, returning 0.1282 and 0.0460. The full-coarsened side meanwhile hardly moves at all between those two anisotropies, 0.1270 against 0.1192. So the whole of the wobble comes from which thresholds the sample happened to reach on the semi-coarsened side, and it belongs to the grid of thresholds rather than to either coarsening.

That is the honest caveat and it makes the essay’s claim sharper rather than weaker. The quantity that reverses is not a delicate one: it moves by a factor of twenty across the sweep, against a sampling wobble of 1.7, and the reversal is a change of sign rather than a change of size. A wobble cannot manufacture one.

The sign changes and the switch reports nothing #

At ε = 0.30 the two sides are a tie in everything but the fourth decimal place. At ε = 0.35 the ordering has reversed: the best factor above the switch is 0.0877 and the best below it is 0.0641, a ratio of 0.73. Full coarsening is now the faster method, and the crossing is located between ε = 0.33, where the ratio is 1.016, and ε = 0.34, where it is 0.975.

The point of the measurement is what happens to the switch across that crossing, which is nothing. At ε = 0.33 the coarsening below θ = ε keeps 481 unknowns in a chequerboard and the coarsening above it keeps 465 in whole rows; at ε = 0.34 it keeps 481 and 465. The strength test’s verdict on every coupling is unchanged, since ε has moved by a hundredth and the two ratios in the matrix are still ε and 1. The step in the curve is in the same place relative to ε, is the same height in the same direction, and separates the same two coarse sets. Every quantity the method computes on its way to a hierarchy is either constant across the crossing or moves through it smoothly.

The convergence factor is not one of those quantities. It is measured afterwards, by running the solve, and a code that has built a hierarchy has not run one.

Past the crossing the loss is as large as the gain was #

The reversal is not a marginal effect that then goes away. At ε = 0.40 the ratio is 0.45, at ε = 0.45 it is 0.44, and at ε = 0.50 it is 0.48 — full coarsening better by rather more than a factor of two, which is the same order of preference as the semi-coarsened side held at ε = 0.10.

The numbers behind the last of those are worth reading directly. At ε = 0.5 the best threshold below the switch is θ = 0.40, returning 0.0610, and the best above it is θ = 0.80, returning 0.1279. Ten digits of residual reduction take 8.2 cycles the first way and 11.2 the second. A code that chose its threshold to guarantee semi-coarsening — which is what a code that has read the strength literature does — has paid three extra cycles in every solve for a repair to a difficulty the operator no longer has.

The conventional threshold is on the wrong side in the middle #

Every treatment of the strength test gives θ = 0.25, and on this family that constant is doing something specific that neither its ubiquity nor the switch reports.

At ε = 0.25 the nearest threshold the scan reaches to the convention is θ = 0.20, and it returns 0.1492 against a best of 0.0528 — a factor of 2.83, or 12.1 cycles to ten digits against 7.8. Two separate things have gone wrong and they compound.

The first is the side. θ = 0.20 is below ε = 0.25, so it calls the horizontal couplings strong and coarsens fully, on a matrix where semi-coarsening is still very nearly twice as good: the best factor above the switch is 0.0528 and the best below it 0.1050. The convention lands on the losing side by five hundredths of a threshold, and it lands there because 0.25 is a constant and ε is a property of the problem — the two are equal at exactly one anisotropy and the constant has no way to know which one.

The second is that within the losing side it is not even the best. The full-coarsened thresholds at ε = 0.25 return 0.1050, 0.1094, 0.1493 and 0.1492 as θ rises, so the convention sits at the worse end of its own plateau, and the plateau is not flat here the way it was at ε = 0.02. The factor of 2.83 is therefore about 2.0 of wrong side and about 1.4 of wrong place on it.

The same constant behaves the same way on a matrix with no scale in it at all, where the graph Laplacian’s threshold scan finds θ = 0.25 ten times worse than θ = 0.20. The two findings are different in kind and that is the point: there, the constant is arbitrary because the matrix has no ε for it to be compared against; here the matrix has one, the comparison is exact, and the constant is still on the wrong side of it. Being meaningful is not the same as being right.

Measured in arithmetic the crossing moves, and it moves a long way #

A convergence factor prices a cycle. It does not price the cycle’s cost, and the two coarsenings do not cost the same.

The stored entries say so. At ε = 0.25 the full-coarsened hierarchies have operator complexities of 2.178 and 2.182 at their two best thresholds, and the semi-coarsened ones 3.442 and 3.504. A V-cycle costs one multiply-add per stored entry per sweep, so the semi-coarsened hierarchy performs 61% more arithmetic per cycle. Its first coarse level holds 465 unknowns against 481, so a count of unknowns says the two hierarchies are the same size to within 3% while the stored entries say one is half as expensive again — which is the disagreement between the two complexities that the cost of an algebraic hierarchy is built around, arriving here from a threshold rather than from a graph. The extra entries come from the Galerkin triple product run on a coarse set that is a set of whole rows, and from the extra level the row-wise coarsening needs before it runs out of unknowns.

Scoring each side by digits of residual reduction per unit of operator complexity, at the threshold on that side which maximises it:

The crossing in arithmetic is between ε = 0.13 and ε = 0.14, against ε = 0.33 and 0.34 in cycles. Two and a half times earlier in the anisotropy, and there is a whole band between them — every ε from about 0.14 to about 0.33 — in which the semi-coarsened side converges in fewer cycles and the full-coarsened side reaches the same accuracy for less work. At ε = 0.25 that reads 22.2 units of operator complexity against 27.4 for ten digits, while the cycle counts say 7.8 against 10.2 the other way.

So there is not one crossover but two, they are far apart, and which one a caller is on depends on a choice of currency that no part of the strength test makes. That is the sharpest available form of this essay’s claim: the threshold is one number, it decides between two methods exactly, and the question it is standing in for has two different answers depending on what is being counted.

What the operator looks like where the ordering turns #

The crossing is not arbitrary, and the coupling graph says what is happening to the matrix there.

At ε = 0.35 the horizontal coupling is 35% of the vertical one, and 0.35 is above 0.25, so the conventional threshold finds every coupling in the matrix strong — 110 in each direction, all of them. There is no weak direction left for the strength test to find, and the coarse set it produces is the chequerboard, with not one of the eleven rows kept or dropped whole.

That is the ordinary reading of the same figure. The reading this essay adds is that the anisotropy at which the strength test stops finding a weak direction at θ = 0.25, and the anisotropy at which full coarsening becomes the faster method, are within 0.09 of each other — 0.25 and 0.335 — and there is no mechanism connecting them. The first is a comparison of ε against a constant that appeared in the literature. The second is a property of how a V-cycle’s coarse correction interacts with a point smoother on a mildly anisotropic operator, and its value would be what it is if the constant had never been written down.

The near-agreement is a coincidence of this operator at this size, and it is exactly the kind of coincidence that makes a default look calibrated. Anything that displaced it — a different smoother, a different number of relaxations, a rediscretisation — would move one of the two numbers and not the other.

What follows for a code that has to choose #

The threshold cannot be read as a recommendation. It answers which couplings are strong, which on this operator it answers correctly at every ε and at every θ, and a code that treats the answer as advice about which coarsening to prefer is reading a classification as a comparison. The switch is exact and empty in the same sense the determinant is a scalar that decides nothing: a quantity that is perfectly well defined, computed without error, and not about the question it is being consulted for.

A default is a claim about a range of problems. θ = 0.25 is right on the anisotropies the strength test was calibrated on, where ε is 10⁻² or smaller and the gap between the sides is a factor of ten. It is on the wrong side of the crossing for ε between roughly 0.14 and 0.33 when work is counted, and it is losing a factor of 2.83 at ε = 0.25. The failure is not that the constant is a poor value; it is that a single constant is being asked to stand for a comparison whose answer depends on the matrix.

Two or three thresholds are cheap and one solve is not. The advice choosing a parameter without knowing the answer arrives at, in a field where the parameter is a regularisation, applies unchanged here: the scan that finds the crossing needs six solves and no reference solution, and the crossing is where a scan pays for itself. Anywhere the two sides are within 20% of each other, the choice does not matter and the scan says so at once.

And the other repairs are not on the same schedule. Line relaxation in the strong direction fixes the smoother rather than the coarsening, so it is unaffected by which side of the crossing the operator is on and becomes the better of the two repairs exactly where semi-coarsening stops being worth its arithmetic. Smoothed aggregation reads this identical strength graph, so it inherits the switch and the constant together, and whether it inherits the crossing as well is a separate measurement nobody has made.

Whatever the threshold kept, the interpolation then has to work with. The energy-minimising formula reproduces the classical weights on the model problem regardless of which coarse set it is handed, so no repair downstream of the strength test recovers a choice made wrongly at it. And the property both sides of the switch are trying to preserve is the one a rate that does not notice the size measures — a factor that stays constant as the grid refines — which both of them do keep, at every ε in this sweep, in the sense that matters most and settles least.

What is asserted, and what refuses #

The switch is at θ = ε, asserted as two statements rather than one: every threshold below ε produces a coarsening that keeps no row whole, and every threshold above it produces one in which every row is kept or dropped whole. Both are checked at each of the eight anisotropies the slider reaches, over the whole scan.

The scan straddles the switch, asserted before either side is read, so a figure whose thresholds all landed one side of ε refuses to be drawn rather than reporting a plateau as a curve.

At a real anisotropy the semi-coarsened side is far faster, asserted at ε ≤ 0.05 as a factor of at least 2.5 — which the measurement clears by a wide margin, at 9.7 — and at a mild one full coarsening is perfectly good, asserted separately for larger ε as a factor below 0.5. Two assertions rather than one, because the claim they encode is that the ordering is not fixed, and a single assertion in either direction would have had to be false somewhere in the sweep.

And the constant does what it says. The strength measure is built on the anisotropic operator at ε = 10⁻³ and required to find no horizontal coupling strong at θ = 0.25; the assertion that it finds one is fed that matrix and rejects it. That refusal is the counterexample to this essay’s own overreach. θ = 0.25 separates the strong direction from the weak one exactly as advertised, on the operators where the separation is the difficulty — and the measurement above is where the same constant, doing the same correct thing, is on the wrong side of a question it was never asked.