Cache-Oblivious Schedules for Structured Matrix-Vector Products

Many fast algorithms for "structured" dense matrices are judged only by how few arithmetic operations they use. These include Toeplitz-like and Cauchy-like matrices, learned low-displacement-rank layers in neural networks, and tree distance kernels. Once the matrix's compact description no longer fits in cache or RAM, that count stops predicting speed. The cost that matters then is how many blocks of data move between levels of memory. This proposal asks a question that the three input directions each approach from one side but none answers.

The question is: how many block transfers does a structured matrix-vector product need, and can one recursive schedule reach that number on every cache level at once without being told the cache sizes? The concrete claim is this. The recursive algorithm for matrices of low recurrence width reorganises the partial results computed at each level of its recursion, which live in a product tree. If it is executed depth-first, with that product tree stored in a recursive contiguous layout, it becomes cache-oblivious. Its transfer cost is then within one logarithmic factor of the external sorting bound. Recurrence width is a single number measuring how compactly a matrix can be generated by a short recurrence; it covers Toeplitz, Vandermonde, Cauchy, quasiseparable and learned-operator matrices. We also ask whether that extra logarithm is necessary. The same schedule applies directly to the recursive separator tree used by fast tree-field integrators.

Where the directions meet

Displacement structure is the core object. A matrix $A$ has low displacement rank if $LA - AR$ has small rank $r$ for fixed operator matrices $L, R$, so $A$ is described by $O(rN)$ numbers instead of $N^2$. Structured Transforms for Small-Footprint Deep Learning used this with fixed shift operators and FFTs to compress layers. Learning Compressed Transforms with Low Displacement Rank made the operators themselves learnable, with subdiagonal (LDR-SD) and tridiagonal (LDR-TD) variants. A Two-pronged Progress in Structured Dense Matrix Vector Multiplication. unified displacement and rank structure under recurrence width $t$. It gave a divide-and-conquer algorithm computing $Ab$ in $O(t^2 M(N)\log N)$ operations, where $M(N)$ is the cost of multiplying two degree-$N$ polynomials. Fast Tree-Field Integrators showed that kernel matrices $f(\mathrm{dist}(i,j))$ on trees have low-displacement-rank cross blocks across balanced separators, and evaluated them by a similar recursion. None of these papers models memory transfers. That gap motivates this work.

Cache-oblivious design supplies the method. Algorithms that recurse until subproblems fit, without ever knowing the cache size $M$ or block size $B$, are optimal at every level of the memory hierarchy at once. This is the premise behind Cache-Oblivious Query Processing and the van Emde Boas tree layout. Cache-Oblivious VAT-Algorithms constrains the design: recursive layouts can thrash the address-translation buffer unless the ratio $M/B$ is reasonable, so we must measure translation misses rather than assume them away.

External-memory priority-queue complexity supplies the lens. Equivalence between Priority Queues and Sorting in External Memory shows that insert-and-extract queues cost exactly the sorting bound per operation. DecreaseKeys are expensive for external memory priority queues proves that adding in-place priority updates forces a strictly larger cost, and A Faster External Memory Priority Queue with DecreaseKeys matches that cost with a cache-aware structure. The lesson we borrow is to ask of each primitive whether it is "sorting-equivalent" in I/O or strictly harder, and to answer with both a matching algorithm and a restricted lower bound. We do not build a priority queue.

Core Claim

Write $\mathrm{Sort}(N) = \frac{N}{B}\log_{M/B}\frac{N}{B}$ for the cost of external sorting. Consider the recurrence-width algorithm executed depth-first. Its polynomial-matrix products are computed by a cache-oblivious FFT convolution, and its product tree is stored so that every subtree occupies a contiguous region. We conjecture it incurs

$$ Q(N) = O\!\left(t^2 \,\mathrm{Sort}(N)\,\log\frac{N}{M}\right) $$

block transfers for $Ab$, $A^T b$, and the analogous cost for $A^{-1}b$. The form has a simple source. Levels of the recursion whose subproblems fit in memory cost only a scan, and there are $\log(N/M)$ levels above that threshold. Each of those levels does polynomial work of total size $O(t^2 N)$, and each costs a sorting bound through FFT. The current breadth-first, pointer-based implementations pay a transfer for nearly every level and every tree node. That is roughly $t^2 \frac{N}{B}\log N$ transfers or worse once the product tree spills out of cache.

The second half of the claim is a lower bound for the family of algorithms that compute $Ab$ through the recurrence's product tree. The argument would follow the computation-graph technique that On the I/O Complexity of the Cocke-Younger-Kasami Algorithm used for a family of dynamic programs. We would show that the $\log(N/M)$ factor cannot be removed within this family. That would give structured matrix-vector multiplication its own analogue of the priority-queue-with-updates separation: sorting-equivalent for fixed-operator Toeplitz/Cauchy cases that reduce to a constant number of FFTs, strictly harder for general recurrence width. If the lower bound fails, the failure tells us something too: a flatter schedule exists, and we would look for it.

Research Program

The work has three parts, each done first for the recurrence-width algorithm and then carried over to tree-field integration.

The first part is analysis in the ideal-cache model. We fix a recursive layout for the product tree in which a node's polynomial-matrix coefficients are stored with its subtree. We prove the upper bound, including the cost of the "transitional" polynomial products at each level, the cost of their transposed counterparts for $A^T b$, and the two-pass structure for $A^{-1}b$. We then prove the lower bound for product-tree algorithms, by counting how many intermediate polynomials of each level must be simultaneously live in memory.

