A hierarchical butterfly LU preconditioner for two-dimensional electromagnetic scattering problems involving open surfaces

Yang Liu, Haizhao Yang

TL;DR

This paper introduces a novel preconditioner, the Hierarchical Interpolative Decomposition Butterfly-LU (H-IDBF-LU), for efficiently solving large-scale electromagnetic scattering problems. It achieves near-linear complexity (O(N log² N)) for both matrix-vector multiplication and the preconditioning step, enabling the solution of systems with up to 100 million unknowns.

What Problem Does This Paper Address?

Electromagnetic scattering analysis often relies on solving large systems of linear equations derived from integral equations, such as the electric-field integral equation (EFIE). For electrically large objects, especially those with open surfaces, these systems become computationally prohibitive for traditional direct or iterative solvers. While fast iterative methods like MLFMA exist, their efficiency can degrade significantly for problems with resonances or complex geometries, leading to a large number of iterations. The challenge is to develop solvers that maintain near-linear complexity even for these challenging scenarios.

Methods

The core of this work lies in the H-IDBF-LU preconditioner, which combines two key ideas:

  • Hierarchical Interpolative Decomposition Butterfly Factorization (H-IDBF): This technique is used to compress dense blocks of the discretized EFIE operator. IDBF leverages the idea of interpolative decomposition to represent these blocks in a data-sparse format, significantly reducing memory and computational costs for matrix-vector products.
  • Approximate Butterfly-Compressed LU Factorization: The authors observe that the lower and upper triangular factors of the EFIE matrix exhibit similar "oscillation patterns" to the original matrix, especially for open surfaces without strong resonances. They propose using the H-IDBF representations of these triangular factors as an approximate LU decomposition. This allows for efficient preconditioning by solving triangular systems, which is crucial for iterative solvers.

The method constructs the H-IDBF of the impedance matrix and then uses this to derive the H-IDBFs of its approximate LU factors. Applying the preconditioner involves solving two hierarchical triangular systems.

Datasets

Not discussed in the paper. The authors use synthetically generated geometries for their numerical experiments.

Key Insights and Ideas

  • The "Oscillation Pattern" Connection: A crucial insight is that the LU factors of the impedance matrix for open surfaces share similar oscillatory characteristics with the original matrix. This observation is key to approximating the LU factorization using the H-IDBF structure.
  • Open Surfaces as a Sweet Spot: The proposed method appears particularly effective for open surfaces that don't exhibit strong resonances. This suggests that the underlying assumptions about the structure of the LU factors hold well in these cases.
  • Hierarchical Structure for Efficiency: The paper demonstrates how to leverage hierarchical structures (like those in butterfly factorizations) not just for matrix compression but also for approximating fundamental matrix operations like LU decomposition, leading to significant computational gains.

Key Results

  • Near-Linear Complexity: The H-IDBF-LU preconditioner achieves a computational complexity of O(N log² N) per iteration for both matrix-vector multiplication and the preconditioning step.
  • Reduced Iterations: For the tested geometries, the number of iterations required for convergence was remarkably low, scaling at most as O(log² N), and often as O(1) or O(log N).
  • Scalability to Large Problems: The method successfully solved problems with up to 100 million unknowns, demonstrating its scalability for practical electromagnetic scattering analysis.
  • Accuracy: Numerical results show good accuracy for various geometry shapes, with a slight degradation observed as the problem size increases.
  • Competitive Performance: The proposed method is competitive with state-of-the-art MLFMA-based iterative solvers, particularly for large-scale problems.

Limitations and Future Work

  • Resonance and Closed Surfaces: The authors note that for highly resonant cavities or closed surfaces, the iteration counts can grow much faster, indicating that the preconditioner's effectiveness might be reduced in such cases.
  • Theoretical Understanding of LU Factors: While the paper provides physical explanations and numerical evidence, a rigorous proof for why the LU factors of the EFIE operator are hierarchically complementary low-rank is still an open area for future theoretical investigation.
  • Extension to 3D: The authors suggest that the idea of using approximate LU factorization based on hierarchical structures could be extended to three-dimensional EFIEs with open surfaces, which would be a significant future research direction.

Summary updated

Abstract

Highlights•O(Nlog2⁡N)<math><mi is="true">O</mi><mo stretchy="false" is="true">(</mo><mi is="true">N</mi><msup is="true"><mrow is="true"><mi mathvariant="normal" is="true">log</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msup><mo is="true">⁡</mo><mi is="true">N</mi><mo stretchy="false" is="true">)</mo></math> fast matvec and approximate LU factorization of the linear system from 2D EFIE involving open surfaces.•The approximate LU serves as an efficient preconditioner with an O(Nlog2⁡N)<math><mi is="true">O</mi><mo stretchy="false" is="true">(</mo><mi is="true">N</mi><msup is="true"><mrow is="true"><mi mathvariant="normal" is="true">log</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msup><mo is="true">⁡</mo><mi is="true">N</mi><mo stretchy="false" is="true">)</mo></math> application cost and an iteration number at most O(log2⁡N)<math><mi is="true">O</mi><mo stretchy="false" is="true">(</mo><msup is="true"><mrow is="true"><mi mathvariant="normal" is="true">log</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msup><mo is="true">⁡</mo><mi is="true">N</mi><mo stretchy="false" is="true">)</mo></math>.•A practical solver for linear systems of size up to 100 million unknowns in the high-frequency integral equation.
BibTeX
@article{liu2020hierarchical,
  author = {Yang Liu and Haizhao Yang},
  title = {{A hierarchical butterfly LU preconditioner for two-dimensional electromagnetic scattering problems involving open surfaces}},
  journal = {Journal of Computational Physics},
  year = {2020},
  url = {https://openreview.net/forum?id=ADp6jWS0Rg},
}
Figure