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

The kernel with nothing to compress

Hold the geometry fixed at q = ½, fix the wavelength, and scale the picture up by sixteen. A smooth kernel needs six columns at every scale. An oscillatory one needs twelve, sixteen, twenty-two, thirty-three, fifty-three, and there is no scale at which it stops.
34 min read 25 figures Where the algebra stops being the arithmeticMeasured, not assertedAssertions that reject

Worth reading first: A block nobody can call sparse · The stencil that is not symmetric · The condition number is an amplifier.

Three essays in, this field has a thesis and no case against it. That is a bad sign, and the fix is not a caveat but an experiment.

Two kernels on identical geometry, as the picture is scaled up at a fixed wavelengthTwo parallel segments of length L a distance 2L apart, so q = 0.50 at every point on this sweep and nothing about the arrangement changes. 1/r needs 6, 6, 6, 6, 6 columns — one number. cos(κr)/r at κ = 40 needs 12, 16, 22, 33, 53, growing like a power of the size with no size at which it stops, because what decides it is the number of wavelengths across the pair — 3.2, 6.4, 12.7, 25.5, 50.9 — and no ratio of lengths can see that. The segments are parallel rather than collinear on purpose: in one dimension cos(κ|x − y|) obeys an addition formula and is exactly rank two, which makes the collinear version of this look like a confirmation of the smooth case and is an artefact of the arrangement.-1012301020304050log₂ of the segment lengthcolumns above 10⁻⁸cos(κr) ⁄ r at κ = 401 ⁄ r, same pointsthe case with no answerq, held fixed0.51/r at L = 0.561/r at L = 86cos(κr)/r at L = 0.512cos(κr)/r at L = 853the geometry did not moveand the rank did
Fig. 1 Two kernels on identical geometry, as the picture is scaled up at a fixed wavelength. One line is horizontal by construction and the other is the whole of this essay.

The experiment

The measurement in the previous essay held the geometry fixed and refined the sampling. This one does something different and more pointed: it holds the geometry fixed in the sense that matters — the separation ratio q — and grows everything else.

Two parallel line segments, each of length L, a distance 2L apart. The half-widths are L/2 each and the centres are 2L apart, so

q = (L/2 + L/2) / 2L = 1/2

at every scale. Sixteen-fold changes in L leave q at exactly one half; the assertion behind the figure checks that equality to twelve digits rather than assuming it, because an experiment whose independent variable secretly moves is not an experiment.

Both segments are sampled at 256 points, and two kernels are evaluated on the same points:

1/r and cos(κ r)/r , κ = 40 .

Count the singular values above 10⁻⁸ of the largest.

L q 1/r cos(40 r)/r wavelengths across the pair
0.5 0.5 6 12 3.2
1 0.5 6 16 6.4
2 0.5 6 22 12.7
4 0.5 6 33 25.5
8 0.5 6 53 50.9

The left column is the previous essay’s result, restated: a smooth kernel does not know how big the picture is. The right column is what happens when the kernel does.

Why the segments are parallel

This is the detail that took the longest to get right and it is worth the paragraph, because the obvious arrangement produces a confirmation of the thesis and it is an artefact.

Put the two clusters collinear — on [0, 1] and [2, 3], as in every earlier essay — and the distance between a point of one and a point of the other is |x − y|. Then

cos(κ|x − y|) = cos κx cos κy + sin κx sin κy

by the addition formula, which is a sum of two products of a function of x with a function of y. The numerator is exactly rank two. Multiplied entrywise by 1/|x − y|, which the earlier essays measure at rank five, the whole block has rank at most ten — and measured, at κ = 160 and 256 points, it is ten.

So the collinear arrangement says the oscillatory kernel is as compressible as the smooth one, and it says so for a reason that has nothing to do with kernels: one-dimensional geometry admits an addition formula that two-dimensional geometry does not. Move the segments off each other’s line and the distance is √((x − y)² + h²), which is not linear in x and y separately and has no addition formula, and the rank behaves as the table above shows.

