Numerical Linear Algebra
where the algebra stops being the arithmetic
Neither sparse nor dense

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.
37 min read 27 figures Measured, not assertedWhose fault is itAssertions that reject

Worth reading first: Which pairs are allowed to be small · A block nobody can call sparse · The same arithmetic at a different price.

The previous essay put a test in the partition and did not say what it was worth. This one measures both sides of it, and the two sides point in opposite directions.

The largest rank in each partition, and what refusing to compress a touching pair costsThe strong rule's worst block is rank 5 at every size — one number across a factor of eight — because it never compresses a pair of clusters that touch. The weak rule compresses them and its worst rank climbs 9, 10, 12, 13, at about one per doubling, which is the touching block's logarithm arriving inside a whole partition. That is what the test buys. What it costs is on the badge: at every size measured, the finer partition stores MORE — 67,968 numbers against 61,440 at n = 512 — because it pays in blocks what it saves in rank, and the blocks near the diagonal are dense. The bounded rank is an asymptotic argument and the sizes here are not asymptotic.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
Fig. 1 The largest rank in each partition against the size of the matrix. One line is horizontal and the other climbs; the badge is what each of them costs.

The two partitions, side by side

Same matrix, same points, same accuracy, same leaf size, at four sizes:

n blocks (strong) worst rank numbers blocks (weak) worst rank numbers
64 16 5 3,456 10 9 3,200
128 46 5 10,112 22 10 8,960
256 112 5 27,008 46 12 24,064
512 250 5 67,968 94 13 61,440

Read the rank columns and the test is obviously worth having: five at every size against a number that climbs by one per doubling. Read the storage columns and it is obviously not: the partition with the bounded rank costs more at every size, by between eight and thirteen per cent.

Both readings are correct and the second is the one nobody expects, which is why it is the finding rather than a footnote.

Where the extra storage goes

The strong partition has two and a half times as many blocks and they are smaller. That is the whole of it, and it costs in two places.

The dense fringe. Refusing to compress a touching pair means subdividing it, and the subdivision terminates on leaves that are stored entry by entry. At n = 512 the strong partition keeps 106 dense blocks against the weak one’s 32 — because every touching pair, at every level, eventually becomes four leaf-sized dense squares. Those are small individually and there are a great many of them.

The rank floor. A compressed block never has rank zero. A 32 × 32 block at rank 5 stores 320 numbers against 1,024 entries, which is a saving of a factor of three; a 256 × 128 block at rank 12 stores 9,216 against 32,768, a factor of three and a half. The saving from a low-rank block is 2k/n in the block’s own size, so small blocks compress badly, and a partition made of small blocks is a partition that compresses badly even when each of its ranks is tiny.

So the test trades a rank that grows slowly for a block count that grows quickly, and at these sizes the block count is winning.

A 256 × 256 kernel matrix partitioned by the strong rule, with each compressed block's rank112 blocks: 46 kept dense and 66 stored as two thin factors, whose ranks run from 4 to 5. The rule decides one thing — whether a pair of index clusters may be compressed — and it decides it from four numbers about where those clusters sit, before any entry of the matrix is read. The strong rule refuses any pair whose clusters touch, and subdivides instead, so the diagonal is fringed with small dense blocks and no rank on the picture exceeds 5. The whole thing stores 27,008 numbers against 65,536 entries, and reproduces the matrix to 3.41·10⁻¹⁰.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
Fig. 2 Where the extra blocks are: the diagonal fringed with dense squares, each of them a pair the test refused and then subdivided until the pieces were leaf-sized.
A 256 × 256 kernel matrix partitioned by the weak rule, with each compressed block's rank46 blocks: 16 kept dense and 30 stored as two thin factors, whose ranks run from 8 to 12. The rule decides one thing — whether a pair of index clusters may be compressed — and it decides it from four numbers about where those clusters sit, before any entry of the matrix is read. The weak rule compresses every off-diagonal block there is, including the two touching halves at the top level, whose rank is the largest number on the picture and is the one that climbs as the matrix grows. The whole thing stores 24,064 numbers against 65,536 entries, and reproduces the matrix to 1.08·10⁻⁹.121210109988889988881010998888998888rows and columns, in the order the points arrivedark: kept dense · light: two thin factors, rank printedthe weak partitionblocks46kept dense16largest rank12numbers stored2.4·10⁴‖A − A_H‖ ⁄ ‖A‖1.1·10⁻⁹the picture is decidedbefore a number is read
Fig. 3 And the partition that asks nothing, whose diagonal fringe is sixteen squares and whose two largest blocks carry the rank that climbs.

When the other reading wins

The asymptotic argument is not wrong, it has simply not arrived yet, and it is worth saying exactly what it needs.

The weak partition’s cost is O(n log²n) rather than O(n log n), because its rank carries a log of its own. At n = 512 with a leaf of 16 there are five levels, so the extra log is a factor of five — and a factor of five inside an asymptotic constant is invisible against a twelve per cent difference in the measured totals. The crossover is where the weak partition’s rank has grown enough to overwhelm the strong one’s block count, and extrapolating the two columns puts it far past any size this site can compute.

