Numerical Linear Algebra
where the algebra stops being the arithmetic
The matrix that is a graph

The stall was in the block

On two dense clusters joined by a coupling ε, the power iteration needs about 7/ε steps and then stalls at about u/(4ε). Aggregation–disaggregation was predicted to need a number of steps independent of ε and to stall at rounding, and with a power step as its smoother it does: fourteen steps at every coupling from a tenth to 10⁻¹², every entry to a relative 10⁻¹⁵. The textbook smoother, block Gauss–Seidel, is faster and stalls at u/ε again — because each block solve forms one minus a self-probability, and a block whose rows sum to 1 − ε is singular to within ε. Solved without that subtraction, the same blocks finish in one to four steps at rounding, and get faster as the coupling weakens.
21 min read 5 figures Measured, not assumedIdentical algebra, different arithmeticWhose fault is itExact ground truth

Worth reading first: A ranking that is an eigenvector · An eigenvector that must not change sign.

No subtraction and no waiting put three routes to a Markov chain’s stationary vector side by side on a chain built to be hard: two dense clusters of twelve states, with each state of the first cluster sending a fraction 3ε3\varepsilon of its probability to the second and each state of the second sending ε\varepsilon back. The stationary vector gives the clusters a quarter and three quarters of the mass, and the second eigenvalue of the transition matrix is within about ε\varepsilon of one. The power iteration, which forms only sums of positive numbers and keeps every small entry honest, needs about 7/ε7/\varepsilon steps on it — 6,900 at ε=10−3\varepsilon = 10^{-3}, 69,000 at 10−410^{-4} — and then stalls at a relative error of about u/(4ε)u/(4\varepsilon). Gaussian elimination is fast and loses the small entries. The Grassmann–Taksar–Heyman elimination, which rearranges Gaussian elimination so that it never subtracts, is fast and holds every entry to 10−1510^{-15} at every coupling down to 10−1210^{-12}.

The essay ended on the standard cure for the power iteration’s steps. “Iterative aggregation–disaggregation solves a small chain between clusters and the clusters separately, and is the standard cure for the power iteration’s 1/ε1/\varepsilon steps. The prediction is that on the two-cluster chain it reaches 10−1210^{-12} in a number of steps independent of ε\varepsilon — under thirty from 10−210^{-2} to 10−1210^{-12} — and that its stall point is independent of ε\varepsilon as well, because the aggregated chain is solved directly.”

The prediction holds for one version of the method and fails for the version usually written down, and the reason it fails is the reason the earlier essay was about.

Aggregation, disaggregation, smoothing

Each step of the method has three parts. Aggregation collapses the chain to one state per cluster: from the current estimate of the stationary vector, each cluster’s states are weighted by their share of that cluster’s mass, and the probability of moving from cluster to cluster is the weighted average of the states’ probabilities of leaving. Here that is a two-by-two chain whose off-diagonal entries are about 3ε3\varepsilon and ε\varepsilon. Disaggregation solves that small chain exactly — the earlier essay’s subtraction-free elimination does it to rounding — and rescales each cluster’s entries so that the cluster holds the mass the small chain gives it, keeping the shape within the cluster. Smoothing then improves the shape within each cluster, using the full chain.

The aggregated chain carries everything the coupling does: how mass divides between the clusters, which is exactly the slow mode the power iteration takes 1/ε1/\varepsilon steps to resolve. The smoothing has to carry only what happens within a cluster, where the chain mixes fast. That division of labour is the method’s whole idea, and it is the same one the coarse problem is a different problem describes for multigrid: a small problem that sees the slow components, and a cheap iteration for the rest. Three smoothings are measured. One step of the power iteration. Block Gauss–Seidel, which solves each cluster’s own equations for its entries given the latest values of the other’s — the Koury–McAllister–Stewart method as it is usually written — with each block solved by Gaussian elimination with partial pivoting. And the same block Gauss–Seidel with each block solved the way the earlier essay solved the whole chain: without a subtraction.

