A fast transform for spherical harmonics

摘要: Spherical Harmonics arise on the sphere $S\sp2$ in same way that (Fourier) exponential functions $\{e\sp{ik\Theta}\}\sb{k\in {\rm Z}}$ circle. Harmonic series have many of wonderful properties as Fourier series, but lacked one important thing: a numerically stable fast transform analogous to Fast Transform. Without transform, evaluating (or expanding in) computer is slow--for large computations prohibitively slow. This thesis provides transform. For grid $N\sp2$ points sphere, direct calculation has computational complexity ${\cal O}(N\sp4)$, simple separation variables and Transform reduces it O}(N\sp3)$ time. Here we present an algorithm with time O}(N\sp2\log\ \sp2 N)$. The problem quickly application matrices Associated Legendre Functions certain orders. The essential insight although these are dense oscillatory, locally they can be represented efficiently trigonometric functions. We construct adaptive partition each matrix into rectangles such rectangle sparse (two dimensional) local series. entire O}(N\ \log\ N)$ coefficients this non- standard form, constants independent order parameter. It applied time, overhead cost for adaption \log\sp2\ N)$. Adding over orders yields overall O}(N\sp2\