That is an honest place to stop, and it is worth noticing what the honest stopping point implies. For a problem of ten thousand unknowns the simpler partition is very likely still cheaper. For one of ten million it is very likely not. Nobody in this field is ever choosing between the two on a 512-square, and a measurement on a 512-square cannot settle the choice for them — what it can do is establish the shape of the trade, which is the useful thing, and refuse the reading that one of the two dominates.

Numbers stored per unknown, against the size of the matrix, at 10⁻⁸The dense matrix stores n numbers per unknown, which is the straight line through the origin and doubles whenever n does. The hierarchical representations store 54, 79, 106, 133 and 50, 70, 94, 120, adding about 26 per doubling — a constant per doubling is a logarithm, and it is the whole claim. At n = 512 that is 26 and 23 per cent of the dense matrix, and the share falls at every size. The exponent between consecutive sizes is 1.55, 1.42, 1.33, falling towards one and never arriving, which is what a logarithm looks like from inside.56789100108216324432log₂ nnumbers stored 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 doubling26‖A − A_H‖ ⁄ ‖A‖3.8·10⁻¹⁰the dense line doublesand the other two add a constant
Fig. 4 The same two totals as a curve rather than a table, with the dense matrix on the same axes for scale. Both hierarchical lines add a constant per doubling; the gap between them does not close.

The rank is not only a storage cost

The table above prices a rank in numbers stored, which under-counts it, and the under-counting is why the asymptotic argument is worth taking seriously earlier than the storage says.

Every operation in a formatted arithmetic costs more than linearly in the rank. Multiplying two rank-k blocks costs O(k²n); adding two of them and recompressing costs O(k²n) for the orthogonalisation and O(k³) for the small decomposition; a formatted factorisation does a great many of both. So a rank of 13 against a rank of 5 is a factor of 2.6 in storage and a factor of nearly 7 in the arithmetic of every operation that touches those blocks.

A representation that is only ever multiplied by vectors does not care: a matrix–vector product is linear in the rank, and the storage table is the whole story. A representation that is going to be inverted, or squared, or used to build a formatted factorisation, cares a great deal.

Which is the same sentence the previous essay ends on and the one this whole field keeps arriving at: a format is chosen for what is going to be done to it, and a comparison that prices only storage has priced the easiest thing anybody does with it.

The singular values of a sum of two rank-4 blocks, and the 4 a truncation has to discardA rank-4 block times a vector is a rank-4 block times a vector. A rank-4 block times a rank-4 block is a rank-4 block. A rank-4 block PLUS a rank-4 block is a rank-8 block, exactly, and the 8 bars here are why: the sum of two 4-dimensional spaces is generally 8-dimensional, and none of the 8 singular values is small. Truncating back to 4 costs 61.9 per cent of the block. Below the 8th the values are the unit roundoff, which is the check that the doubling is exact rather than approximate. Every product, every factorisation and every Schur complement inside this format is a chain of these, and there is nothing else to do: without the truncation the ranks double at every level and the format is dense by the bottom.σ ⁄ σ₁ of the sum, 64 × 64σ1, kept1σ2, kept0.922σ3, kept0.812σ4, kept0.785σ5, discarded0.778σ6, discarded0.758σ7, discarded0.658σ8, discarded0.571σ92.63·10⁻¹⁶σ102.3·10⁻¹⁶the operation that is not closedrank of each term4rank of the sum8truncated back to4cost of the truncation0.62the best there is0.62two planesmake a four-space
Fig. 5 Why a rank costs more than its storage, from three essays ahead: the sum of two rank-k blocks is a rank-2k block, and the truncation that brings it back is where the arithmetic goes.
‖A − LLᵀ‖ ⁄ ‖A‖ for a Cholesky computed in the format, against how many truncations it performedThe recursion is the textbook one and every step stays in the format: the off-diagonal factor is exact, because a triangular solve against one factor of a rank-k block leaves a rank-k block, and the Schur complement is a rank-k addition to a hierarchical matrix, which is the only approximate step there is. So the number of truncations is a count — one per admissible block in the subtree being updated, at every level — and it runs from 0 at a leaf of 128 to 98 at a leaf of 8. The residual goes from 2.119·10⁻¹⁰ to 1.138·10⁻⁹, and all of that movement is the representation, whose own error is the upper curve and moves by the same factor: the ratio between them is 1.00, 0.93, 0.92, 0.91, 0.81, never above one. A hundred approximate operations contributed nothing measurable to the answer.02040608010010⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸truncations performed by the factorisationrelative errorthe representation's own error‖A − LLᵀ‖ ⁄ ‖A‖no decomposition without its residualresidual, 0 truncations2.1·10⁻¹⁰residual, 98 truncations1.1·10⁻⁹representation, deepest1.4·10⁻⁹residual ⁄ representation0.81levels, deepest5a hundred approximate stepsand an exact-looking factorisation
Fig. 6 And what a formatted factorisation does with those operations, from the same essay: ninety-eight of them, in one Cholesky.

