Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Weak admissibility — where it appears

The rule that compresses every off-diagonal block of a partition without asking whether its clusters are separated. It gives far fewer blocks than a geometric test and a rank that grows slowly with the size, and it is the format almost every hierarchical solver actually uses.

Named by 2 essays across one field — 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 567891003691215log₂ nlargest rank in the partitionweak: touching pairs compressedstrong: touching pairs refusedthe test bounds a rank and costs storagestrong, blocks250weak, blocks94strong, numbers6.8·10⁴weak, numbers6.1·10⁴strong ⁄ weak1.1the better partitionis the more expensive one

The test that costs what it saves

The partition that refuses to compress a touching pair keeps every rank at five while the other lets them climb from nine to thirteen. It also stores more numbers at every size measured — 67,968 against 61,440 at n = 512 — and which of those two facts matters is a question about how large the problem is going to get.

hierarchy · admissibility

Named alongside it

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

AdmissibilityBlock methodsCluster treeHierarchical matrixOff diagonal rankAsymptotic analysisFlop countKernel matrixLower boundMatrix structureNumerical rankSubdivision

All concepts