Relative Schwarz Method

Fei Wei, Anna ZhaoarXiv 2022 · DOI · arXiv

Abstract

Traditional Domain Decomposition Methods (DDM) for solving wave equations, such as Schwarz Waveform Relaxation (SWR), typically rely on iterative processes to achieve convergence between subdomains. These iterations often introduce significant computational overhead and require complex preconditioning. This paper introduces the Relative Schwarz Waveform Relaxation (RSWR) algorithm, a novel non-iterative approach that leverages the physical principle of finite wave propagation speed. By synchronizing subdomains within a specific "validity window," RSWR achieves high-precision results in a fixed three-step process. Numerical simulations of 1D wave equations demonstrate that the method achieves near-machine-epsilon accuracy and maintains scalability across multiple subdomains.

Introduction

Solving large-scale physical problems, such as wave propagation in complex media, necessitates the use of Domain Decomposition Methods (DDM). These methods partition a global domain into smaller, manageable subdomains that can be processed in parallel. A prominent class of DDM is Schwarz Waveform Relaxation (SWR), which involves exchanging waveforms—time-dependent data—across subdomain boundaries.

Despite its popularity, traditional SWR is inherently iterative. Subdomains must repeatedly exchange information until the global solution stabilizes, a process that can be slow and computationally expensive. To address these inefficiencies, the authors propose the Relative Schwarz Waveform Relaxation (RSWR) method. Inspired by the physical constraints of wave velocity, RSWR aims to provide a direct, non-iterative solution to the wave equation, significantly reducing the communication and calculation cycles required for distributed computing.

Methodology

The RSWR algorithm is built on the observation that information in a wave equation cannot travel faster than a specific velocity ($a$). This physical limit implies that for a given duration, the solution in the interior of a subdomain is independent of boundary changes that have not yet had time to propagate inward.

The Predict-Select-Update Strategy

RSWR replaces the standard "guess-and-check" iteration with a structured three-step strategy:

  1. Prediction: Each subdomain independently calculates a local solution over a defined time interval. For the initial step, boundary inputs from neighboring subdomains are assumed to be zero.
  2. Selection: The algorithm identifies a Maximum Waveform Time Span ($\Delta T_{max}$). Based on Theorem 2.11, this span is defined as $\Delta T_{max} < \Delta X_{overlap} / 2a$, where $\Delta X_{overlap}$ is the width of the overlap between subdomains. Within this window, the error introduced by the initial boundary assumption has not yet reached the interior overlap region, ensuring that predicted solutions from adjacent subdomains are consistent.
  3. Update: The algorithm extracts the valid portion of the waveform and updates the global solution.

By utilizing this "validity window," the method ensures that the subdomains are synchronized based on the physical limits of wave transmission rather than mathematical convergence criteria.

Experimental Results

The authors evaluated the RSWR algorithm through numerical experiments focusing on 1D wave equations and dynamic pulse sources.

Precision and Accuracy

In experiments involving two subdomains ($N=2$), the RSWR method demonstrated exceptional numerical precision. The total error recorded was in the range of $10^{-14}$, which is near machine epsilon. This suggests that the method is effectively exact for the linear wave equation within the constraints of floating-point arithmetic.

Scalability

To test the robustness of the algorithm in distributed environments, the researchers extended the simulation to ten subdomains ($N=10$). The results indicated that the method maintains its accuracy and non-iterative nature as the number of subdomains increases. This scalability suggests that RSWR is well-suited for high-performance computing (HPC) architectures where minimizing iteration-related communication is critical.

Discussion and Limitations

While RSWR represents a significant step forward in non-iterative DDM, several areas remain for future development:

  • Dimensionality: The current study focuses on 1D implementations. While the underlying logic regarding finite propagation speed applies to 2D and 3D spaces, the geometric complexity of overlaps in higher dimensions requires further exploration.
  • Theoretical Framework: The authors note that certain formal proofs (specifically Theorem 2.10) are currently being finalized, indicating that the theoretical foundation is still maturing.
  • Equation Scope: The present results are limited to linear wave equations. The potential application of RSWR to non-linear hyperbolic partial differential equations remains a subject for future research.
  • Hardware Performance: While the algorithm is theoretically more efficient, actual wall-clock speedup benchmarks on supercomputing clusters compared to optimized iterative SWR methods have yet to be fully documented.

Conclusion

The Relative Schwarz Waveform Relaxation method offers a promising alternative to traditional iterative domain decomposition. By grounding numerical synchronization in the physical reality of wave speed, RSWR eliminates the need for costly iterations and complex preconditioners. Its high precision and demonstrated scalability make it a potent candidate for the next generation of distributed physical simulations.

Summary updated

BibTeX
@misc{wei2022relative,
  author = {Fei Wei and Anna Zhao},
  title = {{Relative Schwarz Method}},
  year = {2022},
  eprint = {2203.10477},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2203.10477},
}
Figure