Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Positive definite — where it appears

The property that xᵀAx is positive for every nonzero x, required by conjugate gradients of both the matrix and its preconditioner.

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

10²110¹10²size niterations to 10⁻¹⁰λ_min(C) changes signno preconditionerStrang's circulantthe preconditioner's own spectrumλ_min(C) at n = 16-0.4λ_min(C) at n = 32-0.14λ_min(C) at n = 640.016λ_min(C) at n = 1280.051λ_min(C) at n = 2560.053left of the line the repair costs stepsright of it, the count stops counting n

A preconditioner that changes sign

Strang's circulant preconditioner takes Toeplitz conjugate gradients from 179 steps to 10 at n = 256. At n = 64 on the same family it takes 66 steps to 109 — worse than doing nothing. Between those rows the preconditioner's smallest eigenvalue crosses zero, and nothing in the published account of the method mentions that it can be negative.

structure · preconditioning 10²020406080100120140160size niterationsno preconditionerwrapped (Strang)averaged (T. Chan)both are circulant approximations‖C − T‖/‖T‖, averaged0.13‖C − T‖/‖T‖, wrapped0.25smallest eigenvalue, wrapped, n = 16-0.65one of them is positive definiteand it is the one that is nearer

The circulant that cannot be indefinite

The previous essay found a preconditioner taking 117 steps against an unpreconditioned 59, because its smallest eigenvalue was −0.173. Average the two diagonals instead of choosing between them and the count is 7, 8, 9, 10, 10 across a factor of sixteen in size.

structure · toeplitz

Named alongside it

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

Circulant preconditionerClustered spectrumConjugate gradientsPreconditioningToeplitz matrixCirculant matrixCondition numberConvergence rateDiscrete fourier transformFrobenius norm

All concepts