That is the shape of mistake this collection keeps a whole habit for. A measurement taken in the cheapest available geometry confirmed the thesis; the confirmation was a property of the geometry; and every gate the site has would have passed it, because the number was correct and the assertion that read it was correct too.

The singular values of one off-diagonal block, for four kernels on the same 128 pointsTwo intervals that do not touch — [0, 1] and [2, 3] — and the 128 × 128 block between them, for four kernels. 1/r falls a factor of 52 a column and is below 10⁻⁸ after 5; log r behaves the same way, for the reason the expansion makes obvious. An independent draw per entry gives 128 singular values above 10⁻⁸ out of 128, on the same size and the same density, which is what makes the other curves a measurement rather than a property of sorted numbers. The block has full algebraic rank in every case; what differs is where the numbers stop mattering, and that is a decision rather than a fact about the matrix.051015202530354010⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹singular value, in orderσ ⁄ σ₁eight digitsan independent draw per entry1 ⁄ ra cliff, and a control1/r rank at 10⁻⁸5log r rank at 10⁻⁸5noise rank at 10⁻⁸128σ₂ ⁄ σ₁0.024σ₆ ⁄ σ₁2.8·10⁻⁹the block has full rankand five useful columns
Fig. 2 The collinear arrangement, where the oscillatory curve sits with the others and says nothing. Only the control on this figure is doing work.
The smallest eigenvalue of each circulant, ρ = 0.95Smallest eigenvalue against the matrix size on a linear vertical axis with zero marked. The wrapped circulant runs -0.6548, -0.4258, -0.1730, -0.0128, 0.0242 — negative at the small sizes and crossing zero by n = 256. The averaged one runs 0.0431, 0.0382, 0.0332, 0.0295, 0.0276: falling towards zero and never reaching it.10²0size nsmallest eigenvaluezerowrapped (Strang)averaged (T. Chan)an average of positives is positivewrapped, n = 16-0.65averaged, n = 160.043averaged, n = 2560.028a choice between two diagonals can be negativean average of them cannot
Fig. 3 Another place a one-dimensional coincidence flatters a method, from the structure field: a circulant is diagonalised exactly and nothing about that survives the move to two dimensions.

The growth, and what sets it

The right-hand column grows like a power. Fitted against the scale on a log–log axis the exponent is about 0.53, so the rank goes roughly like √L — or, in the quantity that has a meaning, like the square root of the number of wavelengths across the pair.

The mechanism is standard and worth stating in one sentence. The block is a sampling of cos(κ r)/r as a function on a rectangle, and how many separable terms a function needs is set by how much it oscillates across that rectangle. A smooth kernel varies by a fixed amount across the rectangle however large the rectangle is, because r and the rectangle scale together and 1/r is homogeneous. cos(κ r) does not scale: κ is a fixed number with units, so a rectangle twice as large contains twice as many oscillations.

The number that decides an oscillatory rank is therefore κL²/d — the count of wavelengths across the geometry, which for these segments is κL/4π — and no ratio of lengths can see it. q is dimensionless. The wavelength is not. A test written in q alone is blind to the one quantity that matters here, which is why an admissibility rule that works for the Laplace kernel does not transfer to the Helmholtz one and why high-frequency scattering is a different subject rather than a harder instance of this one.

