Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Matrix structure — where it appears

A property of a matrix that a general algorithm cannot see and a specialised one can exploit. Sparsity, a constant diagonal, a low-rank off-diagonal block and a symmetric spectrum are four different kinds, and none of them is visible in a norm.

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

024681012141610⁻¹1index kλthe transformthe eigensolverC = F* Λ F is a factorisationworst relative disagreement2.6·10⁻¹⁵‖Cx − b‖/‖b‖ from the transform solve4.7·10⁻¹⁶imaginary part of a real spectrum1.2·10⁻¹⁶n = 16, and the whole matrix is 16 numberseigenvectors known in advance

The matrix that is one row

A circulant of size 16 is sixteen numbers, has no zero entry anywhere, and hands over its entire spectrum in closed form — the discrete Fourier transform of its first column, exactly. An eigensolver spends a sweep of Jacobi rotations over 256 entries arriving at the same answer, and agrees to 1.2·10⁻¹⁵.

structure · circulant 545545545455554545545545545454555555454545545545545455554545545545rows and columns, in the order the points arrivedark: kept dense · light: two thin factors, rank printedthe strong partitionblocks112kept dense46largest rank5numbers stored2.7·10⁴‖A − A_H‖ ⁄ ‖A‖3.4·10⁻¹⁰the picture is decidedbefore a number is read

Which pairs are allowed to be small

A hierarchical representation is a partition of the matrix into blocks, and the rule that produces it reads four numbers per pair of index clusters and not one entry of the matrix. On a 256-square it yields 112 blocks, 66 of them stored as two thin factors, none of rank above five.

hierarchy · admissibility

Named alongside it

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

AdmissibilityBlock methodsCirculant matrixCluster treeCondition numberDiscrete fourier transformEigenvaluesFactorisationFast fourier transformHierarchical matrixKernel matrixOff diagonal rank

All concepts