What each partition is actually made of

The block counts in the table are easier to read once the two structures are named, and naming them also says why one of them has a solve and the other does not.

The weak partition is a recursion on the diagonal. At the top level there are exactly three objects: the two off-diagonal blocks, and the two diagonal blocks which are the same problem one level down. At level ℓ it contributes 2·2^ℓ compressed blocks, all of them the same size, and it terminates in 2^L dense leaves. Every compressed block is the full off-diagonal quadrant of some diagonal block. That regularity is what a formatted solve needs — at each level the off-diagonal part is one low-rank correction to a block-diagonal matrix, which is a Woodbury update — and it is why almost every code that inverts a hierarchical matrix uses this partition.

The strong partition is a recursion on pairs. It starts with the root against itself, and every pair that fails the test spawns four pairs of children. The pairs that pass become blocks; the ones that fail and have no children become dense blocks. What comes out has blocks of several sizes at each level, arranged in a band whose width is set by η, and there is no level at which the off-diagonal part is a single low-rank object.

So the extra 156 blocks at n = 512 are not overhead in the bookkeeping sense. They are a genuinely finer description of the matrix, each piece of which is genuinely cheaper than the piece it replaced — and the sum of them is larger, because a description made of many small accurate pieces is not automatically smaller than one made of few large approximate ones.

That is a sentence worth carrying out of this field. Refining a decomposition improves every piece of it and need not improve the total, and which way it goes is arithmetic rather than principle.

A 256 × 256 kernel matrix partitioned by the weak rule, with each compressed block's rank46 blocks: 16 kept dense and 30 stored as two thin factors, whose ranks run from 8 to 12. The rule decides one thing — whether a pair of index clusters may be compressed — and it decides it from four numbers about where those clusters sit, before any entry of the matrix is read. The weak rule compresses every off-diagonal block there is, including the two touching halves at the top level, whose rank is the largest number on the picture and is the one that climbs as the matrix grows. The whole thing stores 24,064 numbers against 65,536 entries, and reproduces the matrix to 1.08·10⁻⁹.121210109988889988881010998888998888rows and columns, in the order the points arrivedark: kept dense · light: two thin factors, rank printedthe weak partitionblocks46kept dense16largest rank12numbers stored2.4·10⁴‖A − A_H‖ ⁄ ‖A‖1.1·10⁻⁹the picture is decidedbefore a number is read
Fig. 7 The recursion on the diagonal, drawn. Three objects at the top level, and the two dark squares are the same picture one level down.
A 256 × 256 kernel matrix partitioned by the strong rule, with each compressed block's rank112 blocks: 46 kept dense and 66 stored as two thin factors, whose ranks run from 4 to 5. The rule decides one thing — whether a pair of index clusters may be compressed — and it decides it from four numbers about where those clusters sit, before any entry of the matrix is read. The strong rule refuses any pair whose clusters touch, and subdivides instead, so the diagonal is fringed with small dense blocks and no rank on the picture exceeds 5. The whole thing stores 27,008 numbers against 65,536 entries, and reproduces the matrix to 3.41·10⁻¹⁰.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
Fig. 8 And the recursion on pairs, whose band widens away from the diagonal because a large pair may be far apart and still admissible.

The rank that climbs, read carefully

The weak partition’s rank column — 9, 10, 12, 13 at eight digits, 12, 14, 16, 18 at twelve — is the only quantity in this field that grows with the problem, and it is worth being precise about what kind of growth it is.

It is not the whole partition’s rank. It is the largest rank anywhere in the partition, and the block carrying it is always the same one: the pair of top-level halves, which touch. Every other block in the weak partition is admissible in the strong sense and has a rank of five, exactly as the strong partition’s blocks do. The mean rank at n = 256 is 8.8 against a maximum of 12, and the distribution is two large numbers and twenty-eight small ones.

So the weak partition is not a worse partition everywhere. It is the strong partition plus a handful of inadmissible blocks compressed anyway, and the handful is small — two per level — which is why the total storage difference is twelve per cent rather than a factor.

That also says where the asymptotic argument bites. The number of inadmissible blocks the weak partition compresses is 2·(levels), and each of their ranks grows like the log of its own size. So the extra cost is a sum over levels of (log of the level’s size) × (the level’s size), which is where the second logarithm comes from, and it is a genuinely different asymptotic class from the strong partition’s. Being a different asymptotic class and being twelve per cent apart at n = 512 are both true, and only the second is a measurement.