Two kernels on identical geometry, as the picture is scaled up at a fixed wavelengthTwo parallel segments of length L a distance 2L apart, so q = 0.50 at every point on this sweep and nothing about the arrangement changes. 1/r needs 6, 6, 6, 6, 6 columns — one number. cos(κr)/r at κ = 5 needs 6, 7, 9, 12, 16, growing like a power of the size with no size at which it stops, because what decides it is the number of wavelengths across the pair — 0.4, 0.8, 1.6, 3.2, 6.4 — and no ratio of lengths can see that. The segments are parallel rather than collinear on purpose: in one dimension cos(κ|x − y|) obeys an addition formula and is exactly rank two, which makes the collinear version of this look like a confirmation of the smooth case and is an artefact of the arrangement.-1012305101520log₂ of the segment lengthcolumns above 10⁻⁸cos(κr) ⁄ r at κ = 51 ⁄ r, same pointsthe case with no answerq, held fixed0.51/r at L = 0.561/r at L = 86cos(κr)/r at L = 0.56cos(κr)/r at L = 816the geometry did not moveand the rank did
Fig. 4 At the lowest wavenumber the two curves nearly coincide: a wave that does not fit inside the picture is a smooth function, and the format works on it.
Two kernels on identical geometry, as the picture is scaled up at a fixed wavelengthTwo parallel segments of length L a distance 2L apart, so q = 0.50 at every point on this sweep and nothing about the arrangement changes. 1/r needs 6, 6, 6, 6, 6 columns — one number. cos(κr)/r at κ = 80 needs 16, 22, 33, 53, 92, growing like a power of the size with no size at which it stops, because what decides it is the number of wavelengths across the pair — 6.4, 12.7, 25.5, 50.9, 101.9 — and no ratio of lengths can see that. The segments are parallel rather than collinear on purpose: in one dimension cos(κ|x − y|) obeys an addition formula and is exactly rank two, which makes the collinear version of this look like a confirmation of the smooth case and is an artefact of the arrangement.-101230163248648096log₂ of the segment lengthcolumns above 10⁻⁸cos(κr) ⁄ r at κ = 801 ⁄ r, same pointsthe case with no answerq, held fixed0.51/r at L = 0.561/r at L = 86cos(κr)/r at L = 0.516cos(κr)/r at L = 892the geometry did not moveand the rank did
Fig. 5 And at the highest, where the rank at the largest scale is most of a hundred and the smooth line has not moved.

What breaks, exactly

It is worth being precise about which parts of the field survive this and which do not, because “the format fails” is too coarse and would be wrong.

The partition survives. The tree, the admissibility test, the block structure and the recursion are all still well defined and still produce a correct representation of the matrix. Nothing in them consults the kernel.

The storage claim does not. The whole argument for n log n storage rests on the rank of an off-diagonal block being a constant, and here it is a growing function of the block’s physical size. At a fixed wavelength and a refining mesh the rank is bounded — the geometry is not growing, only the sampling — so the format is usable on a fixed scattering problem. What fails is the sentence about solving a larger problem at the same cost per unknown, which is the sentence the format was built for.

And the accuracy claim survives untouched. Every representation built at ε is still within ε; the compression is still a backward error; the residual of a solve with it is still the representation’s error. What has changed is only how many numbers that costs. This is the good kind of failure — an expense rather than a wrong answer — and it is worth saying so, because the alternative failure mode is the one this collection spends most of its time on.

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. 6 The claim that does not survive, from later in this field. The lower two lines add a constant per doubling because a rank is a constant; on an oscillatory kernel they would not.
The backward error of a hierarchical solve, against the error of the representation it usedSolve A_H x = b exactly and the residual against the matrix that was wanted is b − Ax = (A_H − A)x, so ‖b − Ax‖ ⁄ ‖A‖‖x‖ cannot be anything but the representation's own error. Measured across six accuracies spanning ten decades, the two track at a slope of 0.983 and sit a constant 7.4× apart, which is the difference between a norm of a matrix and a norm of that matrix applied to one vector. The reading is the one this field is built on: the accuracy knob is not an accuracy, it is a backward error chosen in advance. Everywhere else on this site a backward error is something an algorithm produced and somebody then measured; here it is a line in the program, and its size is known before the solve starts.10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³‖A − A_H‖ ⁄ ‖A‖, the representation‖b − Ax‖ ⁄ ‖A‖‖x‖, the solveequala backward error, chosenslope0.98representation at 10⁻⁸1.4·10⁻⁹backward error there1.4·10⁻¹⁰representation at 10⁻¹²1.2·10⁻¹³backward error there2.3·10⁻¹⁴the compression is not an approximationit is a perturbation of the problem
Fig. 7 And the claim that does. Whatever the rank costs, what the compression is does not change.