Every measurement is against the exact stationary vector of the stored chain, computed in rational arithmetic, as before.

The prediction holds, with a power step

Steps to every stationary entry within a relative 10⁻¹² on the two-cluster chain, against the coupling: the power iteration, and aggregation–disaggregation with three smoothingsε 0.1: power 60, power smoothing 12, block Gauss–Seidel 4, block Gauss–Seidel, no subtraction 4; ε 0.01: power 680, power smoothing 14, block Gauss–Seidel 3, block Gauss–Seidel, no subtraction 3; ε 0.001: power 6900, power smoothing 14, block Gauss–Seidel 3, block Gauss–Seidel, no subtraction 3; ε 10⁻⁴: power 69370, power smoothing 14, block Gauss–Seidel never, block Gauss–Seidel, no subtraction 2; ε 10⁻⁶: power never, power smoothing 14, block Gauss–Seidel never, block Gauss–Seidel, no subtraction 2; ε 10⁻⁸: power never, power smoothing 14, block Gauss–Seidel never, block Gauss–Seidel, no subtraction 2; ε 10⁻¹⁰: power never, power smoothing 14, block Gauss–Seidel never, block Gauss–Seidel, no subtraction 2; ε 10⁻¹²: power never, power smoothing 14, block Gauss–Seidel never, block Gauss–Seidel, no subtraction 1. The power iteration is capped at 200000 steps.10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²110¹10²10³10⁴10⁵coupling ε between the clusterssteps to every entry within 10⁻¹²neverpower iterationblock Gauss–Seidelpower smoothingblock Gauss–Seidel, no subtraction'never': stalled above 10⁻¹²aggregation does not wait for the coupling
Fig. 1 Steps until every stationary entry is within a relative 10⁻¹² of the exact one, against the coupling: the power iteration, and aggregation–disaggregation with each of three smoothings. A method that never gets there is drawn on the line marked ‘never’.

With one power step as its smoother, aggregation–disaggregation reaches every entry to 10−1210^{-12} in twelve steps at a coupling of a tenth and fourteen at every coupling from 10−210^{-2} to 10−1210^{-12}. The power iteration on the same chains needs 60, 680, 6,900 and 69,000 steps from a tenth to 10−410^{-4}, and below that does not get there within 200,000. The step count is independent of the coupling to within two, as predicted, and well under the predicted thirty.

The error falls by about a factor of seven a step — 4⋅10−24 \cdot 10^{-2}, 6⋅10−36 \cdot 10^{-3}, 8⋅10−48 \cdot 10^{-4}, 10−410^{-4}, 10−510^{-5} over the first five, at every coupling from 10−210^{-2} down. That rate is the clusters’ own: a power step within a dense cluster of twelve states with random positive rows damps everything but the cluster’s stationary shape by its second eigenvalue, about a sixth. The coupling has gone from the rate entirely, because the aggregation step puts the mass between the clusters right every time, and the power step never has to move it. The rate is the second eigenvalue measured the power iteration’s rate as the second eigenvalue of the whole chain; here it is the second eigenvalue of a cluster, which is a different and much smaller number.

And the stall point is rounding

