Waveform relaxation as a dynamical system

Morten Bjørhus, Andrew M. StuartMath. Comput 1997 · DOI · OpenReview

Introduction

Waveform relaxation (WR) is a powerful iterative technique used to solve large-scale systems of ordinary differential equations (ODEs). By decomposing a system into smaller subsystems and iterating on entire "waveforms" over a time interval, WR enables efficient parallel computation—a necessity for simulating complex electrical circuits, chemical reactions, and biological networks.

While the convergence of WR over finite time intervals is well-understood, its behavior over long-term or infinite horizons has historically remained a gray area. This paper provides a rigorous mathematical bridge between WR and dynamical systems theory, proving that "windowed" waveform relaxation accurately preserves the qualitative features of the underlying physics, such as steady states, periodic orbits, and strange attractors.

The Challenge of Long-Term Stability

In numerical analysis, a primary concern is whether an iterative method introduces "spurious" or "ghost" behaviors that do not exist in the original system. For instance, does the iterative nature of WR cause the solution to drift away from a true equilibrium? Does it fail to capture the chaotic topology of a system like the Lorenz attractor?

Most existing theory focuses on the contraction of the WR operator in a specific functional space over a fixed, finite time interval. This paper shifts the focus toward the qualitative dynamics of the system, treating the iterative process itself as a dynamical system to determine if the long-term "shape" of the solution remains intact.

Methodology: The Discrete Map Approach

The authors analyze windowed waveform relaxation, where the simulation timeline is divided into windows of length $T$. In each window, the algorithm performs a fixed number of iterations ($k$) before using the final state as the initial condition for the next window.

The key innovation lies in defining this process as a discrete dynamical system. The authors construct a "time $T$ map" that represents the transition from the start of a window to its end after $k$ iterations. To prove the reliability of this map, they establish its $C^1$-closeness to the true flow of the differential equation. This means that not only is the output of the WR map close to the true solution, but its derivative—how the output responds to small perturbations in the input—is also close. This $C^1$ convergence is the essential "secret sauce" that allows the application of powerful theorems from structural stability and dynamical systems theory.

Key Theoretical Insights

The paper presents several critical findings regarding the fidelity of the WR scheme:

  1. Preservation of Equilibria (Theorem 3.1): The authors prove that the steady states (equilibria) of the WR scheme are identical to those of the original physical system. There are no spurious equilibria created by the iteration process.
  2. Shadowing and Hyperbolicity: Due to $C^1$-closeness, the WR scheme accurately "shadows" the hyperbolic structures of the original system. If the true system has a saddle point where paths approach and then diverge, the WR map will exhibit the same geometric behavior.
  3. Manifold and Cycle Preservation (Theorems 3.7 & 4.1): The research demonstrates that local unstable manifolds and periodic solutions (limit cycles) are preserved within an error bound that diminishes as the number of iterations $k$ increases.
  4. Attractor Convergence (Theorem 4.3): For chaotic systems, the authors prove that the attractor generated by the WR map converges to the true attractor (in the sense of Hausdorff distance) as the iteration count grows.

Numerical Validation: The Lorenz Attractor

To validate these theoretical proofs, the authors apply the WR scheme to the classic Lorenz Equations. The Lorenz system is famous for its "strange attractor," a butterfly-shaped fractal structure that is highly sensitive to initial conditions.

Even when using a relatively simple Picard splitting (a common but sometimes "crude" iteration method), the WR scheme successfully reconstructs the iconic butterfly shape. This visual evidence confirms that the iterative method does not collapse the chaotic structure or drift into non-physical states, provided the windowing and iteration counts are handled according to the paper's framework.

Limitations and Future Work

While the paper establishes a robust foundation, it identifies three main areas for future research:

  • Global Lipschitz Conditions: The current proofs assume the system's functions do not grow faster than a linear rate (global Lipschitz). While common in proofs, real-world systems often only satisfy these conditions locally.
  • Numerical Discretization: The analysis treats WR iterations as exact mathematical functions. In practice, each iteration is solved using a numerical integrator (like Runge-Kutta). The authors suggest that the combined error of WR and discretization should behave predictably, but a formal proof remains for future work.
  • Adaptive Algorithms: The study uses fixed window sizes ($T$) and iteration counts ($k$). Modern simulation software often adjusts these parameters dynamically. Extending this dynamical systems viewpoint to adaptive WR algorithms is a significant open challenge.

Conclusion

This research provides the necessary theoretical justification for using waveform relaxation in long-term simulations. By proving that windowed WR is $C^1$-close to the true underlying flow, the authors ensure that the qualitative "soul" of a dynamical system—its attractors, cycles, and stability—is preserved through the iterative process.

Summary updated

Abstract

: In this paper the properties of waveform relaxation are studied when applied to the dynamical system generated by an autonomous ordinary differential equation. In particular, the effect of the waveform relaxation on the invariant sets of the flow is analysed. Windowed waveform relaxation is studied, whereby the iterative technique is applied on successive time intervals of length $T$ and a fixed, finite, number of iterations taken on each window. This process does not generate a dynamical system on $\mathbb {R}^+$ since two different applications of the waveform algorithm over different time intervals do not, in general, commute. In order to generate a dynamical system it is necessary to consider the time $T$ map generated by the relaxation process. This is done, and $C^1$-closeness of the resulting map to the time $T$ map of the underlying ordinary differential equation is established. Using this, various results from the theory of dynamical systems are applied, and the results discussed.
BibTeX
@article{bjrhus1997waveform,
  author = {Morten Bjørhus and Andrew M. Stuart},
  title = {{Waveform relaxation as a dynamical system}},
  journal = {Math. Comput.},
  year = {1997},
  doi = {10.1090/s0025-5718-97-00847-8},
}
Figure