"Fast, Direct Integral and Differential Equation Solvers for Electromagnetic, Acoustic, and Elastic Applications at All Frequency Ranges"
Abstract: Large-scale and full-wave modeling for acoustic and elastic inversion applications, analysis and synthesis of electromagnetic systems for traditional and emerging RF, microwave, terahertz applications rely on efficient numerical tools. Integral equation (i.e., method of moment) and differential equation (e.g., finite-difference, finite-element, and finite-volume) formulations lead to dense and sparse linear systems, respectively. These linear systems can be solved by either iterative or direct solvers. Iterative solvers, despite their success in constructing well-conditioned formulations and fast multipole-type algorithms, remain inefficient for systems that are inherently ill-conditioned and/or require multiple right-hand sides. This is particularly true for design automation, inverse scattering, and other coupled systems where iterative solvers often require forbiddingly high iteration time. Direct solvers, in stark contrast, can attain reliable solutions in a predictable time. However, exact direct solvers typically require O(N3) and O(N2) computational costs for dense and sparse systems of size N, respectively. Fast direct solvers, on the other hand, rely on the fact that off-diagonal blocks of the well-ordered linear systems can be compressed by numerical linear algebra tools including low-rank and butterfly decompositions. When further embedded in hierarchical matrix frameworks, such as H-matrix, hierarchically off-diagonal low-rank (HODLR), and hierarchically semi-separable (HSS) formats, these direct solvers and preconditioners can achieve quasi-linear complexities for construction, factorization and solution for the discretized systems across all frequency ranges. We will review the development of these solvers in the past two decades, with an emphasis on their butterfly-based variants and distributed-memory parallelization for high-frequency problems. An open source package integrating most techniques reviewed, called ButterflyPACK, will also be introduced.