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
Additional Information
- Jens Keiner
- Affiliation: Institute of Mathematics, University of Lübeck, Wallstraße 40, 23560 Lübeck, Germany
- Email: keiner@math.uni-luebeck.de
- Daniel Potts
- Affiliation: Department of Mathematics, Chemnitz University of Technology, Reichenhainer Straße 39, 09107 Chemnitz, Germany
- Email: potts@mathematik.tu-chemnitz.de
- Received by editor(s): June 1, 2006
- Published electronically: June 20, 2007
- © Copyright 2007 American Mathematical Society
- Journal: Math. Comp. 77 (2008), 397-419
- MSC (2000): Primary 65T99, 33C55, 42C10, 65T50
- DOI: https://doi.org/10.1090/S0025-5718-07-02029-7
- MathSciNet review: 2353959