论文标题
通过插值分解蝴蝶分解快速应用球形谐波变换
Rapid Application of the Spherical Harmonic Transform via Interpolative Decomposition Butterfly Factorization
论文作者
论文摘要
我们描述了一种用于应用正向和逆球形谐波变换的算法。它基于一种新方法，用于通过层次应用插值分解蝴蝶分解（IDBF）来快速计算前向和相关的Legendre变换。实验证据表明，我们方法的总运行时间（包括所有必要的预计）是$ \ Mathcal {o}（n^2 \ log^3（n））$，其中$ n $是转换的顺序。这几乎是渐近的最佳选择。此外，与渐近最佳或几乎如此的现有算法不同，我们算法的运行时间的常数足够小，可以使其与最先进的$ \ Mathcal {o} \ left（n^3 \ right）$方法在相对较小的$ n $的值下进行竞争。提供数值结果以证明新框架的有效性和数值稳定性。
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.