The second part is implementation. We re-implement the published C++ algorithm with the depth-first schedule and recursive layout. It keeps a single base-case cutoff chosen by the recursion itself: we recurse to size 1 and fuse small nodes into dense kernels at a size fixed independently of the hardware. That keeps the code oblivious. The same code path serves LDR-SD layers, whose operators embed in recurrence width. For LDR-TD, which the Thomas et al. paper runs in $O(N^2)$ because no fast algorithm is known, we only measure whether the cache-oblivious dense fallback narrows the gap. We do not claim a fast algorithm.

The third part is the tree-field transfer. The IntegratorTree of Fast Tree-Field Integrators recurses on balanced separators and applies Cauchy- or Vandermonde-like cross products at each node. That is structurally the same product tree, so the layout and bound should carry over with $t$ replaced by the kernel's displacement rank. This matters because mesh and graph kernels are the most natural place where $N$ reaches millions.

Baselines

The naive reference point is dense matrix-vector multiplication with a vendor-tuned BLAS routine. It is what practitioners use, and it wins at small $N$: Structured Transforms for Small-Footprint Deep Learning reports that FFT-based structured products are slower than dense ones below roughly $N \le 512$. We run it on the same matrices, materialised, up to the size where they fit in RAM. Our method beats this baseline if the crossover dimension moves lower and the gap widens with $N$.

The strongest existing method for general recurrence width is the published divide-and-conquer implementation of Recurrence Width for Structured Dense Matrix Vector Multiplication.. On its synthetic benchmark up to $N = 10{,}000$ it reports matrix-vector products "3x to 10x faster" than brute force, and preprocessing about "70x faster". We run it unchanged, using the same matrices, compiler, thread count and machine, and give both codes the same small search over the dense-fusion cutoff. Beating it means fewer measured last-level-cache misses and lower wall-clock time at $N = 10{,}000$. It also means a gap that grows with $N$ as the analysis predicts once $N$ exceeds last-level cache. A win only at one size would not count.

For tree fields the strongest method is the original IntegratorTree code. The paper reports "5.7x and 13x" speedups over brute force on graphs of 10,000 to 20,000 nodes. We compare on the same Thingi10K meshes and on larger meshes it did not test.

For fixed-operator Toeplitz-like layers the strongest competitor is the FFT route with a well-tuned FFT library. We treat it as an upper-bar baseline, discussed below.

A cache-aware competitor tunes tile sizes of the product tree to the measured L2 and L3 sizes of each machine. The same schedule in cache-aware form tests whether obliviousness costs anything.

Two ablations isolate the key ingredient. One keeps the depth-first schedule but uses the original level-order memory layout. The other keeps the recursive layout with the breadth-first schedule. If either ablation alone recovers most of the gain, the claim that layout and schedule must go together is wrong.

Why not just…?

Why not just use a cache-oblivious FFT for everything? For Toeplitz-, Hankel- and fixed-shift Cauchy-like matrices this probably does work as well. Those products reduce to a constant number of FFTs, so they are already sorting-equivalent, and we concede that case outright. Our claim is restricted to learned operators and general recurrence width. There the algorithm is a tree of polynomial-matrix products, and the unresolved cost is moving the tree's intermediate results, not the FFTs inside each node. The Toeplitz baseline shows the size of that difference: if our general method comes within a small constant of pure FFT on Toeplitz inputs and far ahead of the original code on quasiseparable and learned-operator inputs, the restriction is justified.

Why not just tune tiles to the hardware? Cache-aware tuning can match us on one machine. Cache-Oblivious Query Processing and Cache-Oblivious VAT-Algorithms document that such tuning is brittle across machines and memory levels. We test this directly. We tune on one CPU and run on two others, and we also run out-of-core on SSD, where the relevant block size is completely different. If the tuned version still wins everywhere, the value of obliviousness here is small, and we will report that.

Why not just use low-rank factors, which run on tuned matrix libraries? Structured Transforms for Small-Footprint Deep Learning found displacement rank 1–2 layers beat low-rank bottlenecks that used 16× more parameters. Fast Tree-Field Integrators notes its low-displacement-rank kernels are exact, whereas low-rank approximations are not. The question here is how to execute structured matrices efficiently, not whether to use them. Our results say nothing new about accuracy.

Why not just attack the cache-oblivious DecreaseKey priority queue instead? That is the obvious open problem named by A Faster External Memory Priority Queue with DecreaseKeys. Its branching factor, buffers and filters are all set from $B$ and $M$, and it has no empirical footprint to test against. We use its separation style as a lens. We take on a problem where both a bound and a measured speedup can be delivered.

Proposed Experiments

The experiments settle three things: whether the bound's shape shows up in practice, whether the benefit is real outside simulation, and whether it extends to tree fields.

To test the bound's shape, we run all codes in an ideal-cache simulator across a grid of $(M, B)$ and $N$ from $10^3$ to $10^7$, for recurrence widths $t \in \{1,2,4\}$. We check that measured transfers track $t^2\,\mathrm{Sort}(N)\log(N/M)$ and that the original schedule tracks the worse curve. Hardware-counter measurements of cache and translation misses on three CPUs follow.

To test the practical benefit, we run out-of-core products on SSD with RAM capped below the matrix description, and we time LDR-SD layers at widths above 4096. At those widths the Sindhwani et al. paper reports "10x to 100x" arithmetic speedups; we check whether they survive memory pressure. Accuracy on CIFAR-10 and WikiText-2 is recorded only to confirm the arithmetic is unchanged.

To test the tree-field extension, we measure integration time on Thingi10K meshes against the published IntegratorTree implementation.

The theory is decisive if the product-tree lower bound holds. The experiments are decisive if the gain over the published recurrence-width code grows with $N/M$ and survives both ablations.