Where each method stalls on the two-cluster chain, against the coupling: the power iteration, aggregation–disaggregation with three smoothings, and the direct elimination without subtraction, beside u divided by the couplingε 0.1: power 6.3·10⁻¹⁶, power smoothing 3.1·10⁻¹⁶, block Gauss–Seidel 1.9·10⁻¹⁵, block Gauss–Seidel, no subtraction 3.1·10⁻¹⁶; ε 0.01: power 1.9·10⁻¹⁵, power smoothing 4.1·10⁻¹⁶, block Gauss–Seidel 1.2·10⁻¹⁴, block Gauss–Seidel, no subtraction 5.9·10⁻¹⁶; ε 0.001: power 3.3·10⁻¹⁵, power smoothing 4.2·10⁻¹⁶, block Gauss–Seidel 1.5·10⁻¹³, block Gauss–Seidel, no subtraction 3.6·10⁻¹⁶; ε 10⁻⁴: power 2.3·10⁻¹³, power smoothing 3.9·10⁻¹⁶, block Gauss–Seidel 1.8·10⁻¹², block Gauss–Seidel, no subtraction 3.3·10⁻¹⁶; ε 10⁻⁶: power 0.45, power smoothing 4.6·10⁻¹⁶, block Gauss–Seidel 1.1·10⁻¹⁰, block Gauss–Seidel, no subtraction 4.9·10⁻¹⁶; ε 10⁻⁸: power 0.99, power smoothing 3.9·10⁻¹⁶, block Gauss–Seidel 7.1·10⁻⁹, block Gauss–Seidel, no subtraction 6.6·10⁻¹⁶; ε 10⁻¹⁰: power 1, power smoothing 4.6·10⁻¹⁶, block Gauss–Seidel 1.3·10⁻⁶, block Gauss–Seidel, no subtraction 3.1·10⁻¹⁶; ε 10⁻¹²: power 1, power smoothing 3.3·10⁻¹⁶, block Gauss–Seidel 1.7·10⁻⁴, block Gauss–Seidel, no subtraction 4.8·10⁻¹⁶.10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²coupling ε between the clustersworst relative entry error, where it stallsu / εpower iteration, at its capblock Gauss–Seidelblock Gauss–Seidel, no subtractiondirect, no subtractionpower smoothingdashed: the unit roundoff over the couplingthe stall belongs to the subtraction
Fig. 2 Where each method stalls, against the coupling: the power iteration (at its step cap where it has not converged), aggregation–disaggregation with three smoothings, and the direct elimination without subtraction, beside the unit roundoff over the coupling. Two methods follow that line; three sit at rounding.

The second clause holds too. Power-smoothed aggregation stalls at a worst relative entry error between 3⋅10−163 \cdot 10^{-16} and 5⋅10−165 \cdot 10^{-16} at every coupling — the same level as the direct elimination without subtraction, which is as accurate as anything can be on these chains. The prediction’s reason was that the aggregated chain is solved directly; the fuller reason is that every operation in the step is a sum of nonnegative numbers. The aggregated chain’s entries are weighted averages of sums of probabilities; its solution is the subtraction-free elimination’s; the rescaling multiplies; and a power step adds products of positive numbers. Nothing in the step can cancel, so nothing in it can lose relative accuracy in a small entry. The power iteration had the same property and stalled anyway, at u/(4ε)u/(4\varepsilon) — but that stall is a rate effect, as the earlier essay showed: the slow mode’s contraction per step is within rounding of one, so the iteration stops moving before it arrives. Aggregation has no slow mode left to wait for.

The textbook smoother stalls where the power iteration did

Block Gauss–Seidel is the smoother the method’s literature uses, and it is faster. It solves each cluster’s equations for that cluster’s entries exactly, so the within-cluster shape is right after a single step rather than converging to it at a sixth a step. At a coupling of a tenth it reaches 10−1210^{-12} in four steps, at 10−210^{-2} and 10−310^{-3} in three.

Then it stops. Its floor is 1.9⋅10−151.9 \cdot 10^{-15} at a tenth, 1.2⋅10−141.2 \cdot 10^{-14} at 10−210^{-2}, 1.5⋅10−131.5 \cdot 10^{-13} at 10−310^{-3}, 1.8⋅10−121.8 \cdot 10^{-12} at 10−410^{-4} — and from there it never reaches 10−1210^{-12}: 1.1⋅10−101.1 \cdot 10^{-10} at 10−610^{-6}, 7.1⋅10−97.1 \cdot 10^{-9} at 10−810^{-8}, 1.3⋅10−61.3 \cdot 10^{-6} at 10−1010^{-10} and 1.7⋅10−41.7 \cdot 10^{-4} at 10−1210^{-12}. Every one of those is within a factor of two of u/εu/\varepsilon. The power iteration’s stall was u/(4ε)u/(4\varepsilon). The method that was supposed to cure the power iteration’s dependence on the coupling has cured its step count and inherited its floor — by a different route.