The number the geometry cannot see, stated carefully

There is a temptation to summarise this as the format needs smooth kernels, and that summary is close enough to be repeated and loose enough to mislead, so it is worth replacing with the actual condition.

What the expansion in the first essay of this field needs is that the kernel be asymptotically smooth: that its derivatives of order p, taken away from the diagonal, grow no faster than p! times a constant to the p over r to the p. That condition is what makes the Taylor coefficients fall off geometrically, and it is satisfied by 1/r, by log r, by 1/r² and by every derivative of any of them — which is to say by the Green’s functions of the Laplace, Stokes and elasticity operators and by the covariance kernels of most of statistics.

cos(κr)/r satisfies it too, with a constant that contains κ. That is the whole subtlety: the kernel is not disqualified, its constant is bad, and a constant that contains a dimensional parameter interacts with a geometry that has a size. The bound reads

rank ≈ (something in q) + (something in κ · diam) ,

and a partition that only controls the first term controls half of it.

So the condition is not smooth and it is not not oscillatory. It is that the kernel must have no length scale of its own, or that whatever length scale it has must be large compared with every cluster the partition produces. A code can check the second version cheaply — it knows κ and it knows its clusters — and the checking is exactly the modified admissibility test the last section describes.

That reframing also explains the two ends of the drag on the hero figure. At κ = 5 a wavelength is longer than the whole picture at every scale drawn, the second term is small, and the two curves sit almost on top of each other. At κ = 80 the second term dominates by the third scale. Nothing about the kernel changed between those two figures except a number with units.

Two kernels on identical geometry, as the picture is scaled up at a fixed wavelengthTwo parallel segments of length L a distance 2L apart, so q = 0.50 at every point on this sweep and nothing about the arrangement changes. 1/r needs 6, 6, 6, 6, 6 columns — one number. cos(κr)/r at κ = 10 needs 7, 9, 12, 16, 22, growing like a power of the size with no size at which it stops, because what decides it is the number of wavelengths across the pair — 0.8, 1.6, 3.2, 6.4, 12.7 — and no ratio of lengths can see that. The segments are parallel rather than collinear on purpose: in one dimension cos(κ|x − y|) obeys an addition formula and is exactly rank two, which makes the collinear version of this look like a confirmation of the smooth case and is an artefact of the arrangement.-101230510152025log₂ of the segment lengthcolumns above 10⁻⁸cos(κr) ⁄ r at κ = 101 ⁄ r, same pointsthe case with no answerq, held fixed0.51/r at L = 0.561/r at L = 86cos(κr)/r at L = 0.57cos(κr)/r at L = 822the geometry did not moveand the rank did
Fig. 8 Near the bottom of the drag, where a wavelength is still comparable with the picture and the oscillatory curve has only begun to lift away.

The company it keeps

This site has three other places where a method meets a problem it cannot exploit, and the family resemblance is worth naming.

randomisation-does-not-create-structure is the closest: a randomised low-rank approximation of a matrix with a flat spectrum returns nothing useful, and nothing else would either, because there is no low-rank structure to find. The failure is honest in the sense that no method could do better.

the-spectrum-that-predicts-nothing is different in kind. There the method works and the predictor fails: GMRES on a non-normal matrix converges at a rate the eigenvalues do not describe, so the quantity everybody reaches for is the wrong quantity. This essay is of that second kind. The format works; q is the wrong quantity; and the right one is not in the geometry at all.

a-limit-the-matrix-never-reaches is the third: Toeplitz structure buys an exact spectrum and does not buy a well-conditioned problem, and the half that gets summarised away is the half that decides whether anything can be solved.

