Rapid Application of the Spherical Harmonic Transform via Interpolative Decomposition Butterfly Factorization

Abstract

We describe an algorithm for the application of the forward and inverse spherical harmonic transforms. It is based on a new method for rapidly computing the forward and inverse associated Legendre transforms by hierarchically applying the interpolative decomposition butterfly factorization (IDBF). Experimental evidence suggests that the total running time of our method -- including all necessary precomputations -- is $\mathcal{O}(N^2{\log }^3(N))$, where $N$ is the order of the transform. This is nearly asymptotically optimal. Moreover, unlike existing algorithms which are asymptotically optimal or nearly so, the constant in the running time of our algorithm is small enough to make it competitive with state-of-the-art $\mathcal{O}\left(N^3\right)$ methods at relatively small values of $N$. Numerical results are provided to demonstrate the effectiveness and numerical stability of the new framework.

References in corpus (4)

• Interpolative Butterfly Factorization
• A Unified Framework for Oscillatory Integral Transform: When to use NUFFT or Butterfly Factorization?
• An algorithm for the numerical evaluation of the associated Legendre functions that runs in time independent of degree and order
• Multidimensional Phase Recovery and Interpolative Decomposition Butterfly Factorization

Cited by in corpus (2)

• A Butterfly-Accelerated Volume Integral Equation Solver for Broad Permittivity and Large-Scale Electromagnetic Analysis
• Sparse Approximate Multifrontal Factorization with Butterfly Compression for High Frequency Wave Equations