The subtraction is in one block solve

One cluster's equations solved alone with the exact right-hand side, whose solution is that cluster's stationary entries: the worst relative error by elimination with the diagonal formed as one minus the self-probability, and without any subtraction, against the couplingε 0.1: elimination 2.4·10⁻¹⁵, no subtraction 4.2·10⁻¹⁶; ε 0.01: elimination 1.6·10⁻¹⁴, no subtraction 2.1·10⁻¹⁶; ε 0.001: elimination 2·10⁻¹³, no subtraction 3.6·10⁻¹⁶; ε 10⁻⁴: elimination 2.4·10⁻¹², no subtraction 4.6·10⁻¹⁶; ε 10⁻⁶: elimination 1.4·10⁻¹⁰, no subtraction 2.4·10⁻¹⁶; ε 10⁻⁸: elimination 9.5·10⁻⁹, no subtraction 3.8·10⁻¹⁶; ε 10⁻¹⁰: elimination 1.7·10⁻⁶, no subtraction 3.1·10⁻¹⁶; ε 10⁻¹²: elimination 2.2·10⁻⁴, no subtraction 4.8·10⁻¹⁶. The block's rows sum to one minus the coupling, so the block is singular to within the coupling.10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²coupling εworst relative error in the block's entrieselimination, 1 − pᵢᵢu / εno subtractiondashed: u / εthe stall is in one block solve
Fig. 3 One cluster’s equations solved alone, with the exact right-hand side, whose solution is that cluster’s stationary entries: the worst relative error by elimination with the diagonal formed as one minus the self-probability, and without any subtraction, against the coupling.

To find where the floor comes from, take one block solve out of the iteration. The second cluster’s equations are x(I−PJJ)=rx(I - P_{JJ}) = r, where PJJP_{JJ} is the cluster’s own block of the transition matrix and rr collects the probability flowing in from the other cluster. Put the exact stationary vector into rr and the exact solution is that cluster’s stationary entries, so the solve can be judged by itself.

By Gaussian elimination with partial pivoting the cluster’s entries come back with a worst relative error of 2.4⋅10−152.4 \cdot 10^{-15} at a coupling of a tenth, 2.4⋅10−122.4 \cdot 10^{-12} at 10−410^{-4}, 9.5⋅10−99.5 \cdot 10^{-9} at 10−810^{-8} and 2.2⋅10−42.2 \cdot 10^{-4} at 10−1210^{-12} — the iteration’s floor, from one solve. The block’s rows sum to 1−ε1 - \varepsilon, so I−PJJI - P_{JJ} has row sums ε\varepsilon: it is singular to within the coupling. Its diagonal is formed as 1−pii1 - p_{ii}, a subtraction of two numbers near one that leaves the difference with an absolute error of uu — and in a matrix singular to within ε\varepsilon, an absolute error of uu in an entry is a relative error of u/εu/\varepsilon in the solution. It is the cancellation cancellation takes the answer, not a digit described, placed where the conditioning amplifies it.

The block is not ill-conditioned for any reason the chain cares about. Its row sums are the probabilities of leaving the cluster, and those are known exactly: they are entries of the data. Form each diagonal entry as the sum of its row’s other probabilities, in-cluster and out, and eliminate in the Grassmann–Taksar–Heyman manner, so that each update adds magnitudes, each new row sum adds the old ones, and each pivot is a sum. Then nothing is subtracted anywhere, and the same solve returns the cluster’s entries to 2⋅10−162 \cdot 10^{-16}–5⋅10−165 \cdot 10^{-16} at every coupling. The singularity to within ε\varepsilon is still there; it simply never meets a rounding error it could amplify, because every rounding is relative to a positive quantity of the size of the result.

