Kernel matrix — where it appears
Named by 11 essays across 2 fields — each of them below, with the objects they name alongside it.
A block nobody can call sparse
A 96 × 96 block of a kernel matrix has ninety-six nonzero singular values and five that matter. It has no zero entries, it is not described by fewer numbers than it contains, and neither of the two ways this collection already knows to make a large matrix affordable applies to it.
A rank that is a number of digits
Ask a kernel block for two digits and it costs two columns; ask for fourteen and it costs nine. The curve is a straight line at 0.55 columns a decade, and the bound the geometry gives is a straight line too — at 3.32, which is the same shape and six times the price.
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.
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.
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.
The fill that is not independent
Eliminate both halves of a grid and what is left on the separator is 100 per cent nonzero — the sparsity field's result, unchanged. Its off-diagonal block is 11 by 12 and six columns describe it to eight digits. Renumber the separator and the same block needs all eleven.
The cliff behind the count
The fill's rank is an integer between three and six across every separator two dense half-eliminations can afford, and this field has already recorded that a handful of such integers cannot carry a law. The singular values underneath are real numbers. They say the cliff's first step is 23.0 at a separator of eleven, 19.1 at fifteen and 16.2 at twenty-three — and that a control with no differential operator behind it gives 14,672.
The knob that moved two things
Decide how many digits the answer needs, divide by the condition number, and compress to that. It is the one rule licensed in advance here, and its two factors are not the independent inputs it reads as: the partition's leaf moves neither of them and moves the answer by nearly a factor of three, and the only knob here that raises κ halves the ranks while it does so.
The smaller cluster sets the rank
An oscillatory kernel block between two equal clusters needs a rank that grows without limit as they grow. Make the clusters unequal at the same separation ratio and the rank stops following the larger one: a target an eighth long against a source of four needs 8 columns where the square block of side four needs 33, and a target a third long against a source 130 wavelengths long needs 11. What decides the rank is the product of the two lengths over their distance — the Fresnel number, the count optics gives for the waves two apertures can exchange.
An offset that bends twice
A hierarchical matrix's cheapest leaf can be named by one build at a leaf of 8, and a rank guessed from the tolerance alone names it on smooth kernels and misses on oscillatory ones. The repair proposed was a term in the frequency: the oscillatory kernels sat two thirds of a rank and one and a half ranks above 1/r at frequencies 40 and 120, and the prediction was a fixed step each time the frequency triples. On five frequencies from 13⅓ to 1,080 the step is a third of a rank, then one, then one and a half, then a third again — a curve that bends twice. The last bend is the smallest blocks filling up: at the tightest tolerance every 8-wide block is at full rank from 360 on. No fixed term reproduces it, and the one build that reads it directly still names the cheapest leaf on thirteen cells of fifteen, never storing two per cent too much, where the uncorrected guess misses seven by up to nine.
Each halving reads its own width
A hierarchical matrix's cheapest leaf is found by halving it while the blocks the halving creates have rank below a quarter of the leaf. The proposal was to probe only the near blocks of one compression at a leaf of 8, predicted to do at least as well as the whole compression. It does worse: twelve cells of fifteen against thirteen, every miss naming 16 where 32 is cheapest, because the decision between 32 and 16 turns on whether a block reaches rank 8 and an 8-wide block cannot exceed it. Read each halving off the blocks of its own width instead and the probe names the cheapest leaf on all fifteen oscillatory cells and all thirty cells of six kernels, beating even the rule with every leaf compressed, from eighteen small blocks at under one per cent of the work of the compression it replaces.
Named alongside it
The objects these essays reach for when they reach for this one.
Off-diagonal rankNumerical rankAdmissibilityHierarchical matrixLow-rank approximationSeparable expansionSingular valuesSpectral decayToleranceAsymptotic analysisFourier modesGreens function