Three ways for a structural claim to be less than it looks: the structure is absent, the predictor is the wrong one, or the structure is real and buys something other than what was wanted. This field’s counterweight is the middle one.

The randomised SVD against the optimum it cannot beatA semi-logarithmic plot of approximation error against target rank. A shaded band shows the spread across seeds, a solid line the optimal error from the exact singular values, and a dashed line the published probabilistic bound well above both.04812162010⁻¹10⁻⁰.⁵1target rank k‖A − A_k‖₂published boundrandomisedσ_{k+1}, optimalhow far apart the three areworst seed spread1.6bound / median at k = 125.9median / optimum at k = 121.960×60, 6 seeds, oversampling p = 5band is best to worst
Fig. 9 The first of the three, from the randomised field: a flat spectrum, and a method returning what is there to be returned, which is nothing.
GMRES on the Laplacian and on the cyclic shift, both 40×40A semi-logarithmic plot of relative residual against iteration. One curve falls steadily; the other is flat at one for every step until the last, where it drops to zero.071421283510⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1iteration‖r‖ / ‖b‖Laplaciancyclic shiftno progress at allevery eigenvalue of the shift is on the unit circleand it predicts nothing
Fig. 10 And the second, from the iterative field, which is the one this essay is an instance of: the standard predictor evaluated on a problem it does not describe.

What a code should do about it

The measurement suggests three responses and only the third is satisfactory.

Detect it. The rank a block turns out to need is available after the block is compressed, so a format can notice that its ranks are growing and report it. That is worth doing and it is a diagnosis rather than a remedy: by the time the ranks are large the memory has been spent.

Refuse it. An admissibility test written in κ·diam as well as in q — a pair is admissible when it is well separated and small compared with a wavelength — produces a partition whose blocks are all genuinely low rank. That works and it produces a great many more blocks, because the second condition puts an absolute cap on cluster size where the first is scale-free. The storage stops being n log n and starts being something worse.

Or change the representation. The methods that actually solve high-frequency scattering keep a low-rank structure that is directional: a block is factored separately for each range of incoming directions, and each of those factors is small. That is a different format with a different partition and it is not this one.

The honest summary is that this field’s format is a Laplace-kernel format, that it applies to everything whose Green’s function is asymptotically smooth — which is a great deal — and that the cases it does not cover are not covered by patching it.

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. 11 The second response, in the form it takes for a different reason, from two essays ahead: a finer partition, smaller ranks, and more of them.
−εu″ + u′ = 0 on 31 points, ε = 0.005, cell Péclet 3.125Three solutions of a boundary-layer problem on the same grid. The exact one rises monotonically from 0 to 1 with a layer of width ε at the right-hand end. The central-difference answer alternates at every point and leaves [0, 1] at 16 of the 31 of them, by as much as 0.5152. The upwind answer is monotone at every Pe.00.250.50.75100.250.50.751xuexactcentral differencesupwindthe oscillation is exact‖Ax − b‖/‖b‖ for the central answer4.6·10⁻¹⁸values outside [0, 1]16worst excursion0.52the dashed lines are 0 and 1, which the equation guaranteesno solver was involved
Fig. 12 And the collection’s other essay about a dimensionless number that stops predicting, from the convection field: below a threshold the standard reading is right and above it the discretisation is oscillatory, and the number that says which is not in any norm.

What the counterweight is for

A field with a thesis and no case against it is not a field with a strong thesis; it is a field whose experiments were chosen by whoever holds the thesis. This site has run into that twice before and written it down both times, so the pattern is worth naming rather than performed.

The first was in the randomised field, where the essay on what randomisation does not create exists because every other essay in that field is about a method working. The second was in the sequence field, where three essays found a rule that reads a free measurement and beats every constant, and the fourth found the boundary — a decision half of which is invisible in any solve, where the same shape of rule loses by ninety-three per cent.

