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

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.
33 min read 29 figures Where the algebra stops being the arithmeticMeasured, not assertedWhose fault is itTwo routes to a number

Worth reading first: A ranking that is an eigenvector · The spectrum is not the graph · The vector that has to be rounded.

Put a walker on one vertex of a connected graph and let it step to a random neighbour repeatedly. Its distribution starts concentrated and ends at the stationary one, which for an undirected graph is the degree distribution. How long that takes is the mixing time, and there is a quantity that is supposed to name it.

122 steps to forget where it started, and λ₂ said 131A random walk on a sixty-vertex graph with two blocks joined at a density of 0.03, started at one vertex, measured as the total variation distance from its stationary distribution. It reaches 10⁻⁶ after 122 steps. The dashed line is |λ₂|ᵏ with λ₂ = 0.900071 from the walk matrix, and the number of steps that predicts is 131. The distance is not the eigenvalue: for the first several steps the walk is leaving one block and the decay is faster than the asymptote, and the two curves become parallel only once the slowest mode is all that is left. The eigenvalue is a rate, not a schedule, and the difference between them is 9.22 steps.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
Fig. 1 A walk on a sixty-vertex graph with two loosely joined blocks, measured as the total variation distance from its stationary distribution, against the decay the second eigenvalue predicts.

The walk matrix P = D⁻¹A is not symmetric, so at first sight none of this field’s machinery applies. It is similar to one that is: D^{1/2}PD^{-1/2} = D^{-1/2}AD^{-1/2} = I − 𝓛, so the walk’s eigenvalues are one minus the normalised Laplacian’s, are real, and lie in [−1, 1]. The mixing rate is |λ₂(P)|, the largest of them in absolute value below one.

The prediction, and what it is not

The asymptotic statement is that the distance to stationarity falls like |λ₂|ᵏ. Reading that as a number of steps gives

k  ≈  log(1/ε) ÷ log(1/|λ₂|)

which is what a practitioner would use to size a run. It is not a bound — a bound would carry a constant from the starting distribution, and that constant can be large — and it is not a fit. It is an asymptotic rate treated as a schedule, which is a thing people do constantly and which deserves to be checked.

What it is worth

Sixty vertices in two blocks, with the density between the blocks swept over forty times, the walk started at one vertex and run until the total variation distance falls below 10⁻⁶:

between-block density   |λ₂|        steps measured   predicted   ratio
0.005                   0.986994        1002            1055      0.950
0.010                   0.958917         314             329      0.953
0.020                   0.925170         169             178      0.951
0.030                   0.900071         122             131      0.930
0.080                   0.698104          36              38      0.936
0.200                   0.450568          16              17      0.923

The step count moves by a factor of sixty across the sweep and the ratio moves from 0.950 to 0.923. The prediction is between five and eight per cent high, everywhere.

That is a better result than the shape of the argument deserves. The asymptotic rate is a statement about what happens eventually, the constant in front of it is not one, and here the eventual behaviour is reached early enough that the constant is worth about seven per cent.

The sign of the discrepancy is worth a sentence: the walk mixes faster than the asymptote predicts, consistently. The starting distribution is a single vertex, which has a large component along every mode, and the fast modes die in a handful of steps — so the first few steps of the run buy more than their share, and the run reaches the tolerance slightly early. The curve in the figure shows exactly that: it falls steeply for the first dozen steps and then becomes parallel to the dashed line.

Three of the four graphs never mix at all

The measurement above was taken on a two-block graph, and the choice was not incidental. Run the same experiment on the other families in this field and most of them do not converge:

graph          λ₂(P)      smallest eigenvalue    bipartite    steps to 10⁻⁶
grid 6×7       0.937025        −1.000000            yes        never
cycle 24       0.965926        −1.000000            yes        never
path 30        0.994138        −1.000000            yes        never
two blocks     0.900071        −0.471447            no          122

After twenty thousand steps the total variation distance on all three bipartite graphs is exactly 0.5, and it stays there forever. The reason is the eigenvalue at −1: a bipartite graph’s walk moves from one side to the other at every step and back at the next, so a walker started on one side is on that side at even times and the other at odd times, permanently.

The rate |λ₂| said nothing about this, because it is the second largest in absolute value and here that is the eigenvalue at −1, which does not decay. Quoting λ₂ as the rate — the second largest eigenvalue rather than the second largest in modulus — is the error, and on a bipartite graph it predicts convergence at 0.937 a step for a walk that never converges at all.

Bipartite graphs are not exotic. A grid is bipartite. A tree is bipartite. Any graph with no odd cycle is bipartite, and a great many graphs from discretisations are.

