Conditioning — where it appears
Named by 6 essays across 3 fields — each of them below, with the objects they name alongside it.
The vertex nobody solves for
A Laplacian is singular, so every solve with one has to remove its kernel first. There are three ways, they agree to fourteen digits, and the one everybody uses carries a free parameter that no account of the method mentions and that moves the condition number by nine hundred.
A ranking whose order is not determined
Of the fourteen adjacent comparisons in a top-fifteen, fourteen survive perturbing the arithmetic at the rounding level, eleven survive moving the teleportation parameter across its usual range, and three survive removing one link. The computation is the strongest part of the answer.
A perturbation that moves every coefficient
The backward error of a polynomial eigenpair is measured against perturbations of all three coefficients at once. Restrict it to the one coefficient anybody is willing to move and the same computed answers are stable at one eigenvalue and unstable at another, by a factor that runs from 1.06 to 6,370 across a single spectrum.
A preconditioner that is a tree
Every eigenvalue of a tree-preconditioned Laplacian is at least one and at most the total stretch — a combinatorial integer with no arithmetic in it. Measured, the bound is two to four times loose, and on a grid the preconditioner makes the conditioning worse by a factor of 1.85 at every size.
The number that moves when the problem does
Two quantities are offered as the condition number of one eigenvalue. One is unmoved to eight digits by a change of variable that is exact in both directions, and grows like the square root of the chain's length. The other is inflated by ten orders by that change of variable, and is ten times too large before anything has been done at all.
The second factor was the last row
Wilkinson's polynomial in Chebyshev coefficients loses its roots exponentially from the colleague matrix, and two factors accounted for the loss: the roots' own conditioning, and the size of the matrix's last row against the rest of it. A diagonal similarity by powers of two — balancing, which changes no eigenvalue and rounds nothing — removes the second factor entirely: the balanced error sits within a factor of two and a half of the conditioning at every degree from fourteen to forty, three and a half thousand times better than unbalanced at forty. What is left is the conditioning, still exponential. Balancing the monomial companion matrix takes its norm down by forty-five orders and gains nothing, because there the error was never the matrix's.
Named alongside it
The objects these essays reach for when they reach for this one.
Backward errorCompanion formGraph laplacianLinearisationScalingCentralityChebyshev basisCoefficient normsCombinatorial preconditioningCondition numberDeflationEffective resistance