Fast spherical Fourier algorithms

[摘要] Spherical Fourier series play an important role in many applications. A numerically stable fast transform analogous to the fast Fourier transform is of great interest. For a standard grid of O(N-2) points on the sphere, a direct calculation has computational complexity of C(N-4), but a simple separation of variables reduces the complexity to C(N-3). Here we improve well-known fast algorithms for the discrete spherical Fourier transform with a computational complexity of C(N-2 log(2) N). Furthermore we present, for the first time, a fast algorithm for scattered data on the sphere. For arbitrary C(N-2) points on the sphere, a direct calculation has a computational complexity of O(N-4), but we present an approximate algorithm with a computational complexity of C(N-2 log(2) N). (C) 2003 Elsevier B.V. All rights reserved.

[发布日期] 2003-12-01

[关键词] spherical Fourier transform;spherical harmonics;associated Legendre functions;fast discrete transforms;fast Fourier transform at nonequispaced knots