The repair, and what it costs

The standard fix is the lazy walk: at each step stay put with probability a half and move with probability a half. Its matrix is (I + P)/2, whose eigenvalues are (1 + μ)/2 — so the eigenvalue at −1 becomes 0, every eigenvalue lands in [0, 1], and periodicity is impossible.

The cost is a factor of two and a bit. The lazy walk’s rate is (1 + λ₂)/2, which for the grid is 0.9685 against 0.9370, so the number of steps roughly doubles. That is the trade: a walk that converges half as fast, in exchange for converging.

It is also exactly what PageRank’s teleportation does, seen from a different angle. Mixing αP with a rank-one term does the same job as mixing P with the identity — both destroy periodicity by giving the walker something to do other than follow an edge — and both cost a factor in the rate. The difference is that teleportation also changes the answer, since (1 − α) of the stationary vector is the teleport distribution, while laziness does not: (I + P)/2 has exactly the same stationary vector as P. Laziness buys convergence for free and teleportation buys it for a change of answer, which is the choice the essay on α is about.

It is the same eigenvalue the partition essays are about

The measurement above and the conductance measurements three essays earlier are the same number seen twice, and it is worth putting them in one table:

between-block density   λ₂(𝓛)      conductance φ    mixing steps
0.005                   0.013006      0.008357          1002
0.020                   0.074830      0.045576           169
0.080                   0.301896      0.183486            36

A graph that is hard to cut is a graph a walk crosses slowly, and the two statements are the same eigenvalue read in two directions. Cheeger’s inequality connects φ to λ₂(𝓛); the mixing time connects λ₂(P) = 1 − λ₂(𝓛) to a number of steps. So a bottleneck is simultaneously a good partition and a slow walk, and neither fact is a metaphor for the other.

That is a genuinely useful equivalence rather than a curiosity. It means the certificate the Cheeger lower bound provides — that no cut is better than λ₂/2 — is also a certificate that the walk cannot mix faster than a rate, and the reverse. One eigenvalue computation answers both questions.

The other direction: what a walk is used for

The reason to care about the rate is that almost nothing waits for the exact stationary vector.

A power iteration for PageRank is a walk with teleportation and is stopped when successive iterates stop moving. A Markov chain Monte Carlo sampler is a walk whose burn-in is exactly a mixing time. A graph-based recommendation is often a few steps of a walk rather than its limit. In every case the question is not what the stationary vector is but how many steps buy how much of it, and that is the quantity the table above measures.

The bad case is worth naming. A walk on a graph with a bottleneck of conductance 10⁻³ takes of order 10³ steps to cross it, and no amount of arithmetic accuracy changes that: the slowness is a property of the graph. What changes it is preconditioning the graph — adding edges, or restarting the walk — which changes the answer as well as the rate, and is the same trade the iterative field makes with a preconditioner.

1002 steps to forget where it started, and λ₂ said 1055A random walk on a sixty-vertex graph with two blocks joined at a density of 0.005, started at one vertex, measured as the total variation distance from its stationary distribution. It reaches 10⁻⁶ after 1002 steps. The dashed line is |λ₂|ᵏ with λ₂ = 0.986994 from the walk matrix, and the number of steps that predicts is 1055. The distance is not the eigenvalue: for the first several steps the walk is leaving one block and the decay is faster than the asymptote, and the two curves become parallel only once the slowest mode is all that is left. The eigenvalue is a rate, not a schedule, and the difference between them is 53.3 steps.0143286429572715858100110⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹1steps of the walkdistance from stationarya rate read as a timeλ₂ of the walk0.99steps measured1002steps predicted1055ratio0.95the dashed line is the eigenvaluethe curve is the walk
Fig. 2 The same experiment with the blocks barely joined, where the walk takes a thousand steps and the prediction is still within five per cent.

And now the claim that is not true

PageRank’s power iteration is said to contract by α a step. It is in every account of the method, it is the basis of every statement about how many iterations are needed, and it is a corollary of a theorem about the Google matrix’s second eigenvalue.

The theorem says the second eigenvalue of αP + (1 − α)v1ᵀ is α·λ₂(P), not α. The two agree exactly when λ₂(P) = 1.

λ₂(P) = 1 happens when the chain has more than one closed communicating class — when the link graph is in pieces that cannot reach each other. A real web graph is exactly that: a giant component, a large number of small islands, and no path from most of the islands back to the main body. So λ₂(P) = 1 holds, and the folk rate is exact.

It is not exact on a connected graph. Measured, at two values of α on three connected graphs:

