2014/08/01 by Fabien Casenave, Casenave, Fabien
Engineering · Physics and Astronomy · #Electromagnetic Scattering and Analysis #Electromagnetic Simulation and Numerical Methods #FOS: Mathematics #Numerical Analysis (math.NA) #Numerical methods in engineering
paper · pdf · doi:10.48550/arxiv.1408.0210
openalex publication_date 2014/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We derive a Fast Multipole Method (FMM) where a low-rank approximation of the kernel is obtained using the Empirical Interpolation Method (EIM). Contrary to classical interpolation-based FMM, where the interpolation points and basis are fixed beforehand, the EIM is a nonlinear approximation method which constructs interpolation points and basis which are adapted to the kernel under consideration. The basis functions are obtained using evaluations of the kernel itself. We restrict ourselves to translation-invariant kernels, for which a modified version of the EIM approximation can be used in a multilevel FMM context; we call the obtained algorithm Empirical Interpolation Fast Multipole Method (EIFMM). An important feature of the EIFMM is a built-in error estimation of the interpolation error made by the low-rank approximation of the far-field behavior of the kernel: the algorithm selects the optimal number of interpolation points required to ensure a given accuracy for the result, leading to important gains for inhomogeneous kernels.