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

The vector that has to be rounded

A spectral partition is an eigenvector, and an eigenvector is a real vector. The answer wanted is a subset. Something has to turn one into the other, and the something is a heuristic applied after the linear algebra has finished.
32 min read 29 figures Where the algebra stops being the arithmeticMeasured, not assertedTwo routes to a number

Worth reading first: A matrix with no numbers in it · An eigenvector that must not change sign · A bound with a square root in it.

Asked to cut a graph into two well-connected pieces, the spectral method returns a real vector of length n with entries like −0.3117 and 0.0842. Asked for a partition, a caller wants a set of vertices. Between those two sentences is a step that is not linear algebra, and it is where every guarantee the linear algebra provides has to be re-established or given up.

One real vector, 23 candidate cuts, and the best of them is number 12The Fiedler vector of the barbell 12, 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. λ₂ = 0.14435. 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 = 12 at a conductance of 0.007519 against a worst prefix of 1 — a factor of 133 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.0481216202410⁻²10⁻¹1vertices on the smaller sideconductance of the prefix cut0.00752, the best prefixthe rounding stepλ₂0.14cuts considered23best conductance0.0075at k =12worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs
Fig. 1 The second eigenvector of a barbell, sorted, against the conductance of every cut that takes a prefix of that order. The dashed curve is the answer the algebra gives; the solid one is what each of its roundings costs.

What the relaxation actually solved

The problem anybody wants solved is combinatorial. Over all subsets S of the vertices, minimise the conductance

φ(S) = (weight of edges leaving S) ÷ (total degree of the smaller side)

which is NP-hard, and for which the number of candidates is 2ⁿ⁻¹ − 1.

The spectral method solves a different problem. Write the cut as a vector — one value on S, another off it — and the numerator becomes the quadratic form xᵀLx. Then drop the requirement that x take only two values, keeping only that it be orthogonal to the constant vector and of unit length. The minimum of the Rayleigh quotient over that set is λ₂, attained at the second eigenvector.

That is a relaxation in the exact sense: the feasible set has been enlarged, so the minimum can only have gone down, and λ₂ is a lower bound on something related to the combinatorial optimum. What it is not is an answer to the original question, because the vector it returns is almost never one of the two-valued vectors the original question was about.

The rounding step, and why it is a sweep

The standard repair is the sweep. Sort the vertices by their entry in the eigenvector; consider the n − 1 prefixes of that order; compute the conductance of each; keep the best.

It is a good heuristic for a specific reason. The eigenvector’s ordering carries the information the relaxation found — vertices the graph keeps close have similar entries — while its actual values, which are the part the relaxation invented, are discarded. Only the order survives, and only n − 1 of the 2ⁿ⁻¹ − 1 candidate subsets are ever examined.

The figure above draws both halves at once: the pale dashed curve is the sorted eigenvector, and the solid curve is the conductance of the prefix ending at each position. The minimum of the second is the answer returned, and where it falls is decided by the ordering of the first.

How flat is the minimum

The first thing to measure is whether the minimum is a minimum or a plateau, because a plateau means the position of the answer is decided by something small.

graph          best φ      at k    cuts within 5% of best
barbell 10     0.010989     10       1 of 19
two blocks 60  0.089820     30       1 of 59
grid 6×7       0.098592     21       3 of 41
path 30        0.034483     15       1 of 29
preferential   0.232143     29       2 of 59

On four of the five, exactly one prefix is within five per cent of the best, and the curve either side of it rises steeply. The grid has three, and they are the three cuts across the middle of a rectangle, which are genuinely almost equally good.

So on graphs with a real bottleneck the sweep’s minimum is sharp, and a small perturbation of the eigenvector does not move it. That is the encouraging half, and it is worth having before the discouraging one.

How far the answer is from the best answer

The second thing to measure is the gap between what the sweep returns and the actual combinatorial optimum — which can only be done on graphs small enough to enumerate.

Thirteen vertices gives 8,190 non-trivial subsets, which is a fraction of a second. Over forty random graphs at edge probability 0.28, of which thirty came out connected:

suboptimal                13 of 30
median ratio               1.0000
mean ratio                 1.0691
worst ratio                1.4773

