Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Fiedler vector — where it appears

The eigenvector of a graph Laplacian belonging to its second-smallest eigenvalue. It is the relaxed solution of a partitioning problem, so it is a real vector where a subset was wanted, and on a symmetric graph it may not exist at all.

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

Also named here as spectral partition — the same set of essays touches all of them, so they are one junction rather than several.

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

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.

graph · spectral partition 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.

graph · spectral partition 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

A partition decided in the last digit

On a graph with a symmetry there is no Fiedler vector — there is a plane, and every vector in it is an exact eigenvector. Twenty-four runs with the edge weights nudged by 10⁻¹² return ten different partitions of a cycle and, on a hypercube, two different qualities of answer.

graph · spectral partition

Named alongside it

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

ConductanceSpectral partitionAlgebraic connectivityCheeger inequalityGraph automorphismRelaxationSweep cutBound tightnessCombinatorial optimumInvariant subspaceNormalised laplacianRank is a decision

All concepts