The rank of an admissible block and of a touching one, against how finely they are sampledBoth blocks are of the kernel 1/r; both are 32, 64, 128, 256 points a side; both are truncated at 10⁻⁸. The admissible pair — [0, 1] against [2, 3] — needs 5, 5, 5, 5 columns, which is one number. The touching pair — [0, 1] against [1, 2] — needs 9, 11, 12, 13, climbing by about one per doubling, which is a logarithm. Neither of them grows like the block, and only one of them stops. That difference is what the admissibility test in a partition is buying, and it is why the touching pair is kept dense rather than compressed at all.45678903691215log₂ of the points a sidecolumns above 10⁻⁸two intervals that touchtwo that do notthe measurement that is a null resultadmissible, n = 325admissible, n = 2565touching, n = 329touching, n = 25613stored ⁄ dense at largest0.039the rank belongs to the geometryand not to the sampling
Fig. 9 The block responsible, isolated, from three essays back: the touching pair whose rank climbs 9, 11, 12, 13 while the admissible one sits at five.
Numbers stored per unknown, against the size of the matrix, at 10⁻¹²The dense matrix stores n numbers per unknown, which is the straight line through the origin and doubles whenever n does. The hierarchical representations store 60, 94, 131, 170 and 60, 88, 120, 156, adding about 37 per doubling — a constant per doubling is a logarithm, and it is the whole claim. At n = 512 that is 33 and 30 per cent of the dense matrix, and the share falls at every size. The exponent between consecutive sizes is 1.65, 1.48, 1.37, falling towards one and never arriving, which is what a logarithm looks like from inside.56789100108216324432log₂ nnumbers stored per unknowndenseweak: every off-diagonal blockstrong: only the admissible onesa constant per doublingstrong, n = 5128.7·10⁴weak, n = 5128·10⁴dense, n = 5122.6·10⁵per doubling37‖A − A_H‖ ⁄ ‖A‖7.4·10⁻¹⁴the dense line doublesand the other two add a constant
Fig. 10 And the two totals at twelve digits, where the weak partition’s extra logarithm is doing the most work it does anywhere on this site and the lines still have not crossed.

The comparison this site has already made twice

The shape here — a finer decomposition with better local properties and worse totals — is one this collection has met in two other fields, and reading the three together is more useful than any of them alone.

the-same-arithmetic-at-a-different-price is the cost field’s version: a blocked factorisation and an unblocked one perform the same multiplications in a different order, the flop counts are identical to the last operation, and the memory traffic differs by a factor that decides which is usable.

a-threshold-between-fill-and-growth is the sparsity field’s: a threshold pivoting rule trades fill against stability, the two are measured in different units, and there is no setting at which both are best.

The common structure is a trade between two resources that cannot be added up. Here it is block count against rank; there it is traffic against operations, and fill against growth. In all three the mistake to avoid is the same one — picking whichever resource the figure happens to plot — and the defence is the same: put both on the badge.

A 6.25-bit block format against 8-bit E4M3, read two waysFour curves of relative error against the spread of the data. Two, for the block format, rise steeply when read as a median and gently when read as a norm; the other two are nearly flat.048121610⁻²10⁻¹1octaves of spread within a blockrelative errorblock, medianblock, 2-normE4M3, medianE4M3, 2-normthe same data, two readingsblock format, bits a value6.3norm across 16 octaves1.8median across 16 octaves62entries deleted at the wide end383640 values, blocks of 32a norm is dominated by what a block format keeps
Fig. 11 The cost field’s version, from the essay that measured it: two orders of the same arithmetic, one count identical and the other not.
Fill against growth as the pivot threshold moves, on the 6×6 gridTwo curves against the pivot threshold on a logarithmic horizontal axis. One falls steeply from left to right; the other rises gently. A vertical line marks the value libraries default to.10⁻³10⁻²10⁻¹1110¹10²10³10⁴pivot threshold τgrowth factor · entries in L+U, ÷ entries in Agrowthfillthe library default‖PA − LU‖/‖A‖ at τ = 0.12.9·10⁻¹⁶growth at τ = 0.138entries in L+U at τ = 0.1372one knob, two measurements, opposite directionsand the default is most of both
Fig. 12 And the sparsity field’s, where the two resources traded are fill and growth and neither is the other’s units.

What the accuracy does to the comparison

The tolerance is a knob on both partitions and it moves them together, which is worth checking rather than assuming.

At 10⁻² the strong partition’s ranks are 2 at every size and the weak one’s are 3 and 4, and both are storing mostly their dense fringe — so the ratio between them is set by the fringe, which is the strong partition’s weak point. It stores 17,216 numbers against 10,752 at n = 256: a factor of 1.60, and the gap is at its widest.

At 10⁻¹² the ranks are 7 against 12, 14, 16, 18 — the weak partition’s climbing three times as fast as before, because a tighter tolerance samples further down a spectrum whose tail is exactly what the touching pairs have. The totals are 33,536 against 30,720: a factor of 1.09.

ε strong ⁄ weak at n = 256 strong ⁄ weak at n = 512
10⁻² 1.60 1.55
10⁻⁸ 1.12 1.11
10⁻¹² 1.09 1.09