Thirteen of thirty times the sweep returns a cut that is not the best one. The median is exactly one — most of the time it finds the optimum — and the worst case returns 0.4545 where the best possible is 0.3077, a factor of 1.48.

Both halves of that are the result. The method is right much more often than a bound would suggest, and when it is wrong it is wrong by tens of per cent rather than by a rounding, because the answer is a different subset rather than a perturbed one.

On the structured families this field builds — the barbell, the two-block graph, the grid, the path — the sweep finds the exact optimum every time, and the reason is that those graphs have one obvious cut and the relaxation finds it. The random graphs at thirteen vertices have no obvious cut, several nearly equally good ones, and that is where the ordering of the eigenvector stops being enough information.

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. 2 A planted two-block graph, where the minimum is sharp and the sweep finds the optimum.

The cheaper rounding, and what it costs

There is an even simpler rule than the sweep, and it is the one most people reach for first: split at zero. The second eigenvector is orthogonal to the constant, so it has entries of both signs, and the sign pattern is a partition without any further work.

It is free, and on the structured families it is the same answer:

graph          sweep φ     sign φ    ratio
barbell 10     0.010989   0.010989   1.000
two blocks 60  0.089820   0.089820   1.000
grid 6×7       0.098592   0.098592   1.000
hypercube 5    0.300000   0.300000   1.000
preferential   0.238938   0.268817   1.125

On five of six the sign cut lands exactly on the sweep’s answer, because on a graph with one obvious cut the eigenvector changes sign exactly where the cut is. On the preferential-attachment graph it is twelve per cent worse.

Over the thirty random graphs the difference is larger and more systematic: the sign cut is worse than the sweep on sixteen of thirty, its mean ratio against the true optimum is 1.152 against the sweep’s 1.069, and its worst case is 1.55 against 1.48.

The reason is what the two rules use. The sign cut reads one number from the eigenvector — where it crosses zero — and that number is a property of the values, which are the part of the eigenvector the relaxation invented. The sweep reads only the ordering, which is the part that carries information about the graph, and then chooses among n − 1 candidates by evaluating the objective directly. It costs one sort and one pass, which against the cost of computing the eigenvector is nothing, and it never returns a worse cut than the sign rule because the sign cut is one of the prefixes it considered.

What λ₂ is worth as a number

It is tempting to report λ₂ as the quality of the partition, and it is not that. It is a lower bound on a relaxed objective, and the two are related through the inequality rather than through equality.

On the barbell, λ₂ of the normalised Laplacian is 0.01864 and the conductance achieved is 0.01099 — the conductance is below λ₂, which is possible and is not a contradiction, because the inequality bounds φ below by λ₂/2 rather than by λ₂. On the two-block graph λ₂ is 0.15383 and φ is 0.08982. On the grid λ₂ is 0.06297 and φ is 0.09859, the other way round.

So λ₂ is neither an upper nor a lower bound on the answer; the bounds are λ₂/2 and √(2λ₂), and the answer moves around inside them. Quoting λ₂ as “the quality of the cut” is quoting a number that happens to be nearby, and how nearby is what the next essay measures.

What λ₂ is good for is a comparison between graphs, or between the same graph at two moments — a falling λ₂ means the graph is becoming easier to cut, and the statement is exact rather than heuristic. It is a property of the object, computed to fourteen digits, and it is the right thing to report as long as it is not labelled as the answer.

The guarantee that survives the rounding

The reason the sweep is not merely a plausible heuristic is that Cheeger’s inequality is a statement about it rather than about the relaxation.

The upper half, φ ≤ √(2λ₂), is proved by exhibiting a cut, and the cut exhibited is a sweep cut of the normalised eigenvector. So the theorem does not say “a good cut exists”; it says “this algorithm’s output is at most √(2λ₂)”, and the algorithm is the one above.

That is unusual and worth appreciating. Most rounding steps in numerical work are justified after the fact by a measurement. Here the rounding is inside the theorem, and what the theorem costs is a square root — which the next essay measures, and which turns out to be loosest exactly where it is quoted.

One caveat, and the field earns it the hard way: the theorem is about the normalised Laplacian’s eigenvector, swept after dividing each entry by the square root of its degree. Sweeping the combinatorial eigenvector is a different algorithm with no such guarantee, and on the graphs here it sometimes returns a better cut and sometimes a worse one. Two Laplacians of one graph is about the difference between the two objectives; this is what it costs at the last step.