graph               λ₂(P)      α      predicted α·λ₂   measured rate
two blocks 50      0.902380   0.50       0.4512          0.4509
two blocks 50      0.902380   0.85       0.7670          0.7668
two blocks 60      0.828870   0.50       0.4144          0.4147
grid 5×6           0.910790   0.50       0.4554          0.4551
two islands        1.000000   0.50       0.5000          0.4848
two islands        1.000000   0.85       0.8500          0.8271

On the connected graphs the measured rate matches α·λ₂(P) to four digits and is nowhere near α. On the graph built in two closed pieces it matches α.

So a widely quoted rate is correct because of a property of the data that is never mentioned when the rate is quoted. It is not wrong and it is not tight for the reason anybody thinks: the analysis gives α·λ₂(P), the web supplies λ₂(P) = 1, and the two coincide by accident of subject matter.

Why this is worth more than a correction

Two consequences follow, and the second is the one that matters.

On a connected graph the iteration is faster than advertised, by exactly the factor λ₂(P). On the grid above that is a factor of 0.91 a step, which compounds: reaching 10⁻¹² takes 289 steps at the folk rate and 261 at the real one. Nobody is harmed by a pessimistic estimate, but a run sized by it is doing ten per cent more work than it needs to.

And a graph’s connectivity is now a performance parameter. If λ₂(P) is what decides the rate, then anything that changes the graph’s connectivity changes how long a PageRank computation takes — adding links between islands, merging crawls, restricting to a strongly connected core. Those are decisions made for other reasons, and the folk rate says they cannot possibly affect the cost. They can, and by the ratio between λ₂(P) and 1.

This is the shape the site keeps finding when a rate is quoted without its derivation: a rate that is known in advance is about the stationary iterations whose asymptotic factors are exact and whose transients are not, and the rate the condition number predicts is about a bound that is correct and is attained only when the spectrum has no structure. The pattern is that a rate is a statement about a spectrum, and quoting it without the spectrum is quoting a coincidence.

Where it starts hardly matters

One assumption in the table is worth checking, because a rate that is only asymptotic could easily be dominated by the transient, and the transient depends on where the walker began.

Starting the same walk at seven different vertices of the two-block graph, chosen to span the degree range from eight to eighteen and to include vertices in both blocks:

start vertex   degree   steps to 10⁻⁶
 0              12          122
 1              11          125
29              18          125
30              12          126
59               9          127
 4              18          126
 6               8          126

Four per cent, across the whole range. The starting vertex is worth five steps out of a hundred and twenty-five, and its degree does not correlate with anything.

That is the asymptotic rate earning its keep. The transient differs between starts — a walker beginning at a high-degree vertex is closer to stationarity after one step than one beginning at a leaf — but the difference is spent within a dozen steps, and the remaining hundred and ten are the slow mode, which is the same slow mode whatever the start.

It also means the seven per cent discrepancy in the first table is not a start artefact. It is the transient, it is the same size wherever the walk begins, and it is a property of the graph rather than of the experiment.

What to measure instead

The honest procedure is three lines and none of them is expensive relative to the run they are sizing.

Compute λ₂ of the walk, symmetrically. D^{-1/2}AD^{-1/2} is symmetric, so the site’s own eigensolver applies, and one eigenvalue of a sparse symmetric matrix is a few dozen matrix–vector products.

Predict, and expect to be five per cent high. log(1/ε)/log(1/|λ₂|) was between 1.05 and 1.08 times the measured step count across a sixty-fold range here. That is a good enough estimate to size a run and a poor enough one that it should be reported as an estimate.

And measure the thing being waited for, not the iterate’s change. The total variation distance in the figure is available only because the stationary vector is known here; in practice what is measured is the change between iterates, and the change underestimates the remaining error by a factor of 1/(1 − |λ₂|). At |λ₂| = 0.987 that factor is seventy-seven. A run stopped when the change falls below 10⁻⁸ is 10⁻⁶ from the answer, and nothing in its output says so.

The one thing the eigenvalue does not say

A closing caveat, because the whole essay has been about a single number and there is a question it cannot answer.

|λ₂| says how fast the worst starting distribution decays. It says nothing about how fast a particular functional of the walk converges, and functionals are usually what is wanted. A walk used to estimate the expected value of something concentrated on a few vertices can be accurate long before the distribution has mixed, because the modes that are still alive may have almost no component on those vertices. Equally it can be inaccurate long after, if they do.

This is the same distinction the trace estimation essays make about a randomised estimator: the variance of the quantity being estimated is not the variance of the vector it is computed from, and a bound on one is not a bound on the other.