The direction is the useful part. Tightening the accuracy favours the test, because a tighter accuracy makes ranks the dominant cost and ranks are what the test controls. A code that needs three digits should use the simpler partition; a code that needs twelve has a reason to pay for the finer one, at any size.

That is a cleaner rule than the asymptotic one and it is available now rather than at ten million unknowns, which is the sort of thing a measurement is for. It is also, honestly, a rule about a narrowing gap rather than a crossing one: the ratio goes 1.60, 1.12, 1.09 and does not reach one at any tolerance the arithmetic supports. What tightening the accuracy buys the test is that its cost stops mattering, not that it starts paying.

The largest rank in each partition, and what refusing to compress a touching pair costsThe strong rule's worst block is rank 7 at every size — one number across a factor of eight — because it never compresses a pair of clusters that touch. The weak rule compresses them and its worst rank climbs 12, 14, 16, 18, at about one per doubling, which is the touching block's logarithm arriving inside a whole partition. That is what the test buys. What it costs is on the badge: at every size measured, the finer partition stores MORE — 86,784 numbers against 79,872 at n = 512 — because it pays in blocks what it saves in rank, and the blocks near the diagonal are dense. The bounded rank is an asymptotic argument and the sizes here are not asymptotic.5678910048121620log₂ nlargest rank in the partitionweak: touching pairs compressedstrong: touching pairs refusedthe test bounds a rank and costs storagestrong, blocks250weak, blocks94strong, numbers8.7·10⁴weak, numbers8·10⁴strong ⁄ weak1.1the better partitionis the more expensive one
Fig. 13 At twelve digits, where both sets of ranks have grown and the one the test controls has grown less.
The largest rank in each partition, and what refusing to compress a touching pair costsThe strong rule's worst block is rank 2 at every size — one number across a factor of eight — because it never compresses a pair of clusters that touch. The weak rule compresses them and its worst rank climbs 3, 3, 4, 4, at about one per doubling, which is the touching block's logarithm arriving inside a whole partition. That is what the test buys. What it costs is on the badge: at every size measured, the finer partition stores MORE — 39,744 numbers against 25,600 at n = 512 — because it pays in blocks what it saves in rank, and the blocks near the diagonal are dense. The bounded rank is an asymptotic argument and the sizes here are not asymptotic.567891002468log₂ nlargest rank in the partitionweak: touching pairs compressedstrong: touching pairs refusedthe test bounds a rank and costs storagestrong, blocks250weak, blocks94strong, numbers4·10⁴weak, numbers2.6·10⁴strong ⁄ weak1.6the better partitionis the more expensive one
Fig. 14 And at two, where both partitions are mostly storing their dense diagonal and the ranks are almost beside the point.

The other resource, which neither column prices

There is a third quantity in this comparison and neither of the two tables has it, so it is worth putting on the record before the verdict.

Both partitions reproduce the matrix. The strong one reaches 3.4·10⁻¹⁰ at n = 256 and the weak one 1.1·10⁻⁹, at the same ε — a factor of three, in the strong partition’s favour, at every size measured.

That is not a coincidence and it is not free either. The reason the strong partition is more accurate is the same reason it is more expensive: it keeps the touching pairs dense, so those blocks are exact, and they are the blocks with the largest entries in the whole matrix. The weak partition compresses them, at a rank chosen by the same ε as everything else, and their error is what dominates the total.

So a fair comparison would run the weak partition at a tighter ε and see what its storage becomes, which is a third table nobody wants. What can be said from the two that exist is that the twelve per cent in the storage column is bought with a factor of three in the error column, and a reader who wanted the two partitions equalised on accuracy would find the gap smaller still.

This is the standing difficulty with comparing two methods that each have a knob: there is no comparison, only a surface, and any table is a slice through it. This collection’s field about four knobs and one floor is the long version of that observation, and the shortest useful form of it is that a comparison is only honest if it says which slice it took.

The accuracy asked for, against the accuracy obtained, for two kernels on one partitionε is applied to each block against that block's own largest singular value; the error is then reported against the whole matrix's norm. The two are not the same number and the dashed diagonal is where they would be. For 1/r the obtained error is 29 times smaller than the tolerance asked for; for log r on the identical partition it is 13 times smaller. Both curves are straight and parallel to the diagonal, so the knob does what a knob should — a decade in buys a decade out — and neither of them sits on it. The factor is how much of the matrix's mass lives off the diagonal, which is a property of the kernel; it is not the number of blocks, which is 112 and would put the curves on the other side of the diagonal.10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³ε asked for, per block‖A − A_H‖ ⁄ ‖A‖ obtainedasked = obtainedlog r1 ⁄ rtwo numbers, not one1/r, obtained at 10⁻⁸3.4·10⁻¹⁰log r, obtained at 10⁻⁸7.8·10⁻¹⁰1/r, obtained ⁄ asked0.034log r, obtained ⁄ asked0.078blocks in the partition112the tolerance is per blockand the error is per matrix
Fig. 15 Where the accuracy of an assembled representation comes from, from the essay that measures it: a per-block tolerance and a whole-matrix error are two numbers, and the factor between them is set by where the matrix keeps its mass.

