Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Perron frobenius — where it appears

The theorem that a nonnegative matrix with a strongly connected graph has its spectral radius as a simple eigenvalue with a strictly positive eigenvector. The positivity is a statement about real numbers and does not survive a norm-wise approximation.

Named by 5 essays across one field — each of them below, with the objects they name alongside it.

01428425670849810⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²iterationchange between iteratestwo rates, one curveα0.85λ₂(P)0.9predicted rate0.77measured0.77iterations108against the solve10⁻¹⁶the upper dashed line is αᵏthe curve is on the other one

A ranking that is an eigenvector

PageRank is the stationary vector of a walk that follows links with probability α and jumps at random otherwise. The iteration and the elimination agree to 4·10⁻¹⁷. What α is set to changes which pages come third, fourth and fifth.

graph · Random walk 02244668811013215417610⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²iterationchange between iteratestwo rates, one curveα0.85λ₂(P)1predicted rate0.85measured0.84iterations176against the solve1.4·10⁻¹⁶the upper dashed line is αᵏthe curve is on the other one

A chain with no stationary vector

A page with no outgoing links loses forty per cent of the walker's probability in six hundred steps. A directed cycle never converges at all. And on a graph whose links only run one way, the entire rank of half the vertices is exactly one minus the teleportation parameter.

graph · Random walk 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.

graph · Perron frobenius 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.

graph · Perron frobenius 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.

graph · Perron frobenius

Named alongside it

The objects these essays reach for when they reach for this one.

Power iterationStationary distributionCollatz wielandtDangling nodeMixing timePagerankRegularisationRelative accuracyTeleportationBlock methodsCatastrophic cancellationCentrality

All concepts