Fast Stencil Computations on a Single Arbitrarily Moving Interval

Stencil computations update each cell of a grid from its neighbors' values at the previous timestep. Simulating T steps on N cells directly costs $\Theta (NT)$. A line of work beginning with Ahmad et al. reduces this cost by composing many timesteps into a single linear operator and applying it via Fast Fourier Transform (FFT). However, this technique requires knowing which cells will still obey the same operator when the composed step ends. In free-boundary problems, this region is determined by the solution and moves as it evolves, making the composition challenging.

This paper studies one spatial dimension, a three-point stencil with time-varying coefficients, and a computed region that is a single interval whose two endpoints move by arbitrary amounts at every step, revealed online. The key parameter is $B$, the horizon plus the total variation of the boundary trajectory. The main result is a schedule with work $O((B+N)\log T\log (N+B))$ and span $O(T\log T\log (N+B))$, with exact computed values. This improves upon the best existing bound, which required the boundary to travel at most one cell per timestep. The new bound remains near-linear on every trajectory covered by the

The main result is a schedule with work $O((B+N)\log T\log (N+B))$ and span $O(T\log T\log (N+B))$, where $B$ is the horizon plus the total variation of the boundary trajectory. The computed values are exact. This improves upon the previous best bound, which required the boundary to move at most one cell per timestep. For boundaries obeying that restriction, $B\le 3T$, so the new bound is near-linear on all trajectories covered by the earlier result. In general, $B$ grows only by the distance the boundary actually travels; for example, one jump of width $N$ costs $T+2N$.

The bound is tight in the sense that with $p$ regions, the work degrades by a factor $p$. At $p=\sqrt{T}$, there is an instance where the work is $\Theta (T^{3/2})$ while $B+N=\Theta (T)$. This shows that the total variation approach cannot be relaxed to multiple regions without loss.

All results are machine-checked in Lean 4, except the classical convolution bound, which is imported as an interface. This provides high confidence in the correctness of the proofs.