A line at the real kernel's slope

The smaller cluster sets the rank measured the rank of the block of $\cos(\kappa r)/r$ between two parallel segments — the off-diagonal block a hierarchical matrix stores in low-rank form for an oscillatory kernel — and found that what decides it is the Fresnel number $F = \kappa ab/(2\pi D)$: the two lengths’ product over their distance, in wavelengths, the count optics gives for the waves two apertures can exchange. For square blocks the rank over $\sqrt F$ sat near nine from $F = 2$ to 8 and rose to 9.8 at 16, and the earlier essay’s largest block, at $F$ of about 25, needed 53 columns. A square root was the shape the size the rank does not notice had first reported, and the essay suspected it of being a regime rather than a law.

“The optics count predicts that the number of well-coupled beams grows in proportion to the Fresnel number, not as its square root. … The prediction with a sign is that past $F \approx 30$ the rank becomes a straight line in $F$ with a slope near two, one beam for each direction the real kernel travels in, and that the square-root law was the regime in which the margin of the accuracy dominates.”

The second half holds. The first holds in shape and fails in its number, and the number turns out to be computable before any block is factorised.

Counting past the dense route #

The blocks are the earlier essays’: two equal parallel segments, centred on each other, their distance the sum of their lengths so the separation ratio is one half, $\kappa = 40$, sampled at twelve points a wavelength. At $F = 24$ the block is 576 by 576 and its dense singular values take a hundred seconds; the number of samples grows with $F$ and the cost with its cube, so $F = 64$ would take most of an hour. The rank is counted instead by a randomised range finder: multiply the block by a Gaussian matrix with comfortably more columns than the expected rank, orthonormalise, apply two power iterations, and take the singular values of the block projected onto the result, doubling the sketch until its last singular value is below $10^{-12}$ of the first. The sketch that is not the answer is the reminder that this is an approximation with its own error; here it is checked where it can be. At $F = 8$ and 16 the sketched rank at $10^{-8}$ is 25 and 39, exactly the dense counts, and at 24 the sketch gives 51 where the dense route gave 51.

The figure at the top of the page answers the shape question at once. At $10^{-8}$ the rank is 13, 18, 25, 39, 51, 64, 88 and 111 at $F = 2, 4, 8, 16, 24, 32, 48$ and 64. From 16 on, the points lie on a straight line; the increments over each eight units of $F$ are twelve, thirteen, then twenty-four and twenty-three over sixteen. At the other two tolerances the same: 19 to 102 at $10^{-4}$, 30 to 121 at $10^{-12}$, both straight from 16 on.

The slope is not two #

From $F = 32$ to 64 the rank at $10^{-8}$ rises by 47, a slope of 1.47. At $10^{-4}$, 1.47 as well; at $10^{-12}$, 1.56. None is near two, and the increments are not rising towards two either — they fall slightly with $F$.

The prediction’s reasoning was that the complex kernel $e^{i\kappa r}/r$ carries about $F$ independent waves between the two segments, and the real kernel is half the sum of that kernel and its conjugate, which travels the other way; two directions, twice the waves. The first step is right and can be computed exactly. At a target point $x$, the source segment is seen over a range of directions, and the block’s row oscillates in $x$ with local frequency $\kappa \sin\theta$ for every direction $\theta$ in that range. Count the area of that band of frequencies over the whole target, divide by $2\pi$, and the result is the number of waves the complex kernel can carry: 0.944 $F$ for this geometry, slightly under the paraxial count because the segments subtend wide angles.

The second step is where two becomes 1.40. The conjugate kernel’s band at each point is the first band reflected through zero. At the centre of the target the band is symmetric — the source is seen equally to the left and right — and its reflection is itself; the conjugate adds nothing there. Towards the ends the band slides to one side and its reflection slides to the other, and only there does the conjugate contribute directions the first wave did not have. The real kernel’s count is the area of the union of the two bands, and for two equal segments at this separation it is 1.396 $F$ — at $F = 64$, 89 waves, where twice the complex count would be 121.

The measured slope, 1.47 at $10^{-8}$, is within six per cent of 1.40, and at $10^{-4}$ the same; the prediction’s two is thirty-six per cent away. The beams the essay counted are not independent across the two directions, because a beam that leaves the target at an angle and a beam that arrives at the reflected angle are, near the middle of the block, the same oscillation.