An eigenvector that must not change sign put the moral in its strongest form: a property guaranteed by a theorem — there, positivity — is preserved numerically only by an algorithm whose arithmetic cannot violate it. Here the property is relative accuracy in entries of very different sizes, and the algorithm that preserves it is the one that never subtracts, applied at whatever scale the solve happens at — the whole chain, as before, or one cluster inside an iteration.

The same blocks, faster as the coupling weakens

The worst relative entry error after each step of aggregation–disaggregation on the two-cluster chain at coupling 10⁻⁸, with three smoothingspower smoothing: 0.04, 0.006, 8·10⁻⁴, 10⁻⁴, 10⁻⁵, 2·10⁻⁶ … stalling at 3.9·10⁻¹⁶; block Gauss–Seidel: 9·10⁻⁹, 7·10⁻⁹, 7·10⁻⁹, 7·10⁻⁹, 7·10⁻⁹, 7·10⁻⁹ … stalling at 7.1·10⁻⁹; block Gauss–Seidel, no subtraction: 2·10⁻⁹, 7·10⁻¹⁶, 7·10⁻¹⁶, 7·10⁻¹⁶, 7·10⁻¹⁶, 7·10⁻¹⁶ … stalling at 6.6·10⁻¹⁶.05101520253010⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1aggregation–disaggregation stepworst relative entry errorblock Gauss–Seidelblock Gauss–Seidel, no subtractionpower smoothinga weaker coupling makes the blocks fasterthe same blocks, two arithmetics
Fig. 4 The worst relative entry error after each step of aggregation–disaggregation at the coupling on the dial, for the three smoothings. The power-smoothed line does not move with the coupling; the block smoothings get faster as it weakens; the one that subtracts also stalls higher.

With the subtraction removed, block Gauss–Seidel does something the prediction did not ask for. It reaches 10−1210^{-12} in four steps at a coupling of a tenth, three at 10−210^{-2} and 10−310^{-3}, two from 10−410^{-4} to 10−1010^{-10}, and one at 10−1210^{-12}. A weaker coupling makes it faster.

Turn the dial and the reason is visible in the first step. Aggregation puts the mass between the clusters right; block Gauss–Seidel then makes each cluster’s shape exactly right given the other cluster’s current values; and the only error left is how much the other cluster’s error leaks in through the coupling. The leak is proportional to the coupling. A nearly decomposable chain — the case that defeats the power iteration — is the easiest case there is for this method, because the clusters barely talk to each other, and a method that solves each cluster exactly needs them to talk only to fix the error the aggregation leaves, which is already small.

The worst relative entry error after one step of aggregation–disaggregation from the uniform vector, against the coupling, for three smoothings, beside the coupling itselfε 0.1: power smoothing 0.032, block Gauss–Seidel 0.013, block Gauss–Seidel, no subtraction 0.013; ε 0.01: power smoothing 0.04, block Gauss–Seidel 0.0016, block Gauss–Seidel, no subtraction 0.0016; ε 0.001: power smoothing 0.042, block Gauss–Seidel 1.7·10⁻⁴, block Gauss–Seidel, no subtraction 1.7·10⁻⁴; ε 10⁻⁴: power smoothing 0.043, block Gauss–Seidel 1.7·10⁻⁵, block Gauss–Seidel, no subtraction 1.7·10⁻⁵; ε 10⁻⁶: power smoothing 0.043, block Gauss–Seidel 1.7·10⁻⁷, block Gauss–Seidel, no subtraction 1.7·10⁻⁷; ε 10⁻⁸: power smoothing 0.043, block Gauss–Seidel 8.8·10⁻⁹, block Gauss–Seidel, no subtraction 1.7·10⁻⁹; ε 10⁻¹⁰: power smoothing 0.043, block Gauss–Seidel 1.3·10⁻⁶, block Gauss–Seidel, no subtraction 1.7·10⁻¹¹; ε 10⁻¹²: power smoothing 0.043, block Gauss–Seidel 1.7·10⁻⁴, block Gauss–Seidel, no subtraction 1.7·10⁻¹³.10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1coupling εworst relative error after one steppower smoothingblock Gauss–Seidelε itselfblock Gauss–Seidel, no subtractiondashed: the coupling εa nearly decomposable chain is the easy case
Fig. 5 The worst relative entry error after a single step from the uniform vector, against the coupling. Both block smoothings fall with the coupling, about a fifth of it; the power smoothing stays near 4·10⁻². The dashed line is the coupling itself.