The shape is the same in all three. The positive essays establish a mechanism; the counterweight establishes the mechanism’s domain, which is the part a reader needs in order to know whether their own problem is inside it. Without it the collection has taught a technique and not taught when it applies, which is the failure mode of every method paper ever written.

Here the domain is stated as sharply as the measurements allow. Inside it: kernels with no length scale of their own, clusters separated by their own diameter, ranks that are constants. Outside it: one number with units, and a rank that grows like the square root of the picture with no size at which it stops.

The cheapest rebuild period for one drifting sequence, against what a rebuild costsOne sequence, one drift rate, one preconditioner — and six answers, because the answer is not a property of the sequence. Costed in iteration-equivalents, the optimal period runs from every 1 member at a setup worth 5 iterations to every 8 at a setup worth 200. A dense Cholesky at this size is worth 6.7 iterations, which is at the left of the axis, so for it the answer is always to rebuild. The rule that rebuilds when a solve takes 1.5 times what the last fresh one did beats the best fixed period at 0 of the 6 ratios and loses at the rest, because it cannot see the setup cost at all.10¹10²10³0246810what one rebuild is worth, in preconditioned iterationscheapest number of members between rebuildsa dense Cholesky here is worth 6.7 iterationsringed: where the growth rule beats every fixed periodcheapest period, by setup costsetup worth 51setup worth 102setup worth 203setup worth 504setup worth 1006setup worth 2008how long to keep itis a question about what it cost to build
Fig. 13 The sequence field’s counterweight, from the essay that found the boundary of its own reading: three essays where a rule beats a constant, and a fourth where half the decision is invisible to it.

The refusal

The claim under test is the one the first three essays of this field would leave a reader holding: that a matrix built from a kernel and two clusters of points has low-rank off-diagonal blocks.

It is fed the case at the far end of this sweep — two parallel segments of length 8 at a distance of 16, so q is exactly the ½ of every compressible measurement in this field, with cos(40 r)/r in place of 1/r. The assertion that the block needs at most twelve columns at 10⁻⁸ is handed 53, and it fails.

What makes the refusal worth the code is that it is fed the same geometry the thesis was measured on. A counterexample with a different q would be a demonstration that admissibility matters, which is a different essay and already written. This one holds every quantity the earlier essays vary, and changes only the one they never mention.

Two kernels on identical geometry, as the picture is scaled up at a fixed wavelengthTwo parallel segments of length L a distance 2L apart, so q = 0.50 at every point on this sweep and nothing about the arrangement changes. 1/r needs 6, 6, 6, 6, 6 columns — one number. cos(κr)/r at κ = 20 needs 9, 12, 16, 22, 33, growing like a power of the size with no size at which it stops, because what decides it is the number of wavelengths across the pair — 1.6, 3.2, 6.4, 12.7, 25.5 — and no ratio of lengths can see that. The segments are parallel rather than collinear on purpose: in one dimension cos(κ|x − y|) obeys an addition formula and is exactly rank two, which makes the collinear version of this look like a confirmation of the smooth case and is an artefact of the arrangement.-101230714212835log₂ of the segment lengthcolumns above 10⁻⁸cos(κr) ⁄ r at κ = 201 ⁄ r, same pointsthe case with no answerq, held fixed0.51/r at L = 0.561/r at L = 86cos(κr)/r at L = 0.59cos(κr)/r at L = 833the geometry did not moveand the rank did
Fig. 14 Halfway up, where the rank at the largest scale is already four times the smooth one and the two lines have long since separated.
κ of the 0.8 kernel on m×m grids, against its two-dimensional limitCondition number against the grid side on a logarithmic vertical axis, with the asymptotic value ((1+ρ)/(1−ρ))⁴ = 6561 drawn as a horizontal line. The measured values are 581, 1196, 1794, 2337, reaching 35.6% of the limit on the largest grid — where the one-dimensional section of the same length reaches far more.4681010³10⁴grid side mκlimit 6561measured κthe symbol multipliesthe limit, from the symbol6561κ at 10×102337share of the limit reached0.36the limit is the square of the one-dimensional oneand it is further away
Fig. 15 And what a second dimension does to a structural claim elsewhere on the site, from the structure field, where the cluster that a one-dimensional argument promised turns out to thin out.
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. 16 The result this essay is the counterweight to, for reading side by side: one row flat over a factor of eight, on a kernel that has an expansion.

