How much direction there was to lose

Smoothed aggregation is the method a practitioner reaches for when anisotropy is the difficulty, and on a 31×31 grid it converges at 0.1935 a cycle when the strong direction lies along a grid axis and at 0.7894 when the same operator is turned through 45°. The essay that measured it located the fault in the discretisation rather than in the hierarchy: at 45° the standard nine-point stencil puts its largest couplings on the grid axes and only half as much along the direction the anisotropy actually runs in, so every strength decision the method makes afterwards is made on the wrong pair of neighbours.

That was one anisotropy on one grid. A diagnosis taken at a single setting names a cause and leaves its size unmeasured, and the two are separable here because the diagnosis has two halves that can be read independently. The defect is a statement about the matrix: which neighbours the strength test calls strong, and how far wrong that is. It is available before any solver runs. The damage is a convergence factor: what the resulting hierarchy costs. At ε = 10⁻³ on that one grid the two were read together and reported as one finding.

Swept, they come apart, and they come apart in the direction that settles what kind of failure this is. The defect does not move at all. From ε = 10⁻⁴ to ε = 0.099 the rotated operator’s strength graph gives every interior point exactly six strong neighbours, the aggregation returns 121 aggregates from 961 points at every one of those settings, and the partition is not merely the same size but the same partition — the owner of every point is identical, index for index, across four decades. The method makes one decision and it makes it everywhere.

The damage produced by that one decision runs from 0.8024 to 0.5810.

A solver that could not handle a direction would fail by about the same amount wherever the direction was. This one fails in proportion to how much direction there was to lose, on a hierarchy that never changes, which is the signature of information destroyed upstream rather than of a method that is bad at something.

The control is a method that keeps the direction #

The figure above is the aligned case measured with a different instrument — a local Fourier smoothing factor rather than a full solve — and it is here because it fixes what “how much direction there was to lose” means as a quantity.

Read it at the left edge. At ε = 10⁻⁴ the point smoother’s factor is 0.9999: the anisotropy is severe enough that a pointwise relaxation removes essentially nothing, which is the failure the whole anchor begins from. Read the two repair curves at the same place and they are at 0.6000 at this weight, flat, and indistinguishable from each other. Whatever ε is, a method that has the direction is unaffected by how strong the direction is.

That coincidence is itself measured rather than assumed: line relaxation and semi-coarsening return the same smoothing factor at every ε drawn and every weight the slider reaches, to 3.7·10⁻¹³ here and to zero at ω = ⅔, which is the closed form both of them reduce to written twice.

So the aligned column of every table below is a control in the strict sense. It is not that the aligned problem is easy; at ε = 10⁻⁴ it is the hardest problem in the anchor for anything that does not know where the strong direction is. It is that knowing the direction removes ε from the answer. Anything left over that depends on ε is therefore about the direction being lost, not about the anisotropy being large.

At the strongest anisotropy the damage is largest #

Four decades below one, the rotated stencil is as close to the limiting case as double precision makes available. The coefficients of the rotated operator are a = c = (ε + 1)/2 and b = (ε − 1)/2, so the four axis entries have magnitude (1 + ε)/2 and the four corner entries (1 − ε)/4, and the ratio between them is 2(1 + ε)/(1 − ε). At ε = 10⁻⁴ that is 2.0004. The largest coupling in every interior row belongs to an axis; the direction the equation is anisotropic along carries half as much; and two of the four corner entries are positive, which every classical strength measure discards outright.

The convergence factor at 45° is 0.8024 against 0.1945 aligned. That is the largest gap anywhere in this essay, and it is the setting at which the coupling ratio is at its smallest. Whatever the ratio is measuring, it is not the harm.

What the strength graph does with that stencil is worth stating as a count rather than as a description. On the aligned operator every interior point has exactly two strong neighbours — the two along the strong direction — which is why the aggregates come out one point wide and the coarsening is semi-coarsening, discovered from the matrix entries by a method with no coordinate in it, as the classical coarsening discovers it. On the rotated operator every interior point has exactly six: the four axis neighbours and the two negative corners. The coupling along the anisotropy is 0.4999 of the axis coupling, comfortably above the threshold of 0.25, so it is not that the test rejects the direction — the test accepts almost everything, and an aggregation given six strong neighbours in a nine-point neighbourhood builds blobs.

The same six neighbours at every setting #

Two decades of anisotropy have been given back and the picture has barely moved. The aligned factor goes from 0.1945 to 0.1927, which is a change of 0.002 and in the direction of improvement by an amount no reader should take seriously. The factor at 45° goes from 0.8024 to 0.7774. And the hierarchy underneath both of those numbers is bit-for-bit the one from the previous figure: six strong neighbours per interior point, 121 aggregates, 121 of them opened by the first pass and 200 points placed by the second, every point owned by the same aggregate as before.