The practical form of it is that a mixing time is an upper bound on the burn-in a sampler needs and is usually a pessimistic one. Sizing a run by it is safe and can be expensive; sizing a run by watching the quantity of interest is cheap and can be wrong, because a quantity that has stopped moving may be stuck rather than converged. Neither is a substitute for the other, and the honest procedure runs both — which is the same conclusion the stopping-test essays reach about a residual.

At other settings

314 steps to forget where it started, and λ₂ said 329A random walk on a sixty-vertex graph with two blocks joined at a density of 0.01, started at one vertex, measured as the total variation distance from its stationary distribution. It reaches 10⁻⁶ after 314 steps. The dashed line is |λ₂|ᵏ with λ₂ = 0.958917 from the walk matrix, and the number of steps that predicts is 329. The distance is not the eigenvalue: for the first several steps the walk is leaving one block and the decay is faster than the asymptote, and the two curves become parallel only once the slowest mode is all that is left. The eigenvalue is a rate, not a schedule, and the difference between them is 15.3 steps.0459013518022527031510⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹1steps of the walkdistance from stationarya rate read as a timeλ₂ of the walk0.96steps measured314steps predicted329ratio0.95the dashed line is the eigenvaluethe curve is the walk
Fig. 3 At a density of 0.01, where the walk takes three hundred steps.
169 steps to forget where it started, and λ₂ said 178A random walk on a sixty-vertex graph with two blocks joined at a density of 0.02, started at one vertex, measured as the total variation distance from its stationary distribution. It reaches 10⁻⁶ after 169 steps. The dashed line is |λ₂|ᵏ with λ₂ = 0.92517 from the walk matrix, and the number of steps that predicts is 178. The distance is not the eigenvalue: for the first several steps the walk is leaving one block and the decay is faster than the asymptote, and the two curves become parallel only once the slowest mode is all that is left. The eigenvalue is a rate, not a schedule, and the difference between them is 8.63 steps.02448729612014416810⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹1steps of the walkdistance from stationarya rate read as a timeλ₂ of the walk0.93steps measured169steps predicted178ratio0.95the dashed line is the eigenvaluethe curve is the walk
Fig. 4 At 0.02, where it takes one hundred and sixty-nine.
36 steps to forget where it started, and λ₂ said 38A random walk on a sixty-vertex graph with two blocks joined at a density of 0.08, started at one vertex, measured as the total variation distance from its stationary distribution. It reaches 10⁻⁶ after 36 steps. The dashed line is |λ₂|ᵏ with λ₂ = 0.698104 from the walk matrix, and the number of steps that predicts is 38. The distance is not the eigenvalue: for the first several steps the walk is leaving one block and the decay is faster than the asymptote, and the two curves become parallel only once the slowest mode is all that is left. The eigenvalue is a rate, not a schedule, and the difference between them is 2.44 steps.0510152025303510⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹1steps of the walkdistance from stationarya rate read as a timeλ₂ of the walk0.7steps measured36steps predicted38ratio0.94the dashed line is the eigenvaluethe curve is the walk
Fig. 5 At 0.08, where the transient is most of the run and the prediction is worst.
16 steps to forget where it started, and λ₂ said 17A random walk on a sixty-vertex graph with two blocks joined at a density of 0.2, started at one vertex, measured as the total variation distance from its stationary distribution. It reaches 10⁻⁶ after 16 steps. The dashed line is |λ₂|ᵏ with λ₂ = 0.450568 from the walk matrix, and the number of steps that predicts is 17. The distance is not the eigenvalue: for the first several steps the walk is leaving one block and the decay is faster than the asymptote, and the two curves become parallel only once the slowest mode is all that is left. The eigenvalue is a rate, not a schedule, and the difference between them is 1.33 steps.0246810121416182010⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹1steps of the walkdistance from stationarya rate read as a timeλ₂ of the walk0.45steps measured16steps predicted17ratio0.92the dashed line is the eigenvaluethe curve is the walk
Fig. 6 And at 0.2, where the walk finishes in sixteen steps and the asymptote is barely reached.
Contracting by 0.7668 where the folk rate says 0.85The PageRank power iteration on a connected fifty-vertex graph, at α = 0.85, plotted as the change between successive iterates. The upper dashed line is αᵏ, the rate every account of the method quotes. The lower one is (α·λ₂(P))ᵏ, which is what the second eigenvalue of the Google matrix actually is: λ₂(P) = 0.90238 here. The measured contraction over the run is 0.76683. The two agree exactly when λ₂(P) = 1, which happens exactly when the link graph has more than one closed communicating class — which every real one does, and which is why a statement that is false of connected graphs has never been noticed to be. The answer is checked against one elimination of I − αP̃, which agrees to 1.04·10⁻¹⁶.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
Fig. 7 The two rates on a connected graph, where the folk one is the upper dashed line.
The published rate is α, and it is α because the graph is in piecesThe PageRank power iteration on a link graph in two closed pieces, at α = 0.85, plotted as the change between successive iterates. The upper dashed line is αᵏ, the rate every account of the method quotes. The lower one is (α·λ₂(P))ᵏ, which is what the second eigenvalue of the Google matrix actually is: λ₂(P) = 1 here. The measured contraction over the run is 0.84123. The two agree exactly when λ₂(P) = 1, which happens exactly when the link graph has more than one closed communicating class — which every real one does, and which is why a statement that is false of connected graphs has never been noticed to be. The answer is checked against one elimination of I − αP̃, which agrees to 1.39·10⁻¹⁶.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
Fig. 8 And on a graph in two closed pieces, where the folk rate is the answer.
The lower bound is attained and the upper one is out by 37.3×Cheeger's inequality on nine graphs of about 40 vertices each: for the normalised Laplacian's λ₂, λ₂/2 ≤ φ ≤ √(2λ₂), where φ is the conductance the sweep cut actually achieves. Each row shows the two bounds as a bar and the measured conductance as a dot inside it. The lower bound is tight on the complete at a ratio of 1. The upper bound is loosest on the barbell — by a factor of 37.3 — which is the graph in the census with a real bottleneck, and therefore the shape the inequality is always quoted about. The square root is what makes it loose: it is the price of turning a spectral quantity into a combinatorial guarantee, and it is paid where the guarantee is wanted.10⁻³10⁻²10⁻¹110¹12345678910conductance, and the two bounds on itpathcyclegridbarbelltwo blockshypercubepreferentialstarcompletethe bar is the inequalitythe dot is the graph
Fig. 9 The same eigenvalue read as a bound on a cut rather than as a rate.
One real vector, 59 candidate cuts, and the best of them is number 30The Fiedler vector of the two blocks 60, its entries sorted, drawn as the pale rising curve against the right-hand scale; and against the logarithmic left-hand scale, the conductance of the cut that takes the first k vertices in that order. λ₂ = 2.5538. The eigenvector is a real vector and the answer wanted is a subset, so something has to round it: the sweep takes every prefix and keeps the best, which here is k = 30 at a conductance of 0.08982 against a worst prefix of 1 — a factor of 11.1 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.010203040506010⁻¹1vertices on the smaller sideconductance of the prefix cut0.0898, the best prefixthe rounding stepλ₂2.6cuts considered59best conductance0.09at k =30worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs
Fig. 10 The partition the bottleneck defines, on the graph the walk is slow on.
two blocks 60: 60 vertices, 504 edges, and a matrix built from themThe two blocks 60 laid out at its own second and third Laplacian eigenvectors, so the picture is the same object the measurements are about. The Laplacian L = D − A is built by subtraction of integers, so every row sums to exactly zero — measured at 0, not at the rounding level — and L·1 is the zero vector with no arithmetic error anywhere in it. Its 1 zero eigenvalue counts the connected components, which breadth-first search also puts at 1; the smallest non-zero eigenvalue is 2.554 and the largest computed zero is 1.51·10⁻¹⁵, a gap of 1.69·10¹⁵. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 1012.the matrix, measuredvertices60edges504‖L·1‖∞0zero eigenvalues1components, by search1λ₂2.6laid out at its own eigenvectorsand the row sums are exactly zero
Fig. 11 The graph itself, whose two blocks the walk has to cross.
barbell 12: 24 vertices, 133 edges, and a matrix built from themThe barbell 12 laid out at its own second and third Laplacian eigenvectors, so the picture is the same object the measurements are about. The Laplacian L = D − A is built by subtraction of integers, so every row sums to exactly zero — measured at 0, not at the rounding level — and L·1 is the zero vector with no arithmetic error anywhere in it. Its 1 zero eigenvalue counts the connected components, which breadth-first search also puts at 1; the smallest non-zero eigenvalue is 0.1443 and the largest computed zero is 8.24·10⁻¹⁶, a gap of 1.75·10¹⁴. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 292.the matrix, measuredvertices24edges133‖L·1‖∞0zero eigenvalues1components, by search1λ₂0.14laid out at its own eigenvectorsand the row sums are exactly zero
Fig. 12 A more extreme bottleneck, where the walk is correspondingly slower.
Jacobi, Gauss–Seidel and SOR at ω = 1.777A semi-logarithmic plot of relative residual against iteration for three stationary methods, with dashed reference curves showing the rate each is predicted to contract at.015030045060075090010⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹iteration‖r‖ / ‖b‖JacobiGauss–SeidelSOR ω=1.78closed form vs measuredρ Jacobi, exact0.99ρ measured0.99ρ Gauss–Seidel, exact0.981D Laplacian, n = 24ω optimal = 1.777
Fig. 13 Stationary iterations against the rates they were predicted to have, in the iterative field.
Conjugate gradients at κ = 104, against the bound κ permitsA semi-logarithmic plot of the relative A-norm error against iteration count. The measured curve falls below a smooth dashed curve showing the classical condition-number bound.0408012016020024010⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹iteration‖e‖_A / ‖e₀‖_Ameasuredκ bound119 steps40×40, spectrum spread evenly in logbound permits 1417
Fig. 14 A convergence bound against the curve it bounds.
LSQR steps to a normal residual of 10⁻¹², with and without a sketched preconditionerTwo curves against κ(A). The unpreconditioned solve takes 15, 22, 32, 59, 150 steps as the conditioning worsens, and at the worst one it does not reach the tolerance inside 150. The preconditioned solve takes 10, 10, 10, 10, 10 — flat across eight decades. Both return the same vector, to the accuracy the problem allows: the preconditioned answer and the direct one differ by about κ(A)·u at every κ, 5.7·10⁻⁶ at the worst. The SAME sketch used as an answer instead of as a preconditioner is 4.5 away.10²10⁴10⁶10⁸10¹⁰110¹10²10³condition number of the matrixLSQR steps to 10⁻¹²no preconditionersketchedthe cost, not the answersteps, preconditioned10steps, without150answer gap, preconditioned5.7·10⁻⁶κ(A)·u at the worst κ1.1·10⁻⁶answer gap, sketch-and-solve4.5one sketch, two things to do with itand only one of them moves the answer
Fig. 15 What changing a spectrum on purpose buys in steps.
The condition number a sketched preconditioner leaves, against the condition number it was givenTwo curves against κ(A), both axes logarithmic. The matrix's own condition number climbs the diagonal from 100 to 10¹⁰; κ(AR⁻¹), where R comes from a QR of a 4n-row sketch, is 2.2284 at every one of them — the same number to ten digits, not a similar one. The reason is two lines of algebra: with G = SU the preconditioned singular values are those of (GᵀG)⁻¹, which has no spectrum of A in it at all.10²10⁴10⁶10⁸10¹⁰110²10⁴10⁶10⁸10¹⁰condition number of the matrixcondition number seen by the iterationκ(A), unchangedκ(AR⁻¹)a bound with no κ(A) in itκ(AR⁻¹), every κ(A)2.2κ(SU), the other route2.2κ(A), across the sweep10⁸κ(AR⁻¹), across the sweep1the sketch never sees the spectrumand the spectrum cancels out of the answer
Fig. 16 And what it does to the spectrum itself.
What a rank-10 approximation can achieve, by spectrumA semi-logarithmic plot of singular value against index for three spectra — geometric decay, algebraic decay, and flat — with the rank-ten approximation error marked on each.1112131415110⁻³10⁻²10⁻¹1index jσⱼσ11geometric, 0.85ʲalgebraic, j^−1.00flatmeasured, and equal to σ₁₁rank-10 error, geometric0.2rank-10 error, algebraic0.091rank-10 error, flat160×60, spectrum chosen rather than the entriesthe matrix decides, not the method
Fig. 17 A spectrum whose shape decides a rate.
The spectrum of C⁻¹T against T's own, n = 64, ρ = 0.8Two sorted spectra on a linear vertical axis. The unpreconditioned Toeplitz matrix spreads its eigenvalues across its whole range; the preconditioned operator puts 97% of them within a tenth of 1, with 0 below zero.08162432404856640123456789index, sortedeigenvalueT aloneC⁻¹Teigenvalues, not singular valuesfraction within 0.1 of 10.97eigenvalues below zero0λ_min of the preconditioner0.11the dashed line is 1, where the cluster formsthe solid line is zero
Fig. 18 A clustered spectrum, where an asymptotic rate is reached quickly.
The residual basis of conjugate gradients, at κ = 106A semi-logarithmic plot against iteration count showing the loss of orthogonality among the residual vectors rising while the relative residual falls.05101520253010⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹iteration‖RᵀR − I‖ and ‖r‖/‖b‖step n‖RᵀR − I‖residual30×30, run for exactly n stepsexact arithmetic would end here
Fig. 19 Orthogonality lost while a rate is being measured.
The accuracy asked for, against the accuracy obtained, for two kernels on one partitionε is applied to each block against that block's own largest singular value; the error is then reported against the whole matrix's norm. The two are not the same number and the dashed diagonal is where they would be. For 1/r the obtained error is 29 times smaller than the tolerance asked for; for log r on the identical partition it is 13 times smaller. Both curves are straight and parallel to the diagonal, so the knob does what a knob should — a decade in buys a decade out — and neither of them sits on it. The factor is how much of the matrix's mass lives off the diagonal, which is a property of the kernel; it is not the number of blocks, which is 112 and would put the curves on the other side of the diagonal.10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³ε asked for, per block‖A − A_H‖ ⁄ ‖A‖ obtainedasked = obtainedlog r1 ⁄ rtwo numbers, not one1/r, obtained at 10⁻⁸3.4·10⁻¹⁰log r, obtained at 10⁻⁸7.8·10⁻¹⁰1/r, obtained ⁄ asked0.034log r, obtained ⁄ asked0.078blocks in the partition112the tolerance is per blockand the error is per matrix
Fig. 20 A tolerance asked for against one obtained, which every walk here is stopped by.
What the solver reported, and what it achievedFinal relative residual and final relative error against the working precision, on a logarithmic vertical axis. The residual sits at the stopping tolerance at every precision — the method converged, by every test available to it. The error runs from 1.4·10⁻¹³ at 53 bits to 0.00597 at 8, tracking the unit roundoff, which is drawn beside it.614223038465410⁻¹³10⁻¹⁰10⁻⁷10⁻⁴working significand bitsrelative sizeerrorresidualuthe gap the solver cannot seeerror ÷ residual at 24 bits1.5·10⁶error ÷ residual at 16 bits2.3·10⁷error ÷ residual at 8 bits2.4·10¹⁰every convergence test passesand the answer is wrong in proportion to u
Fig. 21 A residual that says nothing about the error, which an iterate’s change also does not.
14 of 14 places survive the arithmetic and 3 survive one missing linkThe top 15 of a PageRank ranking on an eighty-page link graph, and how many of its 14 adjacent comparisons keep their order under three kinds of doubt. Perturbing the teleport vector at the rounding level moves every entry by at most 4.05·10⁻¹¹ and settles 14 of them. Moving α across the range everybody uses moves entries by 0.00123 and settles 11. Removing a single arc — one link that might or might not have been crawled — moves entries by 0.00443 and settles 3. The gaps between consecutive entries run from 6.28·10⁻⁵ to 0.00241, so the ordering is decided by the data at a scale ten orders above anything the arithmetic does. This is the one field on the site where the computation is not the weakest part of the answer.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
Fig. 22 What the answer this walk converges to is determined by.
4 entries of a strictly positive vector are negativeThe Perron eigenvector of a twelve-vertex clique with a tail of 24, normalised to its largest entry, plotted as absolute values on a logarithmic axis. Perron–Frobenius says every entry of this vector is strictly positive, and it is a theorem about a connected nonnegative matrix rather than a statement about a good day. Each step along the tail divides the entry by about the Perron root 11.0077, so the entries fall by a decade a step and reach the rounding level after sixteen. Beyond it 4 of them are negative — the smallest at -1.507·10⁻²⁰ — and they are drawn as open circles. The bracket printed beside it is Collatz–Wielandt: for any strictly positive x, the Perron root lies between the smallest and largest of (Ax)ᵢ/xᵢ, so it is a two-sided bound that is proved, from one product, and after forty steps it is 1.2·10⁻⁴ wide.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
Fig. 23 The positivity of the vector the walk converges to, where the arithmetic loses it.
Twenty eigenvalues, one of them zero, and the graph has one pieceThe Laplacian spectrum of two ten-vertex paths joined by a single edge of conductance 0.01, plotted on a logarithmic axis so the zero end is visible. The dashed line is the threshold 10⁻¹⁰‖L‖ = 1.02·10⁻⁹, and the number of eigenvalues below it is the spectral count of connected components: 1. Breadth-first search, which performs no arithmetic on any weight, says 1. The largest computed zero is 6.99·10⁻¹⁷ and the smallest eigenvalue above the threshold is 0.001891. A count of components is therefore a rank decision at a threshold, and the bridge's conductance decides which side of it λ₂ falls on — at nine orders above the rounding level, not at it.13579111315171910⁻¹⁹10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹indexeigenvalue of L10⁻¹⁰‖L‖, the thresholda count that is a thresholdeigenvalues below it1components, by search1largest computed zero7·10⁻¹⁷smallest above it0.0019ratio2.7·10¹³the graph is connectedat every stop of the slider
Fig. 24 The spectrum whose second entry is the rate in this essay.
How far a perturbation of size ε moves an eigenvalue, 8×8A log–log plot of eigenvalue movement against perturbation size. The symmetric case lies on a line of slope one; the non-symmetric case lies on a line of slope one eighth, and at a perturbation of ten to the minus sixteen it has already moved by a hundredth.10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹size of the perturbation ‖δA‖how far the eigenvalues moveJordan block, ε^(1/8)symmetric, ≤ ‖δA‖rounding error alone moves it to 10⁻²six seeds per symmetric point; Jordan is closed formsymmetry beats precision
Fig. 25 How far an eigenvalue moves when its matrix does, which decides how stable a rate is.
Backward and forward error against the condition numberA log–log plot over twelve decades of condition number. The backward error is a flat line at ten to the minus sixteen; the forward error rises in proportion to the condition number.110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)relative errorforward errorbackward errorpredicted: κ · u8×8, 20 seeds per κ; dashed is the worstthe problem worsens, not the method
Fig. 26 The two errors, in the field that separated them.
Backward error, forward error and the condition number, with measured valuesTwo boxes at the top — the problem posed and the nearby problem the algorithm answered exactly — and two answers below them, with the distances between all four labelled by numbers from a Hilbert solve.the problem you posedA = H10b = A·(1, 2, …, 10)the problem it answered exactlyA + δA, b + δb‖δ‖ / ‖A‖ = 2.3·10⁻¹⁷the answer you wantedx = (1, 2, …, 10), exactlythe answer you gotx̂, wrong by 2.7·10⁻⁴ relativebackward error 2.3·10⁻¹⁷forward error 2.7·10⁻⁴κ = 1.6·10¹³κ · η = 3.6·10⁻⁴, and the measured forward error is 2.7·10⁻⁴.The algorithm is not at fault. The problem is.H10, LU with partial pivotingresidual and error differ
Fig. 27 The identity every measurement here is read against.
Growth factor under partial pivoting to n = 40: the bound, the worst case, and realityGrowth factor against matrix size on a logarithmic vertical axis. The two-to-the-n bound rises as a straight line; Wilkinson's matrix sits exactly on it; random matrices stay near one.0816243240110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴matrix size ngrowth factor max|u| / max|a|the 2ⁿ⁻¹ boundworst of 30 randommedian randomWilkinson's matrix sits on the bound30 Gaussian matrices per sizeat n = 40: bound 5.5·10¹¹, worst 4.8
Fig. 28 A bound never attained, which the mixing prediction is nearly the opposite of.
The exact solution of a 13×13 Hilbert system beside the computed oneTwo columns of numbers: the exact answer, which is the integers one to thirteen, and the answer double-precision elimination returns, with the number of correct digits beside each.H13 x = b, b formed exactly so that x = (1, 2, …, 13)12345678910111213exact1.00002.00003.00133.97865.18864.993010.46720.048921.2657-2.575319.21478.906013.5113computed6.6 correct digits4.8 correct digits3.4 correct digits2.3 correct digits1.4 correct digit0.8 correct digitno correct digitsno correct digitsno correct digitsno correct digitsno correct digits0.6 correct digit1.4 correct digitbackward error2.2·10⁻¹⁷κ = 1.7·10¹⁸The algorithm solved a neighbouring problem perfectly. That problem's answer is this one.right-hand side built in BigInt rationalsthe truth is known
Fig. 29 An answer that is known, which the stationary vector of an undirected walk also is.

Where this goes next

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. 10⁻³10⁻²10⁻¹110¹12345678910conductance, and the two bounds on itpathcyclegridbarbelltwo blockshypercubepreferentialstarcompletethe bar is the inequalitythe dot is the graph A bound with a square root in it Cheeger's inequality brackets a graph's best cut between λ₂/2 and √(2λ₂). The lower bound is attained exactly. The upper one is loose by a factor of fourteen — on the one graph in the census with a real bottleneck, which is the shape it is always quoted about. 0408012016020024010⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹iteration‖e‖_A / ‖e₀‖_Ameasuredκ bound119 steps40×40, spectrum spread evenly in logbound permits 1417 The rate the condition number predicts Conjugate gradients converge at a rate governed by the square root of the condition number. That is a bound rather than an estimate, it is provable, and it is loose enough that provisioning iterations from it wastes nine out of ten.

What links here

Computed from the collection, not written here: the essays that point at this one.

Named objects

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

BipartiteConductanceMixing timeNormalised laplacianPagerankPower iterationRandom walkSpectral gapTotal variation distance