Why the real kernel and not the complex one #

The kernel measured here is the real part of the Helmholtz Green’s function, which is what the earlier essays on off-diagonal rank have used throughout, and the choice matters more than it seemed. A boundary-integral solver for a scattering problem works with the complex kernel $e^{i\kappa r}/r$ — an outgoing wave, with one direction of travel — and its blocks should follow the complex count, 0.944 $F$ plus an edge, about two-thirds of the real kernel’s rank at the same $F$. A cosine kernel arises when the outgoing and incoming solutions are added, as in a standing-wave or a real-arithmetic formulation, and it is the one whose blocks pay for both bands.

The union count also explains why the earlier essays’ smaller cluster set the rank. A short target sees the source over a narrow range of positions along itself, so its band of directions changes little from one end to the other, and the band and its reflection overlap almost everywhere when the target is centred; the union is barely wider than one band. A long target’s ends see very different directions, the band slides across the whole range, and the reflection doubles the area near the ends. The Fresnel number measures the band’s average width; the union measures how much the conjugate adds to it, which is a property of the shape.

A square root that was a line plus a constant #

The square-root reading came from the small-$F$ end of the same line. Divided by $\sqrt F$ the rank is 9.2, 9.0 and 8.8 at $F = 2$, 4 and 8 — flat, as the earlier essay found — and then 9.8, 10.4, 11.3, 12.7 and 13.9, climbing without limit. Divided by $F$ it is 6.5, 4.5 and 3.1 and then falls towards 1.73 at 64 and, on the evidence of the line, towards the union count’s 1.40. A function of the form $1.4F + c$ with $c$ near fifteen is flat over $\sqrt F$ to within a few per cent for $F$ between two and eight, because over that range $1.4F$ and $c$ are comparable and their sum happens to grow like a square root. A rank that is a number of digits made the same point about a smooth kernel, whose whole rank is the constant: here the constant is the part of an oscillatory rank that the accuracy buys, and at small $F$ it is most of it.

What lies above the line #

Subtract the union count from the rank and what is left is the margin the prediction’s second half was about. At $10^{-8}$ it is 10 columns at $F = 2$, 17 at 16 and 22 at 64; at $10^{-4}$, 13 at 64; at $10^{-12}$, 32. Over a thirty-two-fold range of $F$ it grows by about twelve at $10^{-8}$ — roughly linearly in $\log F$ — and from $F = 16$ to 64 by under ten at every tolerance. Each four decades of tolerance adds about nine columns at $F = 64$.

That is the shape the theory of band-limited functions predicts for the edge of a wave count: a plateau of singular values near the largest, as many as the phase-space area, then a transition region whose width grows like the logarithm of the count times the logarithm of the tolerance. The earlier essay’s guess — “the square-root law was the regime in which the margin of the accuracy dominates” — is exactly right in this reading. At $F = 2$ the union count is 2.8 waves and the rank at $10^{-8}$ is 13: the margin is more than three-quarters of the rank. At $F = 64$ it is a fifth.

The dial shows the edge directly. Measured in units of the union count, the singular values stay within two decades of the largest until an index a little past the count — 1.43 times it at $F = 8$, 1.12 times at 32 — and then fall, and the fall becomes steeper relative to the count as $F$ grows, because its width in columns grows only slowly while the count grows linearly. At $F = 8$ the fall from $10^{-2}$ to $10^{-12}$ takes fourteen columns, more than the count itself; at $F = 32$ it takes twenty-one, under half the count.

The practical use of the decomposition is a rank that can be written down before the block is built. A code that compresses blocks adaptively needs to know how many columns to sample, and too few means a second pass while too many means wasted products. The union count is a quadrature over the geometry, a few thousand evaluations of a square root, and it is right to within the margin; the margin at a given tolerance is a slowly growing number that one calibration block per tolerance pins down. Calibrated at $F = 16$ — 39 columns against a count of 22.3, a margin of 16.7 — the estimate for $F = 64$ is $89.4 + 16.7$, about 106, against 111 measured; the logarithmic growth of the margin accounts for the rest, and an estimate that adds a column or two for each doubling of $F$ lands on it. A sketch sized from that estimate, plus the usual oversampling, finishes in one pass.