What survives the counterweight

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. 17 The claim that does not survive: numbers stored per unknown, whose flatness rests on a rank that is a constant.
The residual of a formatted Cholesky, against the accuracy its blocks were compressed atA leaf of 32 means 10 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.028 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.94, 0.89, 0.92, 0.92, 0.93 — one excursion above one, at 0.01, 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 factorisationtruncations10residual at 10⁻⁴1.1·10⁻⁵residual at 10⁻¹⁰9.6·10⁻¹²slope1worst ratio to the representation0.94ten decadesand a slope of one
Fig. 18 The claim that does: a factorisation in the format tracks its tolerance whatever the ranks cost, so an oscillatory kernel is an expense rather than a wrong answer.
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. 19 The partition, which is unaffected. Nothing in the tree or the test consults the kernel, and the structure it produces is correct on any matrix at all.
How many columns a decade of accuracy costs, measured and predicted, at q = 0.333The number of singular values above ε, against the number of digits ε asks for, on a 128 × 128 block between two intervals separated by a gap of 2. The measured curve is a straight line at 0.50 columns a decade: a digit costs the same handful of columns wherever you buy it, which is why the accuracy is a knob and not a cliff. The upper line is what the geometry alone promises — q^(p+1)/(1 − q) below ε, solved for p, using four numbers and no entry of the matrix — at 2.11 columns a decade. Both are straight and they are not the same straight: the bound is right about the shape and loose by 4.3× about the constant, which is the safe direction for a quantity you have to allocate storage from.0369121507142128digits asked for, −log₁₀ εcolumns keptwhat the geometry promiseswhat the matrix costsa rank is a number of digitscolumns a decade0.5bound, a decade2.1rank at 10⁻⁸4bound at 10⁻⁸18q0.33the shape is rightand the constant is not
Fig. 20 The exchange rate on a well-separated smooth pair, for comparison: half a column a decade, where the oscillatory case buys columns with the geometry’s size instead.
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 4, 4, 4, 4 columns, which is one number. The touching pair — [0, 1] against [1, 2] — needs 8, 9, 10, 11, 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 = 324admissible, n = 2564touching, n = 328touching, n = 25611stored ⁄ dense at largest0.031the rank belongs to the geometryand not to the sampling
Fig. 21 And the null result the counterweight is against, at six digits.
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.25, 1.95, 1.78 — falling, because the cost is n log²n and its exponent is on its way to one. The two cross between n = 128 and n = 256: below it the format is the more expensive way to solve the system, at 2.36 times the dense count, and at n = 512 it is 3.4 times cheaper. Every point returns an answer at a backward error of about 2.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 = 642.4ratio at n = 5120.29exponent, first doubling2.2exponent, last doubling1.8backward error2.4·10⁻¹⁴cheaper is a sizenot a property
Fig. 22 What large ranks do to a solve, from the cost field: the crossover walks right, and on an oscillatory kernel it walks off the figure.
What the anisotropy does to the compressibility of the fill, on the operator this site has a field aboutThe five-point operator's two directions stop being equally weighted, ε running from 1 down to 0.01, and the condition number of what is left on the separator rises from 13.1 to 72.5. Every method in the iterative field gets worse across this sweep: a point smoother stops seeing one direction, a coarse grid stops representing it, and the whole anisotropy anchor exists because of it. The fill goes the other way. Its rank falls 5, 5, 4, 3, 3 — a strongly anisotropic Green's function is *closer* to separable than an isotropic one, because coupling along the weak direction has almost vanished and what is left is nearly a function of one coordinate. The fill stays 100 per cent nonzero throughout, so nothing about the amount of fill is moving; only the amount of information in it.-2-1002468log₁₀ of the anisotropy εcolumns above 10⁻⁸columns the fill needsharder, and more compressiblerank at ε = 15rank at ε = 0.013κ at ε = 113κ at ε = 0.0173entries nonzero1the operator got worseand the fill got cheaper
Fig. 23 The opposite surprise in the sparsity field, from the last essay of this run: an operator that gets harder and a fill that gets cheaper.
How far |r_nn| sits above σ_min on Kahan's matrix, against the size and the parameter3 curves of |r_nn| ÷ σ_min against n, one per Kahan parameter. Every curve rises without turning over, reaching 7·10⁴ at n = 30, c = 0.5. Column pivoting makes no interchange at any point on any of them, so the failure is not a poor choice — there is nothing to choose.813182328110¹10²10³10⁴10⁵10⁶size of the matrix|r_nn| ÷ σ_minthe two agreec = 0.2c = 0.35c = 0.5no ceilingratio at n = 1021ratio at n = 307·10⁴interchanges, anywhere0the greedy rule never had a choiceand the gap grows with every row
Fig. 24 A method with nothing to choose on, from the spectra field, which is the other way a structural claim turns out to be about the case it was measured on.
‖Aᵏ‖ for a 6×6 matrix whose spectral radius is 0.8, with 3 above the diagonalTwo curves against the power. The norm of Aᵏ rises to 1.5·10⁵ at step 24 before turning over and decaying to 1.9·10⁻⁴ by step 160; ρᵏ = 0.8ᵏ, drawn beside it, falls from the start. The two horizontal lines are the Kreiss bracket: the peak is at least K = 50880 and at most e·n·K = 8.3·10⁵, both computed from the resolvent norms outside the unit circle and not from the powers at all.027548110813510⁻⁵10⁻³10⁻¹10¹10³10⁵10⁷power‖Aᵏ‖Kreiss constant 50900e · n · K‖Aᵏ‖ρᵏtwo routes to one peakspectral radius0.8peak of ‖Aᵏ‖1.5·10⁵Kreiss constant5.1·10⁴e · n · K8.3·10⁵everything here decays in the endand one of these curves says how much first
Fig. 25 And the collection’s standing case of a predictor evaluated on a problem it does not describe, from the field that measured it.