What the rounding has in common with the rest of the site

A real quantity turned into a discrete verdict by a rule applied afterwards is not a new shape here.

Rank is a decision makes it with a threshold on singular values: the singular values are computed accurately, and how many count as non-zero is a rule applied to them. Deciding that a zero has arrived makes it with a breakdown test. A rank that depends on the thread count makes it with the same threshold and a different summation order, and gets three different integers.

What is different here is where the discreteness comes from. In the rank essays the underlying quantity is genuinely continuous and the integer is imposed on it by a caller who wants one. Here the question was discrete before anybody wrote a matrix down: the caller wants a set of vertices, and the continuous object is the thing that was invented, as a means of getting at it.

That reversal changes what “accuracy” means. An eigenvector computed to fourteen digits rather than seven does not produce a better partition; it produces the same partition, because the sweep only reads the order. Computing the eigenvector more accurately buys nothing at all past the point where the ordering is settled — and the essay after next is about the graphs where the ordering is never settled, however accurate the eigenvector.

More than two pieces

Almost nothing in practice wants two pieces, and the extension is where the honesty of the method is most easily lost.

Two routes are used. Recursive bisection cuts in two, then cuts each half in two, and so on: it reuses everything above unchanged, and its defect is that a cut made at the first level cannot be undone at the second, so a three-way structure gets a first cut through the middle of one of its parts. Multiple eigenvectors takes the first k non-trivial eigenvectors, treats each vertex as a point in k dimensions, and clusters those points — which is the standard spectral clustering algorithm, and which replaces one rounding step with a different and larger one, since the clustering in k dimensions is itself an NP-hard problem attacked by a heuristic.

Neither inherits Cheeger’s inequality. There are higher-order analogues, and they are weaker in a specific way: the bound involves λ_k and a factor polynomial in k, so it degrades as more pieces are asked for, and at k of any practical size it is not a useful number.

That is worth saying plainly because the two-piece case is unusually well served and the good fortune does not extend. The bisection theorem is tight enough to be worth quoting; nothing about the k-way case is. The measurements in this field therefore stay with two pieces, where a claim can be checked against an enumeration, rather than reporting a clustering nobody can score.

How accurate does the eigenvector have to be

If the sweep reads only the ordering, then the accuracy the eigenvector needs is whatever settles the ordering, and nothing more. That is a measurable claim rather than a plausible one.

Perturbing the Fiedler vector by a relative ε and re-sweeping, twelve times at each level, and counting how often the partition changes:

graph            10⁻¹⁴   10⁻¹⁰   10⁻⁶   10⁻³   10⁻¹
barbell 10         0       0       0      0      0
two blocks 60      0       0       0      0      0
path 30            0       0       0      0      2
preferential 60    0       0       0      2     12
grid 6×7          10      10      10     10     10

Four of the five are unmoved by a perturbation of ten per cent. An eigensolver stopped at 10⁻⁶ and one stopped at 10⁻¹⁴ return the identical partition on all of them, and the second costs perhaps three times as much. On this evidence a spectral partitioner asking its eigensolver for fourteen digits is buying nothing.

The grid is the exception and it is not a small one: its partition changes on ten runs in twelve at every level tested, including 10⁻¹⁴. Nothing about the perturbation is doing that. A 6 × 7 grid has a symmetry that exchanges its two long halves, its second eigenvector has entries that are equal in exact arithmetic, and the sort therefore has ties in it whose order is decided by whatever the last bits happened to be. Ten of twelve runs return a partition of the same quality — the conductance is 0.098592 every time — and a different set.

That is the situation the essay after next is entirely about, and it is worth noticing here that it arrived while measuring something else: the question “how accurate must the eigenvector be” has no answer on a graph where accuracy is not what decides.

What to compute, and what to report

Three practical consequences, each of which follows from something measured above.

Report the conductance, not the eigenvalue. λ₂ is a lower bound on a related quantity and is not the quality of the cut returned. The conductance costs one pass over the edge list once the partition is known, and it is the number a caller can act on.

