A Fast Direct Solver for Boundary Integral Equations Using Quadrature By Expansion

We construct and analyze a hierarchical direct solver for linear systems arising from the discretization of boundary integral equations using the Quadrature by Expansion (QBX) method. Our scheme builds on the existing theory of Hierarchical Semi-Separable (HSS) matrix operators that contain low-rank off-diagonal submatrices. We use proxy-based approximations of the far-field interactions and the Interpolative Decomposition (ID) to construct compressed HSS operators that are used as fast direct solvers for the original system. We describe a number of modifications to the standard HSS framework that enable compatibility with the QBX family of discretization methods. We establish an error model for the direct solver that is based on a multipole expansion of the QBX-mediated proxy interactions and standard estimates for the ID. Based on these theoretical results, we develop an automatic approach for setting scheme parameters based on user-provided error tolerances. The resulting solver seamlessly generalizes across two- and tree-dimensional problems and achieves state-of-the-art asymptotic scaling. We conclude with numerical experiments that support the theoretical expectations for the error and computational cost of the direct solver.

IMPACT 2025 - 15th International Workshop on Polyhedral Compilation Techniques

Instructional Faculty (Open Rank)

Instructional Faculty (Open Rank)

IMPACT 2024 - 14th International Workshop on Polyhedral Compilation Techniques

Automatic Synthesis of Low-Complexity Translation Operators for the Fast Multipole Method

We demonstrate a new, hybrid symbolic-numerical method for the automatic synthesis of all families of translation operators required for the execution of the Fast Multipole Method (FMM). Our method is applicable in any dimensionality and to any translation-invariant kernel. The Fast Multipole Method, of course, is the leading approach for attaining linear complexity in the evaluation of long-range (e.g. Coulomb) many-body interactions. Low complexity in translation operators for the Fast Multipole Method (FMM) is usually achieved by algorithms specialized for a potential obeying a specific partial differential equation (PDE). Absent a PDE or specialized algorithms, Taylor series based FMMs or kernel-independent FMM have been used, at asymptotically higher expense. When symbolically provided with a constant-coefficient elliptic PDE obeyed by the potential, our algorithm can automatically synthesize translation operators requiring $\mathrm{O}(p^d)$ operations, where $p$ is the expansion order and $d$ is dimension, compared with $\mathrm{O}(p^{2d})$ operations in a naive approach carried out on (Cartesian) Taylor expansions. This is achieved by using a compression scheme that asymptotically reduces the number of terms in the Taylor expansion and then operating directly on this ``compressed'' representation. Judicious exploitation of shared subexpressions permits formation, translation, and evaluation of local and multipole expansions to be performed in $\mathrm{O}(p^{d})$ operations, while an FFT-based scheme permits multipole-to-local translations in $\mathrm{O}(p^{d-1}\log(p))$ operations. We demonstrate computational scaling of code generation and evaluation as well as numerical accuracy through numerical experiments on a number of potentials from classical physics.