What this does to a hierarchical matrix #

A hierarchical matrix of an oscillatory kernel stores each admissible block at its rank. If the rank were twice the Fresnel number, storage and work at high frequency would be double what the union count says; if it were a square root, oscillatory problems would be nearly as cheap as smooth ones. The measured rank is the union count plus a logarithmic edge, which for square blocks at a fixed separation ratio means a rank proportional to the block’s length in wavelengths — the reason standard hierarchical formats lose their near-linear complexity at high frequency, and the reason directional formats, which split each block’s directions into cones whose union counts are small, exist at all. The kernel with nothing to compress found the extreme of this, a kernel whose blocks had no low rank at any size; the oscillatory kernel is between that and the smooth one, and the line says where.

The union count also says something the Fresnel number alone did not. Two configurations with the same $F$ can have different union areas — the overlap between a band and its reflection depends on how symmetric the view is — and a block seen off to one side, where the band never straddles zero, would have no overlap at all, and a count of twice its complex one. Which pairs are allowed to be small chose admissible pairs by distance and size; this suggests the directional overlap is a third quantity a partition of an oscillatory kernel should read.

The cost argument is short and worth making with numbers. A square admissible block at Fresnel number $F$ spans about $4\pi F/\kappa$ in length — $a = 4\pi F/\kappa$ when the separation equals twice the length — which is $24F$ samples per side at twelve a wavelength. Stored densely it is $576F^2$ numbers; stored at rank $r$ it is $48Fr$. With $r = 1.4F + 22$ at $10^{-8}$ the compressed block is $67F^2 + 1{,}056F$ numbers, a fraction $0.12 + 1.8/F$ of the dense one: an eighth at large $F$, and no better. Compression of an oscillatory kernel at a fixed separation ratio buys a constant factor and not an order, which is the statement a block nobody can call sparse made about the smooth kernel’s blocks being small but dense, carried to a kernel whose blocks are not small at all.

The randomised count is itself part of the lesson. The dense singular value decomposition the earlier essays used cost a cube in the samples, and it stopped these measurements at $F$ near 25; a sketch with a few hundred columns costs the samples squared times the sketch’s width for each pass, which at $F = 64$ is about the same arithmetic as the dense factorisation would be and takes three minutes where the dense route, scaled from its hundred seconds at $F = 24$, would take half an hour — the dense route’s iterative decomposition carries a large constant, the sketch’s products do not — and it is exact here to the column wherever it was checked. The sketch that is spent warned that a sketch can be used only once against a given input; each block here is sketched once, from a fresh draw, and the power iterations reuse the block and not the draw.

What sixty-four does not show #

The largest block measured is $F = 64$, 1,536 samples a side, and the line is established over a factor of four in $F$; a slope that drifted slowly towards two would show more clearly over a wider range, though nothing in the increments, which fall slightly, suggests it. The sketch is checked against the dense count at $F = 8$, 16 and 24 only, and its power iterations are fixed at two; at the largest $F$ the singular values near $10^{-12}$ are the ones a sketch is least sure of, and the $10^{-12}$ counts there may be one or two high or low. And every block is square and centred; the union count’s dependence on the view’s symmetry is computed, not measured, so the reading of the slope as the union’s rests on one geometry agreeing with one quadrature to within six per cent.

Still open: a block seen from the side, and a partition by overlap #

Sideways. For two equal segments offset along their own line so that the target sees the source entirely to one side, the outgoing and incoming bands never overlap. The prediction with a sign is that such a block’s rank, at the same $F$, follows twice the complex count — a slope near 1.9 rather than 1.4 — and that the change from one slope to the other happens as the offset carries the band past zero, at an offset of about half the segment length.

A partition by overlap. If a block’s rank is its union count plus a logarithmic edge, then splitting a block whose bands separate — the ends of a long target — into pieces that each see a narrow band should save more than splitting at the centre, where the bands coincide. The prediction is that on the earlier essays’ segment geometry, a partition that splits first where the band and its reflection separate stores 15 to 25 per cent less than one that splits at midpoints, at the same accuracy and the same number of blocks.