Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Subdivision — where it appears

Splitting a cluster or a box in half and recursing on the pieces. It is how an admissibility test handles a pair it refuses, and how a branch-and-bound search handles a box its verdict cannot decide.

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

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 grey: proved empty · filled: proved to contain exactly one roota covered squareboxes proved empty42boxes proved unique2undecided0operator evaluations87every rectangle carries a proofand the two crosshairs are where the roots are

Where the box is cut

A branch-and-bound with an interval operator settles a whole square — two roots proved unique, forty-two regions proved empty, nothing left undecided, in 87 evaluations. Move the roots so one lands on the first bisection and it proves nothing at all, at any depth. Cutting at 0.485 instead of 0.5 finds both, in a quarter of the work.

arithmetic · interval

Named alongside it

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

AdmissibilityBisectionBlock methodsBranch and boundCluster treeExact ground truthExistence and uniquenessHierarchical matrixInterval arithmeticKernel matrixKrawczyk operatorMatrix structure

All concepts