After one step from the uniform vector, both block smoothings leave an error of about a fifth of the coupling — 2⋅10−32 \cdot 10^{-3} at 10−210^{-2}, 2⋅10−72 \cdot 10^{-7} at 10−610^{-6}, 2⋅10−132 \cdot 10^{-13} at 10−1210^{-12} — while the power smoothing leaves 33 to 4⋅10−24 \cdot 10^{-2} at every coupling. The block smoothing that subtracts tracks the other until it meets u/εu/\varepsilon from below, and then the two lines part: the one falls with ε\varepsilon, the other rises.

What each route costs to rounding

Steps are not work, and the three smoothers do different amounts of it. Counted from the loops themselves on two clusters of twelve states: aggregation costs about 600 operations a step, summing every probability into its block; a power step adds about 1,200; a block Gauss–Seidel step adds about 3,500, most of it two dense twelve-by-twelve eliminations. So the power smoother’s fourteen steps cost about 25,000 operations at every coupling, and the subtraction-free block smoother’s four, three, two and one steps cost 16,000, 12,000, 8,000 and 4,000 — less than the power smoother from a coupling of a tenth on, and a sixth of it at 10−1210^{-12}. The power iteration at 10−410^{-4}, for comparison, does 69,000 steps of about 1,200 operations each: eighty million, three thousand times the power-smoothed aggregation’s work, for an answer that is less accurate.

The textbook smoother costs exactly what its subtraction-free twin costs per step — the same eliminations with the diagonal formed differently — and is just as fast while it works. It stops working at the coupling where u/εu/\varepsilon reaches the tolerance asked for: 10−410^{-4} for a tolerance of 10−1210^{-12}. Below that, no number of its steps reaches the answer, at any price.

A rate that does not notice the size is the multigrid version of the first half of this result: a two-level method whose coarse problem carries the slow components converges at a rate that does not depend on the parameter that makes the problem hard. The same problem on a coarser grid builds that coarse problem out of the fine one, as aggregation builds the two-state chain out of the twenty-four-state one. The second half — that the coarse correction and the smoother can be exact in algebra and still lose the answer in arithmetic — has no counterpart there, because a discretised elliptic operator does not have entries of twelve different magnitudes. A Markov chain’s stationary vector can.

What the cure was curing

The earlier essay had three routes and found that each was paying for something. Gaussian elimination paid in small entries, the power iteration in steps and then in a floor, and the subtraction-free elimination paid nothing, at a cost of one dense factorisation. Aggregation–disaggregation adds a fourth route that can be made to pay nothing too — fourteen cheap steps with a power smoother, or one to four with an exact block smoother — but only if each of its parts keeps the earlier essay’s discipline. The aggregated chain is safe because it is solved without subtraction. The block solves are safe only if they are solved the same way.

That changes what “the standard cure” means. The method’s usual description puts the difficulty of nearly decomposable chains in the number of steps, and its convergence theory is about steps. Its accuracy problem is not in the theory at all, because it is not a property of the method; it is a property of how a linear solve inside it forms one minus a probability. The same mistake, in the same place, would affect any method that solves cluster equations — and every method for nearly decomposable chains does.

A ranking that is an eigenvector and a chain with no stationary vector studied chains whose difficulty was in their structure. This one’s difficulty was in one subtraction, and the measurement that found it was the one the field’s opening essays insisted on: an exact answer to compare against, rather than a residual that would have looked fine.