Where this goes next

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 The size the rank does not notice Sample a kernel block at 32, 64, 128 and 256 points a side and it needs five columns, five, five and five. Sample the touching block next to it at the same four sizes and it needs nine, eleven, twelve and thirteen. Same kernel, same accuracy, one number and a logarithm. 02468101210⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1iteration‖r‖ / ‖b‖Laplaciancyclic shiftno progress at allevery eigenvalue of the shift is on the unit circleand it predicts nothing The spectrum that predicts nothing For a symmetric matrix the eigenvalues govern how fast an iteration converges. Drop symmetry and they stop governing anything — there is a matrix whose eigenvalues are as evenly spread as eigenvalues can be, on which GMRES makes no progress at all until the last possible step. 04812162010⁻¹10⁻⁰.⁵1target rank k‖A − A_k‖₂published boundrandomisedσ_{k+1}, optimalhow far apart the three areworst seed spread1.1bound / median at k = 1211median / optimum at k = 12160×60, 6 seeds, oversampling p = 5band is best to worst Randomisation does not create structure On a matrix whose singular values are all equal, a rank-ten randomised approximation has error 1.0 — and so does the optimal deterministic one. Neither achieved anything, and only one of them is usually sold with the implication that it might.

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 analysisCounterexampleFourier modesHierarchical matrixKernel matrixNumerical rankOff diagonal rankSeparable expansionSpectral decay