Sparsifying preconditioner for the time-harmonic Maxwell's equations

Fei Liu, Lexing Ying

TL;DR

This paper introduces a novel "sparsifying preconditioner" for solving the time-harmonic Maxwell's equations, which are fundamental to electromagnetics. By cleverly approximating dense integral equations with sparse ones, this method significantly reduces computational cost, making it as efficient as solving sparse systems derived from PDE discretizations, even for high-frequency problems.

What Problem Does This Paper Address?

Electromagnetic scattering problems, particularly at high frequencies, lead to massive computational challenges. Traditional methods often discretize the governing partial differential equations (PDEs), resulting in large, sparse systems. However, an alternative approach uses integral equations, which naturally handle boundary conditions but produce dense linear systems. Applying standard sparse matrix techniques to these dense systems is computationally prohibitive. This paper tackles the problem of efficiently solving these dense integral formulations, aiming to bridge the gap in computational efficiency between PDE-based and integral equation-based methods.

Methods

The core of this work is the "sparsifying preconditioner" technique, adapted from its application to scalar wave equations. The key idea is to transform the dense integral equation into a sparse approximation by minimizing non-local interactions. This is achieved by constructing a sparse system that approximates the original dense one. The solution of this sparse system then acts as a preconditioner for the dense system, dramatically reducing the number of iterations required by iterative solvers like GMRES. The method leverages the translational invariance of the underlying Green's functions to efficiently compute the necessary "stencils" (sparse approximations) for different types of grid points (interior, face, edge, vertex).

Datasets

Not discussed in the paper. The paper focuses on developing a numerical method and demonstrates its performance on various simulated electromagnetic scattering scenarios.

Key Insights and Ideas

  • Bridging the Gap: The paper successfully extends a sparsifying preconditioner technique, previously successful for scalar wave equations, to the more complex vector-valued Maxwell's equations. This is a significant step towards making integral equation methods competitive with PDE methods for high-frequency electromagnetics.
  • Minimizing Non-Local Interactions: The fundamental insight is that the dense interactions in the integral equation can be approximated by local ones, leading to a sparse system. This is analogous to how PDE discretizations naturally yield sparse systems.
  • Frequency Independence: A crucial finding is that the number of preconditioned iterations remains small and largely independent of the frequency. This is a highly desirable property for high-frequency scattering problems where the number of unknowns can grow dramatically with frequency.
  • Translational Invariance is Key: Exploiting the translational invariance of the Green's functions is critical for efficiently computing the sparse stencils. This avoids costly computations for each grid point and allows for a scalable approach.

Key Results

The paper demonstrates that the proposed sparsifying preconditioner, when combined with the GMRES solver, significantly reduces the computational cost of solving the time-harmonic Maxwell's equations in their integral form. Numerical results show that the number of iterations is consistently low (typically below ten) and largely independent of the wave number. The setup and application times for the preconditioner are shown to scale favorably, comparable to or better than the theoretical complexities of solving sparse systems from PDE discretizations. For instance, in 2D, application time scales as O(N log N), and in 3D, it scales as O(N^(4/3)), where N is the number of unknowns.

Limitations and Future Work

The authors acknowledge that the current method relies on a smooth medium for the Nyström discretization and the application of FFT. Cases with sharp transitions in the medium are not directly addressed and are referred to existing literature. Future work includes extending the method to handle inhomogeneous magnetic permeability (μ), which would involve a larger system but the same core idea. Additionally, exploring alternative sparse solvers like the sweeping preconditioner or recursive approaches could further reduce computational costs, potentially achieving quasi-linear time complexity for solving the integral form of Maxwell's equations.

Summary updated

Abstract

This paper presents the sparsifying preconditioner for the time-harmonic Maxwell's equations in the integral formulation. Following the work on sparsifying preconditioner for the Lippmann-Schwinger equation, this paper generalizes that approach from the scalar wave case to the vector case. The key idea is to construct a sparse approximation to the dense system by minimizing the non-local interactions in the integral equation, which allows for applying sparse linear solvers to reduce the computational cost. When combined with the standard GMRES solver, the number of preconditioned iterations remains small and essentially independent of the frequency. This suggests that, when the sparsifying preconditioner is adopted, solving the dense integral system can be done as efficiently as solving the sparse system from PDE discretization.
BibTeX
@article{liu2019sparsifying,
  author = {Fei Liu and Lexing Ying},
  title = {{Sparsifying preconditioner for the time-harmonic Maxwell's equations}},
  journal = {Journal of Computational Physics},
  year = {2019},
  url = {https://openreview.net/forum?id=pIge9TQiCn},
}
Figure