Fast evaluation of quadrature formulae on the sphere

Keiner, Jens; Potts, Daniel

doi:10.1090/S0025-5718-07-02029-7

Fast evaluation of quadrature formulae on the sphere
HTML articles powered by AMS MathViewer

by Jens Keiner and Daniel Potts PDF

Math. Comp. 77 (2008), 397-419 Request permission

Abstract:

Recently, a fast approximate algorithm for the evaluation of expansions in terms of standard $\mathrm {L}^2\left (\mathbb {S}^2\right )$-orthonormal spherical harmonics at arbitrary nodes on the sphere $\mathbb {S}^2$ has been proposed in [S. Kunis and D. Potts. Fast spherical Fourier algorithms. J. Comput. Appl. Math., 161:75–98, 2003]. The aim of this paper is to develop a new fast algorithm for the adjoint problem which can be used to compute expansion coefficients from sampled data by means of quadrature rules. We give a formulation in matrix-vector notation and an explicit factorisation of the spherical Fourier matrix based on the former algorithm. Starting from this, we obtain the corresponding factorisation of the adjoint spherical Fourier matrix and are able to describe the associated algorithm for the adjoint transformation which can be employed to evaluate quadrature rules for arbitrary weights and nodes on the sphere. We provide results of numerical tests showing the stability of the obtained algorithm using as examples classical Gauß-Legendre and Clenshaw-Curtis quadrature rules as well as the HEALPix pixelation scheme and an equidistribution.

References

S. Belmehdi, On the associated orthogonal polynomials, J. Comput. Appl. Math. 32 (1990), no. 3, 311–319. MR 1090883, DOI 10.1016/0377-0427(90)90041-W
Martin Böhme and Daniel Potts, A fast algorithm for filtering and wavelet decomposition on the sphere, Electron. Trans. Numer. Anal. 16 (2003), 70–92. MR 1988721
Philip J. Davis and Philip Rabinowitz, Methods of numerical integration, 2nd ed., Computer Science and Applied Mathematics, Academic Press, Inc., Orlando, FL, 1984. MR 760629
James R. Driscoll and Dennis M. Healy Jr., Computing Fourier transforms and convolutions on the $2$-sphere, Adv. in Appl. Math. 15 (1994), no. 2, 202–250. MR 1277214, DOI 10.1006/aama.1994.1008
W. Freeden, T. Gervens, and M. Schreiner, Constructive approximation on the sphere, Numerical Mathematics and Scientific Computation, The Clarendon Press, Oxford University Press, New York, 1998. With applications to geomathematics. MR 1694466
M. Frigo and S. G. Johnson. FFTW, C subroutine library. http://www.fftw.org.
D. M. Healy Jr., D. N. Rockmore, P. J. Kostelec, and S. Moore, FFTs for the 2-sphere-improvements and variations, J. Fourier Anal. Appl. 9 (2003), no. 4, 341–385. MR 1999564, DOI 10.1007/s00041-003-0018-9
J. Keiner, S. Kunis, and D. Potts. NFFT3.0, Softwarepackage, C subroutine library. http://www.tu-chemnitz.de/$\sim$potts/nfft, 2006.
Stefan Kunis and Daniel Potts, Fast spherical Fourier algorithms, J. Comput. Appl. Math. 161 (2003), no. 1, 75–98. MR 2018576, DOI 10.1016/S0377-0427(03)00546-6
H. N. Mhaskar, F. J. Narcowich, and J. D. Ward, Spherical Marcinkiewicz-Zygmund inequalities and positive quadrature, Math. Comp. 70 (2001), no. 235, 1113–1130. MR 1710640, DOI 10.1090/S0025-5718-00-01240-0
Martin J. Mohlenkamp, A fast transform for spherical harmonics, J. Fourier Anal. Appl. 5 (1999), no. 2-3, 159–184. MR 1683208, DOI 10.1007/BF01261607
Daniel Potts, Gabriele Steidl, and Manfred Tasche, Fast algorithms for discrete polynomial transforms, Math. Comp. 67 (1998), no. 224, 1577–1590. MR 1474655, DOI 10.1090/S0025-5718-98-00975-2
Daniel Potts, Gabriele Steidl, and Manfred Tasche, Fast and stable algorithms for discrete spherical Fourier transforms, Proceedings of the Sixth Conference of the International Linear Algebra Society (Chemnitz, 1996), 1998, pp. 433–450. MR 1628403, DOI 10.1016/S0024-3795(97)10013-1
Daniel Potts, Gabriele Steidl, and Manfred Tasche, Fast Fourier transforms for nonequispaced data: a tutorial, Modern sampling theory, Appl. Numer. Harmon. Anal., Birkhäuser Boston, Boston, MA, 2001, pp. 247–270. MR 1865690
Vladimir Rokhlin and Mark Tygert, Fast algorithms for spherical harmonic expansions, SIAM J. Sci. Comput. 27 (2006), no. 6, 1903–1928. MR 2211433, DOI 10.1137/050623073
Ian H. Sloan and Robert S. Womersley, Constructive polynomial approximation on the sphere, J. Approx. Theory 103 (2000), no. 1, 91–118. MR 1744380, DOI 10.1006/jath.1999.3426
Reiji Suda and Masayasu Takami, A fast spherical harmonics transform algorithm, Math. Comp. 71 (2002), no. 238, 703–715. MR 1885622, DOI 10.1090/S0025-5718-01-01386-2
L. N. Trefethen. Is Gauss quadrature better than Clenshaw-Curtis? SIAM Review, 2007. to appear.
Jörg Waldvogel, Fast construction of the Fejér and Clenshaw-Curtis quadrature rules, BIT 46 (2006), no. 1, 195–202. MR 2214855, DOI 10.1007/s10543-006-0045-4
Antony F. Ware, Fast approximate Fourier transforms for irregularly spaced data, SIAM Rev. 40 (1998), no. 4, 838–856. MR 1659685, DOI 10.1137/S003614459731533X
Robert S. Womersley and Ian H. Sloan, How good can polynomial interpolation on the sphere be?, Adv. Comput. Math. 14 (2001), no. 3, 195–226. MR 1845243, DOI 10.1023/A:1016630227163