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 4 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⁴relative compression error3.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 56789100108216324432log₂ nstored per unknowndenseweak: every off-diagonal blockstrong: only the admissible onesa constant per doublingstrong, n = 5126.8·10⁴weak, n = 5126.1·10⁴dense, n = 5122.6·10⁵per doubling26relative compression error3.8·10⁻¹⁰the dense line doublesand the other two add a constant

The offset that moved the slope

The accuracy is supposed to lift a storage curve and leave its growth alone. Measured at seven tolerances, the strong partition adds 10.9 numbers per unknown per doubling at two digits and 36.5 at twelve — the growth rate more than triples, so ten decades of accuracy cost 33 per cent more storage at 64 unknowns and 118 per cent at 512.

hierarchy · Storage growth n = 512, leaf 16blocks, tightest to loosest592and at the loosest94mean rank, tightest3.3and at the loosest8.9052104156208260the separation constantstored per unknown0.20.30.40.50.951.4stored per unknownmean rank, compressed blocksboth curves move togetherwhich is what the other two knobs never do

A geometry setting that is a second accuracy

The tolerance raises every rank and moves no block; the leaf moves every block and no rank. The constant that decides how far apart two clusters must be before their block may be compressed moves both — 592 blocks at mean rank 3.25 at one end and 94 at mean rank 8.94 at the other — and the storage falls the whole way while the error against the dense matrix rises by a factor of 3.5, at a tolerance that never changed. It has no best setting, and it is not a third knob on the storage.

hierarchy · Storage growth

Named alongside it

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

AdmissibilityCluster treeHierarchical matrixNumerical rankOff-diagonal rankAsymptotic analysisBlock methodsLow-rank approximationToleranceTruncationBackward errorFlop count

All concepts