Temporal Parallelization for Dynamical Systems

This direction is split into other directions: CTL model checking complexity, sequential time-stepping bottleneck. Its last version stays readable and citable here.

Version 1 of 1156 papers168 conceptsfrozen 2026-10-04

In the world of high-performance computing, we are accustomed to "spatial" parallelization—splitting a physical domain into chunks and assigning each to a different processor. However, time-dependent problems, such as fluid simulations, robotic control, and state estimation, have long been plagued by a "sequential bottleneck." Because the state at time $t+1$ depends strictly on the state at time $t$, we traditionally compute trajectories one step at a time, leaving modern GPUs and supercomputers largely underutilized.

Recent research has converged on a powerful realization: the temporal dimension is not inherently serial. By reframing differential equations and state-space models as global optimization problems or associative operations, we can break the $O(T)$ linear dependency and achieve $O(\log T)$ logarithmic complexity.

The Associative Scan: From $O(T)$ to $O(\log T)$

The most intuitive way to understand temporal parallelization is through the lens of the associative scan (or prefix-sum). In a standard Kalman filter or Bayesian smoother, we process data chronologically. Ángel F. García-Fernández and Simo Särkkä demonstrate in Temporal Parallelization of Bayesian Smoothers that these filters can be reformulated as a sequence of associative operations.

Imagine you need to calculate the sum of eight numbers. You could add them one by one (sequential), or you could add pairs in parallel (1+2, 3+4, etc.), then add the results of those pairs. This tree-based reduction is the heart of the "prefix-sum" approach. Särkkä applies this to Parallel Kalman Filters and Smoothers, showing that if the transition between time steps can be represented as an associative operator, a GPU can resolve the entire trajectory in logarithmic time. This same logic allows Hamideh Razavi and colleagues to achieve massive speedups in Maximum-A-Posteriori (MAP) trajectory estimation.

Predictor-Corrector Parallelism: The Parareal Framework

When the underlying physics is non-linear or complex, we cannot always find a simple associative operator. In these cases, researchers use the Parareal algorithm. The intuition here is to use two solvers:

  1. A Coarse Solver: A "cheap," inaccurate model that runs sequentially to provide a rough sketch of the entire trajectory.
  2. A Fine Solver: An "expensive," accurate model that runs in parallel across different time intervals, using the coarse sketch as its starting point.

The algorithm then iterates, using the errors from the fine solvers to "correct" the coarse trajectory. Kamran Pentland and Massimiliano Tamborrino have pushed this further with GParareal, which replaces the standard correction step with a Gaussian Process emulator. By learning from previous iterations, the emulator allows the system to converge much faster than traditional Parareal, effectively "learning" the dynamics of the system while solving it.

All-at-Once: Treating Time as Space

Another dominant strategy is the "all-at-once" approach. Instead of stepping through time, we treat the entire space-time volume as a single, massive system of equations.

In AIR Algebraic Multigrid for a Space-Time Hybridizable Discontinuous Galerkin Discretization, Ben S. Southworth shows that by treating the temporal dimension just like a spatial dimension, we can use multigrid solvers to resolve all time steps simultaneously. To make this computationally feasible, researchers like Yunhui He develop specialized preconditioners, such as the Vanka-type multigrid solver, which handle the complex-shifted systems that arise when you discretize time and space together.

Parallel Control and Robotics

The sequential bottleneck is particularly painful in robotics, where the Linear Quadratic Regulator (LQR) and Riccati recursion are standard tools. Traditional Riccati solvers are strictly serial. However, Claire Tomlin and Forrest Laine introduced a method to parallelize Riccati recursion that maintains the feedback policies necessary for stability.

Similarly, Bo Yu and Jie Tang have moved toward hardware-level acceleration. In FGLQR, they re-envision LQR as a factor graph optimization. By representing the temporal dependencies as edges in a graph, they can use parallel message-passing algorithms on FPGAs to solve control problems at frequencies far beyond what a serial CPU could manage.

Spectral and Neural Shortcuts

Finally, a new class of "fast-forward" methods avoids time-stepping altogether. Alessio Quaglino and colleagues introduced SNODE, which represents Neural ODE trajectories as a sum of Legendre polynomials. Instead of integrating step-by-step, the model solves for the polynomial coefficients that satisfy the ODE across the entire time window at once.

In the realm of physics-informed machine learning, Xiao Xue and others use Physics-Informed Neural Operators (PINOs) to "leap" across time. By training a neural network to map an initial state directly to a distant future state, they bypass the need for millions of intermediate, stability-constrained time steps required by traditional solvers like the Lattice Boltzmann method.

Summary

The transition from sequential time-stepping to temporal parallelization represents a fundamental shift in how we simulate and control the world. Whether through associative scans that turn chains into trees, Parareal iterations that use coarse guesses to enable fine parallel work, or all-at-once multigrid methods that treat time as a fourth spatial dimension, the goal remains the same: breaking the $O(T)$ barrier to unlock the full potential of parallel hardware.

Papers in this version

Showing 60 of 156 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_temporal_parallelization_for_dynamical_s_404541fc,
  title = {Temporal Parallelization for Dynamical Systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/temporal-parallelization-for-dynamical-systems/rdr_404541fc14804fd4808443bd72cf10f4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_temporal_parallelization_for_dynamical_s_404541fc_v1,
  title = {Temporal Parallelization for Dynamical Systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/temporal-parallelization-for-dynamical-systems/rdr_404541fc14804fd4808443bd72cf10f4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}