The refusal

The claim under test is the one the rank column invites: that bounding the rank of every block makes the representation cheaper.

It is not marked false. It is marked asymptotic, which is this site’s verdict for a claim that is true in the limit and not true at any size anybody has, and the distinction matters because the wrong verdict here would be as misleading as no verdict at all.

The refusal is fed the storage figures at 256 unknowns: the assertion that the strong partition stores fewer numbers than the weak one is handed 27,008 and 24,064, and it fails. It would fail at every one of the four sizes measured. What it does not do is establish that the asymptotic reading is wrong — nothing here can — and the verdict says so.

The largest rank in each partition, and what refusing to compress a touching pair costsThe strong rule's worst block is rank 5 at every size — one number across a factor of eight — because it never compresses a pair of clusters that touch. The weak rule compresses them and its worst rank climbs 9, 10, 12, 13, at about one per doubling, which is the touching block's logarithm arriving inside a whole partition. That is what the test buys. What it costs is on the badge: at every size measured, the finer partition stores MORE — 67,968 numbers against 61,440 at n = 512 — because it pays in blocks what it saves in rank, and the blocks near the diagonal are dense. The bounded rank is an asymptotic argument and the sizes here are not asymptotic.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
Fig. 16 The measurement the verdict rests on, at the accuracy the field uses throughout, with both resources on the badge.
What one symmetric permutation does to the storage, on a matrix it does not changeThe same 256 × 256 matrix, its rows and columns renumbered by one permutation and its columns by the same one. The condition number is 24.3948 either way, to eight digits; the Frobenius norm is 6139.964 either way, to twelve. Nothing a norm can see has moved. Clustered, the partition stores 27,008 numbers. Shuffled, the admissibility test finds no admissible pair anywhere — every cluster of a shuffled numbering spans the whole interval, so every q is infinite — and the format degenerates to dense storage exactly. The rule with no test to fail does worse than that: it compresses every off-diagonal block regardless, gets ranks up to 119 out of 128, and stores 118,208 numbers — 1.80 times the matrix it was compressing. A rank-119 factorisation of a 128-column block is a more expensive way to write down the block than the block.numbers stored, 256 × 256clustered, strong27,008clustered, weak24,064the dense matrix65,536shuffled, strong65,536shuffled, weak118,208the same matrix, twiceκ, clustered24κ, shuffled24‖A‖_F, clustered6140‖A‖_F, shuffled6140shuffled weak ⁄ dense1.8the compressibility is in the numberingand the numbering is not in the matrix
Fig. 17 And the comparison the next essay makes, where the difference between two ways of storing one matrix is not twelve per cent but a factor of four.
Multiplications in a hierarchical solve and in a dense factorisation, and where they crossBoth counted rather than estimated: the recursion carries a counter and reports what it actually did. The dense factorisation is n³/3 and rises at exactly three per doubling. The hierarchical solve rises at 2.13, 1.93, 1.74 — falling, because the cost is n log²n and its exponent is on its way to one. The two cross between n = 64 and n = 128: below it the format is the more expensive way to solve the system, at 1.48 times the dense count, and at n = 512 it is 6.2 times cheaper. Every point returns an answer at a backward error of about 1.4·10⁻¹⁰, so the comparison is between two ways of getting the same thing.567891010⁴10⁵10⁶10⁷10⁸10⁹log₂ nmultiplicationsdense factorisation, n³⁄3the recursion, countedwhere the format starts payingratio at n = 641.5ratio at n = 5120.16exponent, first doubling2.1exponent, last doubling1.7backward error1.4·10⁻¹⁰cheaper is a sizenot a property
Fig. 18 And the operation the weak partition exists for, which the storage table does not price at all.

The trade at its two ends

