A Butterfly-accelerated Manifold Harmonic Transform

Paul G. Beckman, Samuel F. Potter, Michael O’Neil · 2026

Read A Butterfly-accelerated Manifold Harmonic Transform by Paul G. Beckman, Samuel F. Potter, Michael O’Neil (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-21828.txt.

Introduction

Paul Beckman, Samuel Potter, and Michael O'Neil extend fast transform methods from circles and spheres to Laplace-Beltrami modes of any surfaces, known as manifold harmonics. Their fast method forms sums of them through a butterfly factorization, which shrinks the transform matrix with nested low-rank fits of chosen blocks. Tests show speedups and storage savings across varied shapes, meshes, and uses. A detailed analysis is also given for the flat square.

Catalog record

CREATORPaul G. Beckman, Samuel F. Potter, Michael O’Neil
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68721
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.21828

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Butterfly-accelerated Manifold Harmonic Transform Thanks: Submitted to the editors DATE. Paul G. Beckman, Samuel F. Potter, Michael O’Neil Abstract 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. keywords Butterfly algorithm, manifold harmonics, Laplace-Beltrami, Fourier transform, Fiedler tree Funding. P. G. Beckman was partially supported by the Office of Naval Research under award #N00014-21-1-2383 and by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Department of Energy Computational Science Graduate Fellowship under Award Number DE-SC0022158. S. F. Potter was partially supported by the Office of Naval Research under award #N00014-18-1-2307. M. O’Neil was partially supported by the Office of Naval Research under awards N00014-18-1-2307 and #N00014-21-1-2383. † † runningheads: A Butterfly-accelerated Manifold Harmonic Transform / Beckman, Potter, and O’Neil MSC 65T99, 65R10, 65D15 1 Introduction The Fast Fourier Transform (FFT) [ 52 ] and Nonuniform Fast Fourier Transform (NUFFT) [ 16 , 23 ] have revolutionized computational methods across fields including signal processing, differential equations, and statistics by accelerating the computation of discrete trigonometric sums with n terms and n outputs from \mathcal{O}(n^{2}) to \mathcal{O}(n\log n) time. In the case of the FFT, this acceleration is achieved purely by algebraic manipulations of the quantity e^{2\pi ijk/n} . On the other hand, the NUFFT relies on Fourier convolution theorems and numerical approximations based on an FFT applied to a periodized kernel function. However, both of these algorithms strongly rely on the fact that the underlying geometry is simple and periodic; spectral analysis in \mathbb{R}^{d} or \mathbb{T}^{d} need only manipulate complex exponentials. In order to perform spectral analysis in more general domains, one requires a generalization of the Fourier transform which takes into account the underlying geometry. To motivate such a generalization, consider the two-dimensional type-II nonuniform discrete Fourier transform: \displaystyle f(\bm{x}_{j})=\sum_{\bm{k}\in[-\frac{\sqrt{m}}{2},\frac{\sqrt{m}}{2}-1]^{2}}c_{\bm{k}}\,e^{i\bm{k}\cdot\bm{x}_{j}},\quad\text{for }j=1,\dots,n. (1.1) The above sum evaluates the function f at n nonuniform spatial locations \bm{x}_{j}\in[-\pi,\pi]^{2} given the coefficients c_{\bm{k}} , which denote Fourier coefficients for m uniform integer frequencies \bm{k}\in\mathbb{Z}^{2} . Noting that the functions \varphi_{\bm{k}}(\bm{x})=e^{i\bm{k}\cdot\bm{x}} are exactly the eigenfunctions of the Laplacian \Delta on [-\pi,\pi]^{2} under periodic boundary conditions, it is natural to consider a generalization of the Fourier transform which uses Laplacian eigenfunctions to perform harmonic analysis on domains other than the flat periodic square. For a general compact d -manifold \mathcal{M} with boundary \partial\mathcal{M} , consider the Laplace-Beltrami eigenproblem \displaystyle\Delta_{\mathcal{M}}\varphi \displaystyle=\lambda\varphi, \displaystyle\text{in }\mathcal{M}, (1.2) \displaystyle g\Big(\varphi,\frac{\partial\varphi}{\partial n}\Big) \displaystyle=0 \displaystyle\text{on }\partial\mathcal{M}, where \Delta_{\mathcal{M}} is the Laplace-Beltrami operator and g(\varphi,\partial\varphi/\partial n) represents any suitable set of boundary conditions, e.g. Dirichlet, Neumann, Robin, or a mixture thereof. Of course if \mathcal{M} does not have a boundary, then the above eigenproblem needs no boundary conditions. This eigenproblem yields a set of nonnegative eigenvalues 0\leq\lambda_{1}\leq\lambda_{2}\leq\dots whose corresponding eigenfunctions \varphi_{k} form an orthonormal basis for L^{2}(\mathcal{M}) [ 10 ] . A generalization of the discrete Fourier transform ( 1.1 ) to the manifold \mathcal{M} is then given by the discrete manifold harmonic transform (MHT) f(\bm{x}_{j})=\sum_{k=1}^{m}c_{k}\,\varphi_{k}(\bm{x}_{j}),\quad\text{for }j=1,\dots,n, (1.3) which we write in the equivalent matrix form \bm{\mathsf{f}}=\bm{\mathsf{\Phi}}\bm{\mathsf{c}} where \bm{\mathsf{\Phi}}\in\mathbb{C}^{n\times m} , \bm{\mathsf{\Phi}}_{jk}=\varphi_{k}(\bm{x}_{j}) , and \bm{\mathsf{f}}_{j}=f(\bm{x}_{j}) . Figure 1 shows some numerically computed Laplace-Beltrami eigenfunctions \varphi_{k} on an example manifold \mathcal{M} , each of which serves as a column of the matrix \bm{\mathsf{\Phi}} . Note that as we increase the index k , the eigenfunctions exhibit oscillations on decreasing lengthscales, providing a natural multiscale Fourier-like basis on \mathcal{M} . Figure 1 : Eigenfunctions \varphi_{k} of the Laplace-Beltrami operator on a cow manifold for k=2,4,8,78,340,1350 . The MHT presents a number of computational challenges when compared to the FFT. First, unless the geometry is extremely simple, the requisite eigenfunctions \varphi_{k} are not available in closed form. In addition, even when the eigenfunctions are available in closed form, there is no general fast algorithm for evaluating linear combinations of these functions. When \mathcal{M} is the sphere or disk, the eigenfunctions \varphi_{k} are given by spherical harmonics and Bessel functions, respectively, and one can take advantage of various symmetries and analytical expansions to develop fast algorithms [ 49 , 3 , 43 , 39 , 50 , 30 ] which rely on the FFT. However, no such symmetries or explicit expansions are available a priori for the MHT on general manifolds \mathcal{M} . Therefore the eigenfunctions \varphi_{k} must be computed numerically in general, and no analytical reduction to complex exponentials can be made. Instead, we must rely on general-purpose results regarding the eigenfunctions of the Laplace-Beltrami operator and leverage purely linear-algebraic structure to compress the matrix \bm{\mathsf{\Phi}} . A suitable compressed linear-algebraic representation of oscillatory operators is given by the butterfly factorization [ 33 , 26 , 27 ] , which we apply and analyze here in the MHT context. The butterfly factorization is a generalization of the hierarchical algebraic structure of the FFT algorithm to more general operators satisfying a complementary low-rank property in which a particular hierarchy of matrix blocks are approximately low-rank. Butterfly factorizations have been successfully applied to compress Fourier integral operators [ 9 , 26 , 27 ] , Hankel transforms [ 26 , 33 ] , and spherical harmonic transforms [ 50 , 39 ] , among others. The MHT and related computations appear in applications to computer graphics and meshing [ 51 , 37 , 25 , 38 , 40 ] , surface partial differential equations (PDEs) [ 17 , 7 ] , model order reduction [ 1 , 2 ] , statistics [ 8 , 24 ] , as well as data assimilation and kernel learning [ 21 , 4 ] . A number of compressed representations for the lowest Laplace-Beltrami eigenfunctions have been proposed in the literature [ 5 , 13 , 31 ] . However, these works focus mainly on efficiently computing these eigenfunctions, and do not explicitly investigate the possibility of a fast transform for rapidly evaluating linear combinations of many eigenfunctions \{\varphi_{k}\}_{k=1}^{m} at a large number of target points \{\bm{x}_{j}\}_{j=1}^{n}\subset\mathcal{M} (or of a fast adjoint transform which maps function values to expansion coefficients). In this work, we introduce a discretization-agnostic butterfly-accelerated manifold harmonic transform (BF-MHT) and demonstrate that it can significantly reduce the cost to store and apply the MHT. We begin by describing the butterfly factorization and the trees necessary to compress the MHT matrix. Then, in the case of the two-dimensional periodic Fourier transform, we prove asymptotic complexity results regarding the cost to store

Read the complete text