On the role of relaxation and acceleration in the non-overlapping Schwarz alternating method for coupling

1. Problem Statement

The paper addresses the convergence limitations of the non-overlapping Schwarz alternating method when used for Domain Decomposition (DD) based coupling of Partial Differential Equations (PDEs).

• Context: While overlapping Schwarz methods converge well, non-overlapping methods are preferred for multi-physics and multi-material applications because they allow independent meshing of sub-domains. However, non-overlapping schemes (specifically with Dirichlet-Neumann transmission conditions) are often slower, less robust, and prone to divergence, especially for problems with heterogeneous coefficients, fine meshes, or long/thin sub-domains.
• Challenge: The standard approach to mitigate this is classical relaxation, where a relaxation parameter $\rho$ is manually tuned. However, finding the optimal $\rho$ is problem-specific, difficult to determine a priori, and often leads to poor performance if chosen incorrectly.
• Goal: The authors aim to systematically evaluate and improve the convergence of non-overlapping Schwarz methods by replacing or augmenting classical relaxation with Aitken acceleration and Anderson acceleration, treating the Schwarz scheme as a fixed-point iteration.

2. Methodology

The authors reformulate the multiplicative Dirichlet-Neumann Schwarz algorithm as a fixed-point iteration on the interface data. They then apply two acceleration techniques:

A. Theoretical Framework

• Fixed-Point Reformulation: The interface update is expressed as $g^{(k+1)} = T_r^\rho(g^{(k)})$, where $T$ represents the composition of Dirichlet-to-Neumann and Neumann-to-Dirichlet maps.
• Aitken Acceleration: A dynamic relaxation parameter $\rho^{(k)}$ is computed at each step to minimize the interface jump residual. The authors introduce a parameter $N_0$ to delay the dynamic update for the first few iterations to ensure stability.
• Anderson Acceleration: This method uses a history of previous residuals (depth $m_{and}$) to compute optimal linear combination coefficients ($\alpha$) for the update. It is framed as a constrained least-squares problem.
• Novel Contribution (Anderson with Memory Adaptation): The authors propose a new adaptive variant where the history depth $m_k$ is adjusted on-the-fly based on the change in relative error. If the error reduction is small, the history is truncated to a small value ($\bar{m}$) to avoid ill-conditioning; otherwise, the full history is used.

B. Numerical Experiments

The methods were tested on two distinct problems:

1. 1D Laplace Equation: A linear problem used to derive theoretical convergence rates and verify analytical results (e.g., optimal $\rho$ values).
2. 2D Nonlinear Elasticity: A steady-state nonlinear problem (Neo-Hookean material) to test robustness in a realistic, complex setting.
   • Scenarios: Tests were conducted with $N_{dd} = 2$ (two sub-domains) and $N_{dd} \in \{2, ..., 5\}$ (multi-domain settings).
   • Metrics: Convergence speed (iterations), robustness (sensitivity to $\rho$), error accuracy, and computational cost (CPU time).

3. Key Contributions

1. First Application to Non-Overlapping DD: The paper provides the first known adaptation of Anderson acceleration specifically for the non-overlapping Dirichlet-Neumann Schwarz method.
2. Theoretical Analysis:
   • Proved that for 1D problems, Aitken-accelerated Schwarz achieves quadratic convergence ($p=2$) if the underlying unrelaxed method converges linearly.
   • Derived that Anderson coefficients in the scalar limit follow a geometric distribution based on the dominant eigenvalue of the fixed-point operator.
3. Adaptive Algorithm: Development of "Anderson with memory adaptation," which dynamically adjusts the history depth to balance convergence speed and numerical stability, eliminating the need for manual tuning of the history parameter.
4. Systematic Comparison: A comprehensive benchmark comparing classical relaxation, Aitken, and Anderson acceleration across different domain decomposition sizes.

4. Key Results

1D Laplace Equation

• Classical Relaxation: Convergence is highly sensitive to $\rho$. The optimal value is analytically proven to be $\rho = \bar{x}$ (interface location). Divergence occurs if $\rho$ is too large or too small relative to the interface position.
• Aitken Acceleration: Automatically detects the optimal $\rho$ (converging in 3 iterations) regardless of the initial guess, achieving quadratic convergence.
• Anderson Acceleration: Converges in 3 iterations to machine precision. Theoretically, it finds the exact fixed point in one acceleration step after establishing the history.

2D Nonlinear Elasticity ($N_{dd} = 2$)

• Robustness: Aitken acceleration is significantly more robust to the initial parameter $\rho(1)$ than classical relaxation or Anderson acceleration.
• Performance: For two sub-domains, Aitken-accelerated Schwarz is often the most efficient, requiring fewer iterations than Anderson and classical methods, and achieving lower final errors.
• Convergence Rate: Both Aitken and Anderson methods exhibit near-quadratic convergence rates, whereas classical relaxation is linear.

Multi-Domain Setting ($N_{dd} > 2$)

• Performance Shift: As the number of sub-domains increases, the performance hierarchy changes.
  • Aitken: Performance degrades significantly. For $N_{dd}=5$, it often performs worse than classical relaxation and can fail to converge.
  • Anderson: Remains the superior method. Anderson-accelerated Schwarz (especially with memory adaptation) requires approximately 3–4 times fewer iterations than Aitken or classical methods for $N_{dd}=5$.
• Computational Cost: Despite solving an optimization problem at each step, Anderson acceleration does not incur a significantly higher CPU cost per iteration compared to the other methods, thanks to efficient solvers (e.g., MATLAB's quadrprog).
• Memory Adaptation: The adaptive memory strategy successfully reduced the iteration count by a factor of three compared to fixed-history Anderson methods.

5. Significance and Conclusion

This work establishes that while Aitken acceleration is an excellent, low-cost, and robust choice for two-subdomain couplings, Anderson acceleration (specifically the proposed adaptive variant) is the method of choice for large-scale, multi-domain decompositions.

The study highlights that:

• Non-overlapping Schwarz methods can be made highly efficient and robust without manual parameter tuning.
• The "memory adaptation" strategy effectively mitigates the conditioning issues associated with large history depths in Anderson acceleration.
• The choice of acceleration technique must be dictated by the number of sub-domains: Aitken for simple splits, Anderson for complex, multi-region couplings.

These findings provide a practical guide for implementing efficient domain decomposition solvers in high-performance computing environments, particularly for complex multi-physics simulations where overlapping meshes are not feasible.