What two clusters do not show

Every chain here has two clusters of twelve states, one partition known in advance, and dense rows within clusters. With many clusters the aggregated chain is larger and its own solve must also avoid subtraction, which the subtraction-free elimination already does. With a partition that is wrong — states assigned to the cluster they do not belong to — the aggregation no longer captures the slow mode, and the power-smoothed version’s step count would be expected to depend on the coupling again; that is not measured. The block Gauss–Seidel used here sweeps the two clusters once per step in a fixed order. And the claim that the power smoothing’s rate is a cluster’s second eigenvalue is read off the measured ratios, about a seventh a step, and not checked against that eigenvalue directly.

Still open: the wrong partition, and a chain with many clusters

A partition that is wrong. Aggregation needs the partition to hold the slow mode. Move one state of the first cluster into the second and the aggregated chain no longer represents the mass that state carries across the coupling. The prediction with a sign is that with a single misassigned state, power-smoothed aggregation needs more than 1/(10ε)1/(10\varepsilon) steps at couplings of 10−410^{-4} and below — losing the independence entirely — while the subtraction-free block smoother, which solves the misassigned state’s equations exactly within its block, still finishes in under ten steps at every coupling.

Many clusters, many couplings. A chain of eight clusters joined by couplings spread over six decades has an aggregated chain that is itself nearly decomposable. The prediction is that subtraction-free aggregation still reaches rounding in under ten steps, that the aggregated eight-state chain solved by ordinary elimination introduces a floor of about uu over the smallest coupling, and that solving it without subtraction removes that floor — the earlier essay’s lesson needed at every level of the hierarchy, not only at the bottom.

Where this goes next

10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²10⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1coupling ε between the clustersworst relative entry errorGTHGaussian eliminationpower iterationthe stationary vector is computed against an exact rational solutiononly the elimination with no subtraction holds No subtraction, and no waiting The power iteration keeps a positive vector's small entries correct because it never subtracts, and it pays for that in steps. On a Markov chain made of two clusters joined by a coupling ε it needs about 7/ε of them — 6,900 at ε = 10⁻³, 69,000 at 10⁻⁴ — and then stalls at a fixed point of its own rounded arithmetic about u/(4ε) from the answer; at ε = 10⁻⁶ it is still 45 per cent wrong after 200,000. Gaussian elimination needs no waiting and subtracts: on the same chains its error grows like 1/ε, and on a chain whose entries fall to 10⁻¹⁸⁴ it returns the small ones as noise, eight of them negative. The Grassmann–Taksar–Heyman elimination does neither. Every entry of every chain comes back to a relative 10⁻¹⁵, in a third of n³ operations, because the stationary vector is well conditioned under the perturbations it makes. 0173451688510211910⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹1steps of the walkdistance from stationarya rate read as a timeλ₂ of the walk0.9steps measured122steps predicted131ratio0.93the dashed line is the eigenvaluethe curve is the walk The rate is the second eigenvalue A walk forgets where it started at a rate the graph's second eigenvalue names exactly. Across three orders of magnitude in the step count the prediction is five per cent high — and the published rate for PageRank is right for a reason nobody states, which is that a link graph is in pieces. 1611162126313610⁻²²10⁻¹⁹10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹vertex, clique first then tail|entry| relative to the largestone rounding of the largest entrya bound that is provedPerron root11bracket, low11bracket, high11bracket width1.2·10⁻⁴smallest entry-1.5·10⁻²⁰entries below zero4every entry is positiveand the picture disagrees An eigenvector that must not change sign Perron's theorem says the leading eigenvector of a connected nonnegative matrix is strictly positive. On a clique with a long tail, four of its thirty-six entries come back negative — and beside them is the only two-sided bound in these essays that is proved rather than estimated.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

Block methodsCatastrophic cancellationExact ground truthM-matrixPerron frobeniusPower iterationRelative accuracyStationary distribution