no. 17 · Wednesday 18 November 2026
Forests of Omnitrees: Analysis and Applications to Anisotropic Space–Time Finite Elements
Abstract
We prove output-optimal work bounds for omnitree forests, which bisect cells along selected axes. A canonical descriptor characterizes representable partitions independently of split order. Complete one-level cycles, including coarsening, face balance and selected coarse meshes, take sequential work proportional to stored input and output at fixed dimension and key width, with polynomial depth dependence even for unbalanced input. From balanced input, refinement-only balance stays within each request's coordinate slab; this bound is attained. Polynomial trace equations characterize conforming high-order spaces across crossed face partitions. Reconstruction moments bound interpolation errors and capture the logarithmic loss that bilinear nodal interpolation can suffer on balanced meshes. Elements of degree up to four resolve moving heat layers on unstructured 4D space-time and 5D space-time-parameter meshes. Multigrid uses the generated hierarchies.
- fields
- Numerical Analysis