Sizing RBF-FD Stencils for Modern CPU Caches

Interactive version: the RBF-FD Stencil Sizer computes the sizes below for any polynomial degree, dimension and precision, and checks the footprint against L1/L2 caches or GPU shared memory.

One of the benefits of the RBF-FD methods compared to grid-based finite differences is it is straightforward to change the order of accuracy via the augmented polynomials. The number of monomial terms in the augmented polynomial basis is given by the triangular numbers in 2-d and the tetrahedral numbers in 3-d. For a basis complete through total degree $p$ there are $(p+1)(p+2)/2$ terms in 2-d and $(p+1)(p+2)(p+3)/6$ terms in 3-d. The number of terms can also be read from Pascal’s triangle/pyramid.

For the RBF stencil size a common heuristic is to use twice the number of polynomials terms. This rule of thumb goes back to Flyer, Barnett, and Wicker (2016). While it is a standard starting point for stencil sizing, the relationship between accuracy, computational time, and monomial augmentation remains an active area of research. Readers can find more information in the analysis by Jančič, Slak, and Kosec (2021) and citing works. For a broad study of how the many RBF-FD parameters interact — stencil size, polynomial degree, RBF choice, node distribution — Le Borne and Leinen (2023) is a good source.

The tables below show how the RBF-FD matrix dimensions varies for 2-D and 3-D RBF-FD approximation. We also include the storage size of the matrices for 32- and 64-bit floats.

2-D RBF-FD approximation

3-D RBF-FD approximation

When computing the RBF-FD approximation weights via LU factorization or other forms of factorization (i.e. block Cholesky) the matrix will reside in the L1 or L2 cache. The maximum matrix size that fits in cache also depends on the number of right-hand sides (operators) being solved simultaneously, as those vectors must also share the cache.

Here are the L1 data cache sizes of a few recent CPU architectures:

The figure below plots the matrix storage against polynomial order up to 12, with the L1 data cache sizes drawn as horizontal references. Storage scales with the square of the number of polynomial terms, so the vertical axis is logarithmic.

For polynomials below order 6 in 2D (or 4 in 3D) the RBF-FD matrices fit comfortably in the lowest cache level. The Apple M-series and recent ARM servers like the Nvidia Grace or Fujitsu A64FX have a slight advantage due to the larger L1 cache sizes. Intel and AMD CPUs used 32 KB L1 data caches for more than a decade. AMD increased the size only recently with the Zen 5 series launched in 2024. Intel made the upgrade from 32 KB to 48 KB in the Sunny Cove architecture launched in 2019.

(Note: Apples’s efficiency cores (E-cores) use smaller 64 kB L1D caches. Intel’s efficiency cores have remained at 32 kB L1 data caches. )

Correction (2026-08-30): the monomial counts in the tables and the figure were originally shifted by one order — the row labelled order $p$ held the count for degree $p-1$, so order 2 in 2-D showed 3 terms instead of 6. The tables and figure have been recomputed, which moves the cache-fit thresholds down by one order as well. The stencil-size heuristic was also misattributed to Grady Wright; it originates with Flyer, Barnett, and Wicker.

Update (2026-08-30): added the RBF-FD Stencil Sizer linked at the top, inspired by the layer condition calculator from RRZE (sources).