Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Perron frobenius — the series

4 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 1 · graph
  2. places settled, of 14the arithmetic14 of 14one missing link3 of 14α from 0.80 to 0.9011 of 14entries move by 4.05·10⁻¹¹entries move by 0.00443entries move by 0.00123three kinds of doubtcomparisons14smallest gap6.3·10⁻⁵largest gap0.0024arithmetic band4.1·10⁻¹¹one-link band0.0044α band0.0012the arithmetic settles nearly all of themthe data settles three

    A ranking whose order is not determined

    Of the fourteen adjacent comparisons in a top-fifteen, fourteen survive perturbing the arithmetic at the rounding level, eleven survive moving the teleportation parameter across its usual range, and three survive removing one link. The computation is the strongest part of the answer.

    part 2 · graph
  3. 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.

    part 3 · graph
  4. 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

    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.

    part 4 · graph

All series