Fast stencil calculations on one moving interval in one dimension
Fast Stencil Computations on a Single Arbitrarily Moving Interval
Data Structures and AlgorithmsDistributed, Parallel, and Cluster Computing
Summary
Stencil computations update each point in a line based on its neighbors repeatedly over time, which can be very slow for large grids and many steps. The authors studied a special case where the points being updated form a single moving continuous region, which can shift unpredictably. They developed a new way to compute the updates much faster, even when the region moves arbitrarily, without losing exactness. Their method’s efficiency depends on how much the region's boundaries change over time, making it practical for many cases where previous methods required slow or limited movement.
What this means in practice
- •For numerical simulation engineers: Efficiently simulate dynamic one-dimensional processes where the region of interest changes shape or size unpredictably, speeding up stencil-based calculations.
- •For computer graphics developers: Accelerate computations for one-dimensional effects or signals where active intervals move arbitrarily, enabling faster real-time rendering or filtering.
A theory result. No direct application yet.
Authors
Aaron Gregory
Abstract
A stencil computation repeatedly updates every cell of a grid from its neighbours' values at the previous timestep. Simulating T steps on N cells directly costs Theta(NT), and a line of work beginning with Ahmad et al. reduces this by composing many timesteps into one linear operator and applying it with a Fast Fourier Transform. That technique needs to know which cells will still obey the same operator when the composed step ends, and in a free-boundary problem they do not: the region governed by a given rule is determined by the solution and moves as it evolves. We study 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. Let B be the horizon plus the total variation of the boundary trajectory. We give a schedule whose work is O((B+N) log T log(N+B)) and whose span is O(T log T log(N+B)), and we prove that the values it computes are exact. The best existing bound for a region that moves requires its boundary to travel at most one cell per timestep. We drop that requirement and lose nothing by it: a boundary obeying it has B <= 3T, so our bound stays near-linear on every trajectory the earlier result covers. Elsewhere, B grows only by the distance the boundary actually travels -- one jump of width N costs T + 2N. The reason total variation suffices is that everything the two endpoints touch over a time window of any length lies in two intervals, one per endpoint. This cannot be relaxed: with p regions the bound degrades by a factor p, and at p = sqrt(T) there is an instance on which the work is Theta(T^{3/2}) while B + N = Theta(T). All results are machine-checked in Lean 4, apart from the classical convolution bound, which is imported as an interface.