Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Relaxation — where it appears

Enlarging a problem's feasible set so that the enlarged problem can be solved, and rounding the answer back. The minimum can only fall, so it gives a lower bound, and how much is lost at the rounding step is a separate question the bound does not answer.

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

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

Named alongside it

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

Algebraic connectivityCheeger inequalityConductanceFiedler vectorSpectral partitionBound tightnessCombinatorial optimumGraph automorphismNormalised laplacianRank is a decisionSweep cut

All concepts