Numbers stored per unknown, against the size of the matrix, at 10⁻¹⁰The dense matrix stores n numbers per unknown, which is the straight line through the origin and doubles whenever n does. The hierarchical representations store 57, 87, 118, 151 and 56, 80, 108, 140, adding about 31 per doubling — a constant per doubling is a logarithm, and it is the whole claim. At n = 512 that is 30 and 27 per cent of the dense matrix, and the share falls at every size. The exponent between consecutive sizes is 1.60, 1.45, 1.35, falling towards one and never arriving, which is what a logarithm looks like from inside.56789100108216324432log₂ nnumbers stored per unknowndenseweak: every off-diagonal blockstrong: only the admissible onesa constant per doublingstrong, n = 5127.7·10⁴weak, n = 5127.2·10⁴dense, n = 5122.6·10⁵per doubling31‖A − A_H‖ ⁄ ‖A‖4.9·10⁻¹²the dense line doublesand the other two add a constant
Fig. 19 The two totals at ten digits, where the ranks are doing most of the work and the gap between the rules is at its narrowest.
Numbers stored per unknown, against the size of the matrix, at 10⁻⁶The dense matrix stores n numbers per unknown, which is the straight line through the origin and doubles whenever n does. The hierarchical representations store 51, 72, 93, 114 and 42, 58, 76, 96, adding about 21 per doubling — a constant per doubling is a logarithm, and it is the whole claim. At n = 512 that is 22 and 19 per cent of the dense matrix, and the share falls at every size. The exponent between consecutive sizes is 1.49, 1.38, 1.30, falling towards one and never arriving, which is what a logarithm looks like from inside.56789100108216324432log₂ nnumbers stored per unknowndenseweak: every off-diagonal blockstrong: only the admissible onesa constant per doublingstrong, n = 5125.9·10⁴weak, n = 5124.9·10⁴dense, n = 5122.6·10⁵per doubling21‖A − A_H‖ ⁄ ‖A‖4.1·10⁻⁸the dense line doublesand the other two add a constant
Fig. 20 And at six, where the dense fringe is a larger share and the gap has opened again.
The largest rank in each partition, and what refusing to compress a touching pair costsThe strong rule's worst block is rank 6 at every size — one number across a factor of eight — because it never compresses a pair of clusters that touch. The weak rule compresses them and its worst rank climbs 11, 12, 14, 16, at about one per doubling, which is the touching block's logarithm arriving inside a whole partition. That is what the test buys. What it costs is on the badge: at every size measured, the finer partition stores MORE — 77,376 numbers against 71,680 at n = 512 — because it pays in blocks what it saves in rank, and the blocks near the diagonal are dense. The bounded rank is an asymptotic argument and the sizes here are not asymptotic.56789100369121518log₂ nlargest rank in the partitionweak: touching pairs compressedstrong: touching pairs refusedthe test bounds a rank and costs storagestrong, blocks250weak, blocks94strong, numbers7.7·10⁴weak, numbers7.2·10⁴strong ⁄ weak1.1the better partitionis the more expensive one
Fig. 21 The ranks at ten digits: one row flat at seven, the other climbing from twelve to eighteen.
The largest rank in each partition, and what refusing to compress a touching pair costsThe strong rule's worst block is rank 4 at every size — one number across a factor of eight — because it never compresses a pair of clusters that touch. The weak rule compresses them and its worst rank climbs 7, 8, 9, 10, at about one per doubling, which is the touching block's logarithm arriving inside a whole partition. That is what the test buys. What it costs is on the badge: at every size measured, the finer partition stores MORE — 58,560 numbers against 49,152 at n = 512 — because it pays in blocks what it saves in rank, and the blocks near the diagonal are dense. The bounded rank is an asymptotic argument and the sizes here are not asymptotic.567891002468101214log₂ nlargest rank in the partitionweak: touching pairs compressedstrong: touching pairs refusedthe test bounds a rank and costs storagestrong, blocks250weak, blocks94strong, numbers5.9·10⁴weak, numbers4.9·10⁴strong ⁄ weak1.2the better partitionis the more expensive one
Fig. 22 And at six, where both rows are lower and the shapes are the same, which is what makes the shapes the finding rather than the numbers.
The rank of an admissible block and of a touching one, against how finely they are sampledBoth blocks are of the kernel 1/r; both are 32, 64, 128, 256 points a side; both are truncated at 10⁻¹⁰. The admissible pair — [0, 1] against [2, 3] — needs 6, 6, 6, 6 columns, which is one number. The touching pair — [0, 1] against [1, 2] — needs 11, 13, 14, 16, climbing by about one per doubling, which is a logarithm. Neither of them grows like the block, and only one of them stops. That difference is what the admissibility test in a partition is buying, and it is why the touching pair is kept dense rather than compressed at all.4567890369121518log₂ of the points a sidecolumns above 10⁻¹⁰two intervals that touchtwo that do notthe measurement that is a null resultadmissible, n = 326admissible, n = 2566touching, n = 3211touching, n = 25616stored ⁄ dense at largest0.047the rank belongs to the geometryand not to the sampling
Fig. 23 The single block responsible for the climbing row, isolated, from three essays back.
Multiplications in a hierarchical solve and in a dense factorisation, and where they crossBoth counted rather than estimated: the recursion carries a counter and reports what it actually did. The dense factorisation is n³/3 and rises at exactly three per doubling. The hierarchical solve rises at 2.13, 1.93, 1.74 — falling, because the cost is n log²n and its exponent is on its way to one. The two cross between n = 64 and n = 128: below it the format is the more expensive way to solve the system, at 1.48 times the dense count, and at n = 512 it is 6.2 times cheaper. Every point returns an answer at a backward error of about 1.4·10⁻¹⁰, so the comparison is between two ways of getting the same thing.567891010⁴10⁵10⁶10⁷10⁸10⁹log₂ nmultiplicationsdense factorisation, n³⁄3the recursion, countedwhere the format starts payingratio at n = 641.5ratio at n = 5120.16exponent, first doubling2.1exponent, last doubling1.7backward error1.4·10⁻¹⁰cheaper is a sizenot a property
Fig. 24 The operation the weakly admissible partition exists for and the storage table does not price at all.
The residual of a formatted Cholesky, against the accuracy its blocks were compressed atA leaf of 64 means 2 truncations inside the factorisation, and the ranks of its blocks run to 4, 7, 9, 12, 14 across the sweep. The residual tracks the tolerance at a slope of 1.022 over ten decades: the knob does what a knob should, and nothing in the approximate arithmetic bends it. The ratio to the representation's own error stays at 0.95, 0.95, 0.96, 0.93, 0.93 — one excursion above one, at 10⁻⁶, where the tolerance sits between two singular values of one block and the rank it takes is a rounding of a decision rather than a measurement.10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²ε the blocks were compressed at‖A − LLᵀ‖ ⁄ ‖A‖the factorisationthe knob, on a factorisationtruncations2residual at 10⁻⁴5.2·10⁻⁶residual at 10⁻¹⁰9.5·10⁻¹²slope1worst ratio to the representation0.96ten decadesand a slope of one
Fig. 25 A formatted factorisation at a large leaf, where the tree is shallow and the dense fringe is most of the storage.
The residual of a formatted Cholesky, against the accuracy its blocks were compressed atA leaf of 8 means 98 truncations inside the factorisation, and the ranks of its blocks run to 4, 7, 9, 12, 14 across the sweep. The residual tracks the tolerance at a slope of 1.043 over ten decades: the knob does what a knob should, and nothing in the approximate arithmetic bends it. The ratio to the representation's own error stays at 0.83, 1.78, 0.85, 0.81, 0.86 — one excursion above one, at 10⁻⁴, where the tolerance sits between two singular values of one block and the rank it takes is a rounding of a decision rather than a measurement.10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²ε the blocks were compressed at‖A − LLᵀ‖ ⁄ ‖A‖the factorisationthe knob, on a factorisationtruncations98residual at 10⁻⁴2.2·10⁻⁵residual at 10⁻¹⁰10⁻¹¹slope1worst ratio to the representation1.8ten decadesand a slope of one
Fig. 26 And at a small one, where it is deep and the compressed blocks are. The accuracy does not distinguish them, which is what makes the leaf size a storage decision.
Applications of an operator that is never assembled, against the entries of the matrix it stands forThe blocks at one level of the tree have disjoint column supports, so one batch of random vectors samples all of them at once: two batches a level for the ranges, two more for the projections, and one batch of leaf products for every diagonal block in the matrix together. That is leaf + 2(2k + p)·levels products, and the counter inside the operator says 144, 208, 272, 336 at n = 64, 128, 256, 512 — 64 more per doubling, which is a logarithm. The other line is n², the entries the compression route reads. At n = 512 that is 336 products against 262,144 entries, and the representation it produces is within 6.5× of the one that read them all.567891010¹10²10³10⁴10⁵10⁶log₂ nnumbers the construction touchedentries, n²products with the operatoran operator, applied a few hundred timesproducts at n = 512336entries at n = 5122.6·10⁵per doubling64‖A − A_H‖ ⁄ ‖A‖4·10⁻¹⁰excess over the compression6.5no entry of the matrixwas ever read
Fig. 27 And what a larger rank costs the construction, from the randomised field, where a rank appears linearly rather than in a product along the depth of a tree.

