Recent progress on the butterfly factorization

Sam Potter (Courant Institute of Mathematical Sciences)
05.05.2023 14:00 to 15:00

The butterfly factorization was introduced by Michielssen and Boag as a purely linear algebra-based fast algorithm for solving high-frequency scattering problems. It was later adapted to the numerical evaluation of special function transforms and other oscillatory integrals. We present recent results related to the butterfly factorization in two areas. First, we show how the butterfly factorization can be used to accelerate the transform associated with a discretized Laplace-Beltrami eigenbasis on a surface in 3D. Second, we present numerical results indicating that a reasonable implementation of the Michielssen and Boag "multilevel matrix decomposition algorithm" (MLMDA, or multilevel butterfly factorization) is competitive with the high-frequency fast multipole method in 2D. The common thread is a new software library for butterfly factorizations written in C which is under active development.