A Butterfly-Accelerated Manifold Harmonic Transform
This work provides a practical fast transform for manifold harmonics on arbitrary surfaces, addressing a computational bottleneck for tasks in geometry processing and scientific computing.
The authors develop a fast algorithm for computing linear combinations of Laplace-Beltrami eigenfunctions on arbitrary surfaces (manifold harmonics) using a butterfly factorization, achieving speedups and reduced memory requirements across various geometries and discretizations.
The eigenfunctions of the Laplacian are a natural basis of functions for many tasks in computational mathematics. On the circle and sphere, the eigenfunctions are given by complex periodic exponentials and spherical harmonics, respectively, and much work has been done to develop fast algorithms for analyzing and synthesizing data in these bases. In this work, we generalize these special-case transforms to Laplace-Beltrami eigenfunctions of arbitrary surfaces, referred to as manifold harmonics. The resulting fast algorithm for computing linear combinations of the manifold harmonics is based on a butterfly factorization, which hierarchically compresses the transform matrix by constructing nested low-rank approximations of carefully selected submatrices. Several numerical examples are provided which demonstrate the speedups and reduction in memory requirements achieved by our algorithm for a variety of geometries, discretizations, and applications. In addition, a detailed analysis of the algorithm is given in the case that the underlying manifold is the flat periodic square.