That last fact is the one worth pausing on, because it is stronger than any ratio. The coupling ratio moves — 2.0004, 2.0040, 2.0404 across three decades — and a reader could reasonably ask whether a two per cent movement in it explains a change in the convergence factor. It cannot, because the quantity the ratio is a proxy for did not move at all. The strength graph is a yes-or-no about each edge, the aggregation is a function of that graph, and both are constant here. The method is not making a slightly different mistake at ε = 10⁻² than at ε = 10⁻⁴. It is making the identical mistake, and the mistake costs less.

This is where the step-function behaviour of the strength test, which is a liability everywhere else in the anchor, becomes the instrument. Because the coarsening cannot respond continuously to the operator, a continuous change in the convergence factor with the hierarchy held fixed can only be a change in the problem — in how much the coarse space fails to represent the error a smoother leaves behind. At ε = 10⁻², that error is less directional than at 10⁻⁴, so an isotropic coarse space misrepresents less of it.

The defect is largest exactly where the harm is least #

At ε = 0.05 the convergence factor at 45° is 0.6799, the lowest of the four, and the coupling ratio is 2.2105, the highest of the four. The two quantities move in opposite directions, and continuing past the range the figure will draw makes the opposition unambiguous. Run the same solver directly:

At ε = 0.25 the stencil’s axis couplings are more than three times its diagonal ones — the largest misallocation in the table, by a factor the earlier settings never approach — and the rotation costs essentially nothing: 0.5235 against 0.5008, a ratio of 1.05. Two settings further, at ε = 0.5, the rotated operator converges very slightly faster than the aligned one, and at ε = 1 the two are the same matrix and return the same 0.3529, which is why the figure refuses to draw at ε = 1 rather than producing a flat line and captioning it as a failure.

The last two columns of that table are also where the aligned control stops being flat: 0.5008 at ε = 0.25 is far worse than the 0.19 it holds below, because 0.25 is exactly the strength threshold, the x-coupling stops failing the test, and the aligned aggregation becomes isotropic too. That step is the aggregation’s own discontinuity appearing in a second place, and it is the reason the sweep the figure draws stops at ε = 0.1: past the threshold the comparison is no longer between a method that has the direction and one that has lost it.

The grid is the second control, and it separates them again #

Anisotropy is one variable and the grid is another, and the grid is the better test of the two, because the defining property of a multigrid method is that its convergence factor does not depend on the number of unknowns. A rate that does not notice the size is what separates a multigrid method from a stationary iteration whose factor climbs towards one as the problem grows; it is the property the whole subject exists to obtain.

At 15×15 the aligned factor is 0.3076 and at 31×31 it is 0.1935. That is a large move, and it is the pre-asymptotic end of the sweep rather than a finding about it. The hierarchy on 225 unknowns runs 225, 75, 30, 15, 5, so four coarsenings separate the fine grid from a direct solve on five points, where on 961 unknowns it runs 961, 341, 124, 62, 7. The aggregation at this size is 75 aggregates from 225 points, with 15 of them placed by the second pass rather than none. What the small grid establishes is that the aligned factor is still moving there; what the next figure establishes is where it stops.

At 45° on the same grid the factor is 0.6802. That is the best rotated number of the three grid sizes, and the reason it is worth flagging immediately is that it looks like evidence in the wrong direction — a smaller grid, less damage. The next figure is what decides whether that is a trend.

Across the three grids the aligned factor reads 0.3076, 0.1935, 0.1932. It settles, and it settles to three digits between the last two sizes, which is grid independence measured rather than asserted: a factor of 9.8 in the number of unknowns from the first grid to the last, and a factor of 1.0016 in the convergence factor between the last two.

Across the same three grids the rotated factor reads 0.6802, 0.7894, 0.7968. It moves the other way. The rotated hierarchy is not a slow multigrid method; refining the grid makes it worse, which is the behaviour of a method whose coarse space is not resolving the error at all rather than resolving it imperfectly. Two controls, two different variables, and the same separation: on the aligned operator the factor is insensitive to the anisotropy and settles in the grid, and on the rotated one it is sensitive to the first and unsettled in the second.

What the aggregation is doing while this happens #

The counts underneath those factors are worth reporting, because they are available before any solve and they say the same thing without a convergence history.

On the aligned operator at the two larger sizes the second pass places nothing at all. Every point of the grid is seeded into an aggregate by the first pass, which only opens an aggregate on a point whose entire strong neighbourhood is still free — so the strength graph decomposes cleanly into strongly-connected runs and the aggregation is the first pass in its entirety.

On the rotated operator the second pass places about a fifth of the grid at every size: 45 points of 225, 200 of 961, 511 of 2,209. Those are points with no clean strong neighbourhood of their own, handed to whichever neighbouring aggregate they are most strongly attached to — and the attachment is measured on the axis couplings, because those are the largest entries in the row. The coarsening ratio tells the same story from the other side: 2.82 aligned at 31×31 against 7.94 rotated, and 2.94 against 8.63 at 47×47. The rotated hierarchy coarsens roughly three times as fast, in every direction, on a problem whose error is smooth in one direction only.

