Waveform Transmission Method, a New Waveform-relaxation Based Algorithm to Solve Ordinary Differential Equations in Parallel

Fei Wei, Huazhong YangarXiv 2009 · arXiv

Abstract

Solving large-scale systems of Ordinary Differential Equations (ODEs) is a significant computational challenge in fields such as circuit simulation and structural analysis. Traditional sequential time-stepping methods limit parallelization. This paper introduces the Waveform Transmission Method (WTM), a novel parallel algorithm that combines Waveform Relaxation (WR) with the network-splitting logic of the Virtual Transmission Method (VTM). By virtually inserting "waveform transmission lines" into dynamical systems, WTM enables distributed computing for sparse, symmetric positive definite systems.

Introduction

The simulation of complex dynamical systems often requires solving massive ODE systems. While Waveform Relaxation (WR) was proposed to solve systems over entire time windows rather than single points, its implementation in distributed environments remains challenging. The Waveform Transmission Method (WTM) addresses this by providing a physical analogy for system partitioning, allowing for natural parallelization through the concept of virtual microwave networks.

Methodology

WTM operates through a multi-step process designed to decouple large systems into manageable sub-problems:

  1. Graph Mapping: The ODE system is first mapped onto an electric graph where components represent mathematical relationships.
  2. Electric Vertex Splitting (EVS): The graph is partitioned along specific boundaries into $n$ smaller subgraphs.
  3. Virtual Insertion: To maintain the original system's dynamics, a Waveform Transmission Line (WTL) is inserted between the split "twin" vertices.
  4. Distributed Iteration: Each subgraph is assigned to a separate processor. Waveforms are transferred bidirectionally across the virtual lines in an iterative process similar to Gauss-Jacobi, but operating on entire time windows $[T_1, T_2]$.
The Waveform Transmission Line (WTL) serves as the iterative communication bridge between partitioned sub-problems.

The WTL is characterized by a "characteristic impedance" $Z(t)$, which the authors suggest can be tuned as a preconditioner to improve performance and speed up convergence.

Experimental Validation

The method was validated using a simple capacitive-resistive (RC) network as a proof-of-concept. This toy example allows for a clear demonstration of the splitting process and verification of numerical convergence.

Evolution of a system from a unified RC network (A) to a partitioned state (B) and finally a WTM-ready configuration with a virtual transmission line (C).

Results and Discussion

Theoretical analysis proves that WTM is guaranteed to converge for linear Symmetric Positive Definite (SPD) ODE systems. Numerical experiments on the RC network confirmed that the maximum waveform error consistently decreases over iterations, reaching the same solution as the unified system.

However, the authors note that the current convergence speed and precision are not yet competitive with the original VTM for linear systems. This suggests that the method is in its early stages, with significant potential for optimization through better selection of the impedance $Z(t)$.

Conclusion and Future Work

WTM offers a robust framework for parallel ODE solving by leveraging microwave network analogies. Its bidirected waveform transfer makes it a natural fit for modern parallel hardware. Future research will focus on improving the efficiency of impedance selection and extending the method's application to large-scale nonlinear dynamical systems.

Summary updated

BibTeX
@misc{wei2009waveform,
  author = {Fei Wei and Huazhong Yang},
  title = {{Waveform Transmission Method, a New Waveform-relaxation Based Algorithm to Solve Ordinary Differential Equations in Parallel}},
  year = {2009},
  eprint = {0911.1166},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0911.1166},
}
Figure