Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Fixed point iteration — where it appears

An iteration that stops when its input reproduces its output. Whether it has converged is a question about the condition it was defined by rather than about how far its last step moved, and the two are not the same test.

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

159131721252910⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹steprelative error in the orthogonal factorNewtonNewton, scaledNewton–Schulzone fixed point, three costsscaled Newton, steps7Newton–Schulz, steps28Newton at step 657scaled Newton at step 64.4·10⁻¹³a Newton step needs an inverseand a Schulz step needs two products

An iteration that only multiplies

Newton's iteration for the polar factor needs an inverse every step. Newton–Schulz needs only matrix products — nothing that reads an entry, nothing that pivots — and it converges if and only if every singular value is below √3. At 1.73205 it converges and at 1.73206 it returns an orthogonal matrix that is not the answer, with a residual of 5·10⁻¹⁶ and nothing to say so.

orthogonality · polar decomposition 01234567891011121310⁻¹110¹10²10³iterationinterpolation point σa fixed point that is a conditionorder4iterations13σ against −λ(Aᵣ)2.8·10⁻¹²H₂ error4.3·10⁻⁵it stopped movingand the condition holds there

Interpolating at the model’s own poles

One choice of interpolation points is not arbitrary — the mirrored poles of the model about to be built. It is a fixed point rather than a guess, and when it is reached it beats a method costing O(n³) — by 0.4 per cent, which is the honest size of the whole contest.

reduction · moment matching

Named alongside it

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

Flop countBalanced truncationCondition numberConvergence rateFixed pointH2 normHermite interpolationLyapunov equationMatrix-freeMoment matchingNewton iterationOptimality condition

All concepts