What the failure costs, which is not what it looks like #

A hierarchy that coarsens three times as fast is cheap, and the cost accounting inverts the usual reading of these two cases.

Operator complexity is the total nonzeros over all levels divided by the fine matrix’s, and it is the number that decides whether an optimal-complexity method is actually cheap — the quantity a graph Laplacian pushed to 17.7, with one level of forty-one unknowns entirely dense. Here at ε = 10⁻³ on the 31×31 grid it is 3.009 aligned and 1.196 rotated. The successful hierarchy is two and a half times the more expensive of the two per cycle, because semi-coarsening by three in one direction and by nothing in the other keeps a great many unknowns on every level.

Per digit of residual, the ordering returns. A factor of 0.1935 clears a decade in 1.40 cycles and a factor of 0.7894 needs 9.74, so the work per decade is 4.22 units against 11.64 — the rotated run is 2.76 times the cost of the aligned one despite each of its cycles being cheaper. That ratio is the honest price of the rotation at this anisotropy, and it is smaller than the raw convergence factors suggest, which is the sort of correction a complexity measurement exists to supply.

Where this stops being true #

Three limits, none of which the measurements above can see from the inside.

The figure draws five angles. 0°, 11.25°, 22.5°, 33.75° and 45°, and the curve between them is a straight line because that is what a five-point series is. The essay’s claims are about the endpoints and about the ordering of the intermediate values, not about the shape.

The intermediate angles are not monotone in ε. At 22.5° the factor reads 0.6032, 0.5973, 0.5447 and 0.3280 over the four settings, which is the same ordering as at 45° and supports the argument. At 11.25° it reads 0.4837, 0.4590, 0.5383 and 0.3081, which is not monotone, and no claim here rests on it. Something finer than the direction argument governs the small-angle end, exactly as it does in the angle sweep the host essay records, and that something has not been measured.

And the drawn range stops at ε = 0.1 for a reason that is about meaning rather than about the solver. Above the strength threshold both operators get an isotropic hierarchy, so the comparison is between two methods that have both stopped tracking a direction, and the difference between them is no longer the quantity this essay is about. The two right-hand columns of the table above are there to show where the sequence is heading and are not part of the claim.

What follows for anything that reads this matrix #

A repair aimed at the hierarchy cannot work, and the measurement now says by how much it cannot. The hierarchy at 45° is one hierarchy across four decades of anisotropy; the damage it does varies by 0.22. Nothing that changes the hierarchy can produce a variation the hierarchy does not have. That is a stronger form of the argument the host essay makes, which established that a better hierarchy cannot help and did not establish that the failure is graded.

The size of the repair owed is set by the anisotropy, not by the angle. A code discretising a rotated anisotropic problem at ε = 0.05 is paying 2.75 times the aligned work and one at ε = 10⁻⁴ is paying 4.13 times, on the same stencil and the same solver. Effort spent on an aligned stencil or on a mesh that follows the flow buys back an amount that can be read off before the mesh is built, which is the kind of estimate a discretisation choice needs and rarely has.

A method tuned on an aligned problem carries no guarantee at any angle. That is the property grid alignment prices in the convection field, where a scheme exact at every node at one flow angle has a relative error of 6.9 five degrees away. The mechanism there is a tuned diffusion coefficient and here it is a strength test, and the shape is identical: competence put in by hand along an axis, lost the moment the problem is not on it.

And the diagnosis belongs to the discretisation, which is a choice made before any solver is selected. The couplings in the four figures above are 0.5001, 0.5005, 0.5050 and 0.5250 on the axes against 0.2500, 0.2497, 0.2475 and 0.2375 along the anisotropy, and every one of them was computable from ε and the angle without assembling a matrix. That is the same point the stencil that is not symmetric makes about central differencing past a cell Péclet number of one: the discretisation decides in advance what any solver can see, and it does so with an arithmetic that no solver is involved in.

What is not settled is whether a different strength measure recovers the direction. Affinity and algebraic-distance measures do see positive off-diagonals, which the classical test discards, and the rotated stencil has two of them per interior row. Whether such a measure finds the 45° direction on this stencil is a measurement nobody here has run, and the constancy established above sharpens what it would have to show: not a better convergence factor at one ε, but a strength graph that stops being the same graph at every ε.

And the coarse operator is not where to look. The triple product that builds it reproduces the coarse discretisation exactly, entry for entry, so what a coarse level inherits is what the fine level had. A fine level with no direction in it produces a coarse level with no direction in it, at every level of the hierarchy, which is why the constancy across ε reaches all the way down.