Report where the minimum sat. A sweep whose best prefix is at k = 30 of 59, with the next-best five per cent worse, is a different situation from one whose best twelve prefixes are within a per cent of each other. The first is a partition; the second is a suggestion.

Do not spend accuracy on the eigenvector. Past the point where the ordering is settled, more digits change nothing. An iterative eigensolver stopped at 10⁻⁶ and one stopped at 10⁻¹⁴ return the same partition on every graph in this essay, and the second costs three times as much.

At other settings

One real vector, 35 candidate cuts, and the best of them is number 18The Fiedler vector of the grid 6×6, 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. λ₂ = 0.26795. 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 = 18 at a conductance of 0.1 against a worst prefix of 1 — a factor of 10 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.06121824303610⁻¹1vertices on the smaller sideconductance of the prefix cut0.1, the best prefixthe rounding stepλ₂0.27cuts considered35best conductance0.1at k =18worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs
Fig. 3 A grid, whose three best cuts are within five per cent of each other.
One real vector, 29 candidate cuts, and the best of them is number 15The Fiedler vector of the path 30, 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. λ₂ = 0.010956. 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 = 15 at a conductance of 0.03448 against a worst prefix of 1 — a factor of 29 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.05101520253010⁻¹1vertices on the smaller sideconductance of the prefix cut0.0345, the best prefixthe rounding stepλ₂0.011cuts considered29best conductance0.034at k =15worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs
Fig. 4 A path, where the best cut is the middle and the curve rises symmetrically either side.
One real vector, 59 candidate cuts, and the best of them is number 29The Fiedler vector of the preferential 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. λ₂ = 0.5861. 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 = 29 at a conductance of 0.2321 against a worst prefix of 1 — a factor of 4.31 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.01020304050601vertices on the smaller sideconductance of the prefix cut0.232, the best prefixthe rounding stepλ₂0.59cuts considered59best conductance0.23at k =29worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs
Fig. 5 A preferential-attachment graph, where the minimum is shallower and two cuts are nearly tied.
One real vector, 47 candidate cuts, and the best of them is number 24The Fiedler vector of the barbell 24, 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. λ₂ = 0.077152. 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 = 24 at a conductance of 0.001808 against a worst prefix of 1 — a factor of 553 between the best cut this vector offers and the worst. Nothing in the eigenvalue problem chose k; the sorting did.08162432404810⁻³10⁻²10⁻¹1vertices on the smaller sideconductance of the prefix cut0.00181, the best prefixthe rounding stepλ₂0.077cuts considered47best conductance0.0018at k =24worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs
Fig. 6 A larger barbell, where the bottleneck is one edge and the minimum is unmistakable.
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. 7 The bounds this cut is guaranteed to lie between, on nine graphs at once.
One graph, nudged by 10⁻¹², and 3 different partitionsThree seven-vertex cliques joined in a triangle by three single edges, one of whose conductances is raised by 0. When all three are equal the graph has a three-fold symmetry, λ₂ and λ₃ coincide — measured here at a gap of 1.72·10⁻¹⁵ — and there is no Fiedler vector: there is a plane, and every unit vector in it is an exact eigenvector. Eight runs on this graph with its edge weights nudged by a relative 10⁻¹² — four orders above the rounding, and far below anything anybody would call a difference in the data — return 3 distinct partitions, at conductances 0.0455. All of them are correct answers to the relaxation, and on a symmetric graph they are equally good ones. Which one a library returns is decided by its starting vector, and the site has an essay about a plane surviving what its vectors do not.14710131619110¹indexeigenvalue of Lan eigenvalue with no vectorλ₂0.35λ₃0.35gap1.7·10⁻¹⁵partitions found3best conductance0.045worst0.045two eigenvalues, one valueand the answer is not a function of the graph
Fig. 8 A graph where the ordering is never settled, which is the next essay in this anchor.
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. 9 The barbell the hero figure sweeps, laid out at the same eigenvector.
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. 10 The planted partition, where the two clusters are visible in the layout.
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 10⁻⁴, 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 9.42·10⁻¹⁷ and the smallest eigenvalue above the threshold is 1.999·10⁻⁵. 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 zero9.4·10⁻¹⁷smallest above it2·10⁻⁵ratio2.1·10¹¹the graph is connectedat every stop of the slider
Fig. 11 The spectrum whose second entry the whole relaxation is about.
One system, 36 ways to remove its kernel, and 2.85× between themA Laplacian is singular, so a solve has to remove its kernel, and the usual way is to delete one row and column — grounding a vertex, in the electrical reading. Which vertex is a free parameter that no account of the method mentions, and it is set by whichever index the code happens to drop. Every point here is one choice on the grid 6×6: the condition number of the resulting positive definite matrix against the degree of the vertex removed. Grounding vertex 5, of degree 2, gives κ = 275.34; grounding vertex 15, of degree 4, gives 96.565 — a factor of 2.851 between two ways of solving the identical problem. The trend is that a high-degree vertex is the better ground, which has a reading: grounding a vertex fixes its potential, and fixing the potential of something the rest of the graph is strongly attached to constrains more of the graph.23410²degree of the grounded vertexcondition number of what is left96.56, the best choicea parameter nobody setsvertices tried36best κ97at degree4worst κ275at degree2spread2.9one row and column deletedand it matters which
Fig. 12 A different discrete choice inside the same solve, and what it costs.
Singular values of a rank-4 matrix with noise of relative size 10⁻⁸Ten singular values on a logarithmic axis. The first four sit near one; the rest sit at the noise level, and the vertical distance between the two groups is the evidence for the rank.1234567891010⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1indexsingular valuecutoff, σ₁ · 10⁻¹⁰numerical rank 10gap 8.2·10⁶an opiniontrue rank 410×10, built with 4 nonzero valuesrank is a decision
Fig. 13 A threshold turning a continuous quantity into an integer, in the field that named it.
The numerical rank of one matrix is 10, 12, or somewhere betweenSingular values of one 60 × 14 matrix whose spectrum falls by a fixed factor per index, so there is no gap anywhere and the threshold decides the rank. Each curve is the same matrix, its Gram matrix formed with the inner products summed in a different number of pieces. The curves lie on top of each other for the first several values and separate below about 7.3·10⁻¹³, which is where forming AᵀA has put the rounding. The dashed line is the threshold, σ₁ · 10⁻¹⁴. Counting the values above it gives 12 at p = 1, 12 at p = 2, 12 at p = 4, 10 at p = 8, 10 at p = 16, 11 at p = 32, 11 at p = 60 — the rank of one matrix, as a function of how many workers were available. Not a digit of an answer: the number of columns a model built from this matrix would have.13579111310⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹index ksingular valueσ₁ · 10⁻¹⁴, the thresholdone matrix, three rankspartitionings7lowest rank10highest rank12threshold7.3·10⁻¹⁴σ₁7.3the curves separate in the noiseand the threshold is drawn through it
Fig. 14 One matrix with three numerical ranks, which is the same rounding step under a different name.
A randomised rank-k solve, 4 seeds a rankRelative error against the rank kept, on a logarithmic vertical axis, with a vertical bar at each rank spanning the seeds. The band is 1.68 wide at rank 8, where the method is at its worst, and 1.004 wide at rank 20, where it is at its best. The same computation on the same data returns a different answer each time.0481216202428321rank keptrelative errormedianthe answer movesspread at rank 81.7spread at rank 201best median error0.15widest where the method is worstand the bound does not say so
Fig. 15 A rank that is a band rather than a number.
What a perturbation of 10⁻⁶ moves, against the gap it is applied acrossThree curves against the gap between two eigenvalues, both axes logarithmic. Two are flat; the third rises steeply as the gap closes and then levels off.10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻⁸10⁻⁵10⁻²gap between the two eigenvalueshow far it movedthe eigenvectorsthe eigenvaluestheir plane‖E‖ / gapone perturbation, three answerseigenvalue shift, spread over the sweep1plane angle, spread over the sweep1eigenvector angle, spread1.6·10⁵the dashed line is Davis–Kahan's ‖E‖/gaptwo of the three never noticed
Fig. 16 An eigenvector decided by a gap, which is what the ordering here depends on.
Three perturbations of 10⁻¹⁴, three eigenvectors, one planeA circle with three radii at widely different angles, one for each perturbation, and a table of their residuals showing all three satisfy the eigenvalue equation.every radius is an eigenvectorseed 11: 2.0°seed 23: 60.5°seed 41: 18.2°none of them is wrongspread of the returned angles1spread of the returned planes1.3·10⁻¹⁵worst ‖Ax − λx‖5·10⁻¹⁵an exactly repeated eigenvalueno correct answer to fail to return
Fig. 17 What an eigenvector is when its eigenvalue is not simple.
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. 18 How far an eigenvalue moves when the matrix does.
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. 19 A residual that says nothing about the error, which an eigenvector residual here also does not.
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 the last section says not to tighten.
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. 21 The iteration an eigenvector of this size is computed by in practice.
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. 22 Orthogonality lost while computing one, which the sweep does not notice.
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. 23 The two errors, of which only one is visible to a caller.
How much a perturbation of the right-hand side is amplified, κ = 10⁶The cumulative distribution of the amplification factor over two hundred random perturbation directions, with the condition number marked as the upper limit.110¹10²10³10⁴10⁵10⁶10⁷00.250.50.751amplification of the input perturbationfraction of directions at or belowκ = 10·10⁵worst found 7.6·10⁵6×6, 200 directionsmedian reaches 0.29 of κ
Fig. 24 The amplifier belonging to the problem rather than to the algorithm.
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. 25 An answer known exactly, which the enumeration in this essay is a combinatorial version of.
Past the cliff: what each method returnsLoss of orthogonality at four condition numbers past κ²u = 1. Cholesky QR returns a factor whose implied Q is 0.37 away from orthogonal at κ = 10⁸ and 1.49 at 10¹² — and at 3·10¹⁰ it refuses outright, on a pivot of -6.5·10⁻¹⁷. The sweep and the tree return a usable factorisation of every one of these matrices.‖QᵀQ − I‖ of the implied Qκ = 10⁸, Cholesky0.37κ = 10⁸, sweep8.5·10⁻⁹κ = 10¹⁰, Cholesky1.3κ = 10¹⁰, sweep3·10⁻⁷κ = 3·10¹⁰, Choleskyrefusedκ = 3·10¹⁰, sweep6.7·10⁻⁶κ = 10¹², Cholesky1.5κ = 10¹², sweep1.4·10⁻⁴the safe run is the one that failsrefusals in the range1wholly non-orthogonal returns2the pivot it refused on-6.5·10⁻¹⁷one of these outcomes is safeand it is the refusal
Fig. 26 A routine that returns something rather than refusing, which the sweep always does.
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 the measurements here are 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, in the field that measured it first.
Forward error of a 6×6 Hilbert solve at eight precisionsA bar for each significand width from 12 to 53 bits showing the relative error in the computed solution, with the condition number times the unit roundoff marked as a prediction.κ = 1.5·10⁷ · the exact answer is (1, 2, …, 6)12 bits3.316 bits0.8620 bits4.324 bits0.09330 bits7.6·10⁻⁴36 bits6.2·10⁻⁶43 bits2·10⁻⁷53 bits4.5·10⁻¹¹dashed: κ · unit roundoffone matrix, eight arithmeticsmeasured against a known answer
Fig. 29 The precision knob, which this essay argues buys nothing past a point.

Where this goes next

the matrix, measuredvertices40edges223‖L·1‖∞0zero eigenvalues1components, by search1λ₂1.5laid out at its own eigenvectorsand the row sums are exactly zero A matrix with no numbers in it A graph arrives as vertices and edges. Two different matrices can be built from it, they answer different questions, and one of them has a null vector that is exact — the only object on this site whose kernel is known before anything runs. 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. 1234567891010⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1indexsingular valuecutoff, σ₁ · 10⁻¹⁰numerical rank 10gap 8.2·10⁶an opiniontrue rank 410×10, built with 4 nonzero valuesrank is a decision Rank is a decision A floating-point matrix does not have a rank. It has a spectrum of singular values, and somewhere in that spectrum is a place where the values stop being signal and start being noise. Deciding where is a judgement, and the evidence for it is a gap.

What links here

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

Reads more easily once this is understood

Essays that name this one as worth reading first.

Named objects

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

Algebraic connectivityCheeger inequalityCombinatorial optimumConductanceFiedler vectorGraph automorphismRank is a decisionRelaxationSpectral partitionSweep cut