Where this goes next

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. 10²10³10⁴10⁵matrix size ncountoperations, bothwords, unblockedwords, blocked (b = 6)the answer does not move‖PA − LU‖/‖A‖, unblocked2.8·10⁻¹⁶‖PA − LU‖/‖A‖, blocked2.8·10⁻¹⁶difference between them0the dashed curve is both orderings' operation countthe solid pair is what they cost The same arithmetic at a different price A blocked and an unblocked elimination perform 72,568 operations each — the same operations, associated differently — choose the same pivots, and return a factorisation identical to the last bit: ‖PA − LU‖/‖A‖ = 4.487946226420872·10⁻¹⁶ in both. One of them moves 41,332 words between fast and slow memory and the other moves 19,476. 10⁻³10⁻²10⁻¹1110¹10²10³10⁴pivot threshold τgrowth factor · entries in L+U, ÷ entries in Agrowthfillthe library default‖PA − LU‖/‖A‖ at τ = 0.12.9·10⁻¹⁶growth at τ = 0.138entries in L+U at τ = 0.1372one knob, two measurements, opposite directionsand the default is most of both A threshold between fill and growth One number decides how small a pivot an elimination will accept. At 0.001 the factor holds 172 entries and the matrix grows by 1,330; at 1 it holds 260 and grows by 1.2. The libraries ship 0.1, and the measurement says why.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

AdmissibilityAsymptotic analysisBlock methodsCluster treeFlop countHierarchical matrixLower boundNumerical rankOff diagonal rankWeak admissibility