Simulating a system step by step is slow because each state depends on the previous one. Parallel-in-time solvers get around this: they guess the whole trajectory at once and repeatedly correct it with Newton's method. The exact Newton correction, however, needs the Jacobian of every time step, and for a $d$-dimensional state each Jacobian is a dense $d \times d$ matrix. Storing all of them for all time steps is the memory wall. Existing solvers escape it in one of two ways. ParaSolver pretends the Jacobian is the identity. Multiple shooting stores everything and accepts the cost. The first works when the dynamics damp errors and fails when they do not. The second stops scaling beyond a few hundred dimensions.
We propose a third route for dynamics that come from discretized differential equations, where each step's Jacobian is close to shift-invariant: a stencil with boundary effects. Such matrices have low displacement rank. That means the difference between the matrix and a shifted copy of itself is a low-rank matrix, so the whole $d \times d$ matrix can be stored as $O(dr)$ numbers and multiplied by a vector with FFTs. The plan has three parts. First, recover these compact "generators" for each step's Jacobian from a handful of automatic-differentiation probes. Second, compose them with a parallel prefix scan, which inverts the space-time Newton system in $O(\log N)$ depth over $N$ time steps. Third, recompress the generators after each composition. Memory drops from $O(Nd^2)$ to $O(Ndr)$, and the Newton corrections stay close to exact. Because the residual is always evaluated exactly, compression error slows convergence but does not change the answer.
Core Claim
For near-translation-invariant dynamics with non-periodic boundaries and smooth nonlinearities, products of step Jacobians keep a small numerical displacement rank. If that holds, near-exact parallel Newton becomes affordable at state dimensions where dense Jacobians cannot fit in memory. On oscillatory or non-dissipative problems, this should turn the roughly $N$ outer iterations that identity-Jacobian and Krylov solvers need into a small constant, with $O(\log N)$ parallel depth per iteration.
The new element is not using displacement structure to invert a single Toeplitz matrix. That is well understood. The new element is carrying displacement generators through the composition algebra of a parallel-in-time solver, with rank truncation, so that structured inversion becomes the device that sets where the solver sits on the memory-parallelism curve.
Where This Sits
Three papers already put the space-time system in view, and each leaves a specific opening.
ParaSolver casts diffusion sampling as a banded nonlinear system. It replaces the unit-diagonal Jacobian with the identity and handles GPU memory with a sliding window. It reports an 8.1× speedup on Stable Diffusion v2 (128.0 s down to 15.9 s, FID 55.3 against 55.9) on 8 RTX 3090s. Differentiable Multiple Shooting Layers solves a block-bidiagonal Newton system on boundary states. Its memory grows with the number of sub-intervals and the state dimension, and it reports being 3× faster than sequential baselines on a 200-dimensional Timoshenko beam. Tight two-level convergence of Linear Parareal and MGRIT uses the block Toeplitz structure of the time-stepping operator only to prove convergence bounds. It shows that hyperbolic problems need fine-grid steps that match coarse steps to $1/N_c$ accuracy, and that L-stable integrators are required. That result constrains any cheap approximate correction.
On the matrix side, several papers supply the method. Structured Transforms for Small-Footprint Deep Learning and Theoretical Properties for Neural Networks with Weight Matrices of Low Displacement Rank show that Toeplitz-like displacement-rank matrices are full-rank, expressive, and FFT-fast. A new Toeplitz inversion formula and Skew cyclic displacements and decompositions of inverse matrix write such matrices and their inverses as sums of products of circulant and skew-circulant factors. That is the reconstruction algebra we reuse. A Two-pronged Progress in Structured Dense Matrix Vector Multiplication and Faster Sparse Matrix Inversion keep inverses implicit in skinny generators, but only in exact arithmetic over finite fields. None of these papers composes structured matrices along a time axis. None faces floating-point truncation inside an iterative solver. We do both.
The motivation for caring about memory comes from PIADM, where sub-linear parallel time costs $O(d^2)$ space for the SDE variant. It also comes from parallel discrete diffusion, where halving network evaluations yields only 1.45–1.86× wall-clock gains on one GPU because of trajectory memory traffic.
Research Program
Sketching generators without forming Jacobians. Fix the Sylvester operator pair $(L, R) = (Z_1, Z_{-1})$, the cyclic and skew-cyclic down-shifts. For a step Jacobian $J$, the displacement is $E = Z_1 J - J Z_{-1}$. This operator is invertible because the two shifts have disjoint spectra. Applying $E$ to a probe vector $\omega$ costs two Jacobian-vector products, $Z_1(J\omega) - J(Z_{-1}\omega)$. Applying $E^\top$ costs two vector-Jacobian products. A randomized range finder with $r + p$ probes therefore returns generators $G, H \in \mathbb{R}^{d \times r}$ with $E \approx GH^\top$. The cost is $O(r)$ network or stencil evaluations per step, independent of $d$. $J$ is then applied as a sum of $r$ circulant-times-skew-circulant products via FFT.
Composing in a parallel scan. The linearized Newton update on the space-time system is the affine recursion $\delta_{k+1} = J_k \delta_k + c_k$. We solve it with an associative scan over pairs $(J, c)$, which gives $O(\log N)$ depth. The key algebraic fact is the product rule under this operator pair:
$$ Z_1 (AB) - (AB) Z_{-1} = (Z_1 A - A Z_{-1})\,B + A\,(Z_1 B - B Z_{-1}) + A\,(Z_{-1} - Z_1)\,B . $$
Since $Z_{-1} - Z_1$ has rank one, this identity gives $\operatorname{rank}(E_{AB}) \le r_A + r_B + 1$. Each composition is followed by recompression: a QR factorization of the stacked generators and an SVD of the small core, truncated at relative tolerance $\tau$. The cost is $O(dr^2)$ per composition. Peak memory is $O(Ndr)$, against $O(Nd^2)$ for a dense scan and $O(Nd)$ for identity-Jacobian Picard. The dial is $r$, now a principled knob between the two extremes.
Exactness and stability. Truncation makes each linear solve inexact. The outer Newton residual, though, is always the exact sequential-integrator residual, so the fixed point is the true sequential trajectory. We will measure how $\tau$ trades inner accuracy against outer iterations. We will also test whether truncated compositions stay forward stable on non-normal operators, the regime that the Toeplitz inversion analysis leaves open. For stiff problems requiring implicit steps, each step's $(I - hJ)^{-1}$ is itself inverted in structured form. This uses the fact that the inverse of a matrix of displacement rank $r$ under $(L, R)$ has rank $r$ under the swapped pair $(R, L)$, applied through the circulant and skew-circulant inversion formulas.
Known weakness, stated up front. A pointwise nonlinearity adds a diagonal term to the Jacobian. A diagonal matrix has high exact displacement rank under shifts. Its displacement is small in norm when the coefficient field is smooth, because it scales with grid spacing times the field's gradient, but it is not low-rank. Whether numerical rank stays small after truncation is therefore an empirical question. It is the first thing we test.
Baselines
The naive reference is the sequential integrator with the same step size and scheme. It sets both the target trajectory and the wall-clock time to beat. It also gives the memory floor of $O(d)$.
The strongest existing competitor on non-contractive dynamics is an identity-Jacobian parallel Newton/Picard solver in the style of ParaSolver. It is ported from diffusion to our PDE rollouts with the same banded formulation and a sliding window. It is the method to beat because it has the smallest memory and has shown the largest reported speedups (8.1× on Stable Diffusion v2, 12.1× on LSUN Church, 8 GPUs). It runs on the same 8-GPU budget with its window size tuned over the same grid we use for our rank $r$.
For multiple shooting, we run Differentiable Multiple Shooting Layers with dense block-bidiagonal Newton on its own Timoshenko beam setting. The reported reference point is 3× faster than sequential. We beat it if we match its accuracy with lower memory and at least equal speed at $d = 200$, and if we keep scaling at $d \ge 4096$ where it runs out of memory.
We also run two-level Parareal/MGRIT following Southworth et al., with an L-stable coarse integrator. On 2D wave and advection-diffusion that paper reports only that its bounds track observed convergence. No reported result was found on Lacuna for wall-clock time or memory on these equations, so we measure both ourselves.
Two oracles and one ablation complete the set. A dense-Jacobian scan, feasible only at small $d$, gives the exact-Newton oracle. A diagonal-Jacobian scan is the cheapest structured correction. The ablation that isolates our key ingredient is an identity-plus-low-rank correction $J \approx I + UV^\top$, fitted from the same probes with the same parameter budget $2dr$. If it matches us, displacement structure is not doing the work. All methods share step size, stopping tolerance on the exact residual, hardware (8× RTX 3090 to match ParaSolver), and a fixed tuning grid.
Why not just…?
Why not just use the identity Jacobian, as ParaSolver does? It works when the dynamics contract errors, which is why it succeeds on denoising. On wave-like dynamics, Southworth et al. show that coarse corrections must be accurate to $1/N_c$ or errors grow across the time grid. We predict the outer iteration count for $J \approx I$ grows roughly linearly with $N$ on the wave, beam, and KdV-type problems. On dissipative problems such as the heat equation, it is a real threat, and we expect it to win there. We include the heat equation as a negative control and will report the regime boundary honestly.
Why not just run Jacobian-free Newton–Krylov on the whole space-time system? It needs only vectors, so its memory is excellent. But the space-time matrix is the identity minus a strictly block-subdiagonal part. Its minimal polynomial can have degree $N$, so without contraction the Krylov solver may need close to $N$ parallel iterations. That recovers sequential depth. We will plot inner Krylov iterations against $N$ next to our scan depth. If Krylov iterations stay flat, the scan is unnecessary and we drop it.
Why not just use a low-rank Jacobian correction? Stencil Jacobians are full-rank, so a rank-$k$ correction to the identity misses most of the spectrum. Structured Transforms found displacement-rank-1 or rank-2 layers outperforming low-rank layers with 16× more parameters, though in a different setting. The matched-budget ablation above settles the question for our operators.
Why not just diagonalize with FFTs, or use a diagonal Jacobian? With periodic boundaries and constant coefficients, everything is circulant and trivially parallel in Fourier space, so we deliberately use Dirichlet or clamped boundaries and nonlinear terms. A diagonal Jacobian ignores exactly the spatial coupling that carries waves. It is included as a baseline, and we expect it to track $J \approx I$ on hyperbolic problems.
Proposed Experiments
The first experiment is a go/no-go study that costs little and decides the project. For the MSL Timoshenko beam (200-D), a 1D wave equation with Dirichlet boundaries, viscous Burgers, a nonlinear Klein–Gordon equation, and 1D advection-diffusion with non-recirculating flow, we compute exact step Jacobians at $d$ up to 2048. We then measure the singular value decay of the displacement $E$ for single steps and for products spanning $m = 1$ to $N$ steps. As the ordinary-low-rank control, we measure the singular value decay of $J - I$. If the truncated displacement rank at $\tau = 10^{-6}$ exceeds about $d/8$ for long products, the method loses its memory advantage and we stop. We also locate where along the smoothness spectrum of the nonlinearity this happens.
If the study passes, we run the full solvers at $d \in \{200, 1024, 4096, 16384\}$ and $N \in \{64, 256, 1024\}$. We report outer Newton iterations, parallel depth, wall-clock time, peak GPU memory, and final deviation from the sequential trajectory. At $d = 16384$, a dense Jacobian is about 1 GB per step and cannot be held over hundreds of steps, while generators at $r = 16$ are about 2 MB. This is the regime where only our method and the vector-only baselines can run. A 2D wave extension uses two-level shift operators, a known complication because single-index shifts give displacement rank proportional to $\sqrt{d}$.
As a stretch check we would apply the method to a neural ODE whose vector field uses displacement-rank weights, in the spirit of Theoretical Properties for Neural Networks with Weight Matrices of Low Displacement Rank. Generic diffusion-model U-Nets are not a target, since their Jacobians carry no shift structure and their contractivity already favors $J \approx I$.
Four results would be decisive. On wave-type problems, our outer iterations must stay near-constant in $N$ while identity-Jacobian and Krylov iterations grow. Our memory must stay within a small factor of $O(Nd)$ while the dense scan exceeds hardware at moderate $d$. The final trajectory must match the sequential solution to within the Newton tolerance, showing that truncation did not bias the result. And the matched-budget low-rank ablation must fall clearly short of the displacement version. Failing the last check would mean the idea is simply low-rank correction under a new name.
References
- ParaSolver: A Hierarchical Parallel Integral Solver for Diffusion Models
- Differentiable Multiple Shooting Layers
- Tight two-level convergence of Linear Parareal and MGRIT: Extensions and implications in practice
- Structured Transforms for Small-Footprint Deep Learning
- Theoretical Properties for Neural Networks with Weight Matrices of Low Displacement Rank
- A new Toeplitz inversion formula, stability analysis and the value
- Skew cyclic displacements and decompositions of inverse matrix for an innovative structure matrix
- A Two-pronged Progress in Structured Dense Matrix Vector Multiplication
- Faster Sparse Matrix Inversion and Rank Computation in Finite Fields
- Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity
- Accelerating Discrete Diffusion Models with Parallel-In-Time Sampling