Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Symmetry — where it appears

The property Aᵀ = A, which is worth a short recurrence, real eigenvalues, an unambiguous divisor and half the arithmetic. It buys a short recurrence, real eigenvalues, half the arithmetic and an unambiguous pivot, which together are worth more than several extra digits of precision.

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

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

Symmetry is worth more than precision

A symmetric matrix gives up its eigenvalues to full accuracy however ill-conditioned it is. An unsymmetric one can move them by the eighth root of a perturbation, so the rounding involved in merely storing the matrix shifts the spectrum by a hundredth.

spectra · Eigen conditioning Re λIm λwhat survives the arrowsvertices18arcs18worst row sum0worst column sum0largest |Im λ|0.98asymmetry1the null vector is still exactand nothing else about the spectrum is real

A Laplacian that is not symmetric

Point the edges and the matrix stops being symmetric. Its row sums are still exactly zero, so the null vector survives; everything built on the quadratic form does not, and the eigenvalues need a plane rather than a line. Asymmetry permits that and does not force it, which the smallest case here demonstrates by being asymmetric and real.

graph · Directed laplacian 10¹10⁴10⁷10¹⁰10¹³10¹⁶10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹κ(B)relative error, and asymmetryvia B⁻¹Avia Choleskyasymmetry of B⁻¹Au · κ(B)against a spectrum known exactlyslope, via B⁻¹A0.92slope, via Cholesky0.98worst ratio between them2.3asymmetry of B⁻¹A1.1the symmetry claim is trueand it is not about the accuracy

Two matrices and one problem

Ax = λBx is what a finite element model, a structural vibration and a constrained optimisation actually produce, and it is not the one-matrix problem with a change of variables. Everybody is told not to form B⁻¹A because it is not symmetric. That is true, the departure from symmetry is about one, and it is not what decides the accuracy.

spectra · Pencil

Named alongside it

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

OrthogonalityBackward errorCholeskyComplex eigenvaluesCondition numberDirected graphEigenvalue condition numberEigenvalue sensitivityEigenvaluesGeneralised eigenvalue problemGraph laplacianJacobi's eigenvalue method

All concepts