A fast and accurate algorithm for spherical harmonic analysis on HEALPix grids with applications to the cosmic microwave background radiation. (English) Zbl 1437.65251

Drake, Kathryn P.; Wright, Grady B.

J. Comput. Phys. 416, Article ID 109544, 14 p. (2020).

Summary: The Hierarchical Equal Area isoLatitude Pixelation (HEALPix) scheme is used extensively in astrophysics for data collection and analysis on the sphere. The scheme was originally designed for studying the Cosmic Microwave Background (CMB) radiation, which represents the first light to travel during the early stages of the universe’s development and gives the strongest evidence for the Big Bang theory to date. Refined analysis of the CMB angular power spectrum can lead to revolutionary developments in understanding the nature of dark matter and dark energy. In this paper, we present a new method for performing spherical harmonic analysis for HEALPix data, which is a central component to computing and analyzing the angular power spectrum of the massive CMB data sets. The method uses a novel combination of a non-uniform fast Fourier transform, the double Fourier sphere method, and R. M. Slevinsky’s fast spherical harmonic transform [Appl. Comput. Harmon. Anal. 47, No. 3, 585–606 (2019; Zbl 1495.33006)]. For a HEALPix grid with \(N\) pixels (points), the computational complexity of the method is \(\mathcal{O}(N \log^2 N)\), with an initial set-up cost of \(\mathcal{O}( N^{3 / 2} \log N)\). This compares favorably with \(\mathcal{O}( N^{3 / 2})\) runtime complexity of the current methods available in the HEALPix software when multiple maps need to be analyzed at the same time. Using numerical experiments, we demonstrate that the new method also appears to provide better accuracy over the entire angular power spectrum of synthetic data when compared to the current methods, with a convergence rate at least two times higher.

MSC:

65T50	Numerical methods for discrete and fast Fourier transforms
65Z05	Applications to the sciences
85A40	Astrophysical cosmology

Keywords:

HEALPix; fast spherical harmonic transform; nonuniform fast Fourier transform; double Fourier sphere; cosmic microwave background radiation

Citations:

Zbl 1495.33006

Software:

Healpix; LSQR; FastTransforms.jl; CRAIG; IGLOO

References:

[1]	Atkinson, K.; Han, W., Spherical Harmonics and Approximations on the Unit Sphere: An Introduction (2012), Springer: Springer Berlin, Heidelberg · Zbl 1254.41015
[2]	Beatson, R.; Greengard, L., A short course on fast multipole methods, (Wavelets Multilevel Methods Elliptic PDEs, Vol. 1 (1997)), 1-37 · Zbl 0882.65106
[3]	Bennett, C. L.; Larson, D.; Weiland, J. L.; Jarosik, N.; Hinshaw, G.; Odegard, N.; Smith, K. M.; Hill, R. S.; Gold, B.; Halpern, M.; Komatsu, E.; Nolta, M. R.; Page, L.; Spergel, D. N.; Wollack, E.; Dunkley, J.; Kogut, A.; Limon, M.; Meyer, S. S.; Tucker, G. S.; Wright, E. L., Nine-year Wilkinson microwave anisotropy probe (WMAP) observations: final maps and results, Astrophys. J. Suppl. Ser., 208, 20 (2013)
[4]	Benzi, M.; Golub, G. H.; Liesen, J., Numerical solution of saddle point problems, Acta Numer., 14, 1-137 (2005) · Zbl 1115.65034
[5]	Cooley, J.; Tukey, J., An algorithm for the machine calculation of complex Fourier series, Math. Comput., 19, 297-301 (1965) · Zbl 0127.09002
[6]	Crittenden, R. G.; Turok, N. G., Exactly azimuthal pixelizations of the sky (1998), University of Cambridge, Tech. Rep. DAMTP-1998-78
[7]	Estrin, G., Organization of computer systems – the fixed plus variable structure computer, (Proc. Western Joint IREAIEE-ACM Comput. Conf. (1960)), 33-40
[8]	Fasshauer, G. E., Matrix Approximation Methods with MATLAB (2007), World Scientific Publishers: World Scientific Publishers Singapore · Zbl 1123.65001
[9]	Golub, G.; Van Loan, C. F., Matrix Computations (1996), Johns Hopkins University Press: Johns Hopkins University Press Baltimore · Zbl 0865.65009
[10]	Górski, K. M.; Wandelt, B. D.; Hivon, E.; Hansen, F. K.; Banday, A. J., The HEALPix primer (1999)
[11]	Górski, K. M.; Wandelt, B. D.; Hivon, E.; Hansen, F. K.; Banday, A. J.; Reinecke, M.; Bartelmann, M., HEALPix – a framework for high resolution discretization, and fast analysis of data distributed on the sphere, Astrophys. J., 622, 759-771 (2005)
[12]	Greengard, L.; Lee, J., Accelerating the nonuniform fast Fourier transform, SIAM Rev., 46, 443-454 (2004) · Zbl 1064.65156
[13]	Greengard, L.; Rokhlin, V., A fast algorithm for particle simulations, J. Comput. Phys., 73, 325-348 (1987) · Zbl 0629.65005
[14]	Hardin, D. P.; Michaels, T.; Saff, E. B., A comparison of popular point configurations on \(\mathbb{S}^2\), Dolomites Res. Notes Approx., 9, 16-49 (2016) · Zbl 1370.31001
[15]	Hinshaw, G.; Larson, D.; Komatsu, E.; Spergel, D. N.; Bennett, C. L.; Dunkley, J.; Nolta, M. R.; Halpern, M.; Hill, R. S.; Odegard, N.; Page, L.; Smith, K. M.; Weiland, J. L.; Gold, B.; Jarosik, N.; Kogut, A.; Limon, M.; Meyer, S. S.; Tucker, G. S.; Wollack, E.; Wright, E. L., Nine-year Wilkinson microwave anisotropy probe (WMAP) observations: cosmological results, Astrophys. J. Suppl. Ser., 208, 19 (2013)
[16]	Hoover, R. C.; Maciejewski, A. A.; Roberts, R. G., Pose detection of 3-D objects using \(\mathbb{S}^2\)-correlated images and discrete spherical harmonic transforms, (2008 IEEE International Conference on Robotics and Automation (2008)), 993-998
[17]	Hu, W.; Dodelson, S., Cosmic microwave background anisotropies, Annu. Rev. Astron. Astrophys., 40, 171-216 (2002)
[18]	Hubbert, S.; Baxter, B. J.C., Radial basis functions for the sphere, (Recent Progress in Multivariate Approximation (Witten-Bommerholz, 2000). Recent Progress in Multivariate Approximation (Witten-Bommerholz, 2000), Internat. Ser. Numer. Math., vol. 137 (2001), Birkhäuser: Birkhäuser Basel), 33-47 · Zbl 1035.41012
[19]	Keiner, J.; Potts, D., Fast evaluation of quadrature formulae on the sphere, Math. Comput., 77, 397-419 (2008) · Zbl 1128.65110
[20]	Leopardi, P., A partition of the unit sphere into regions of equal area and small diameter, Electron. Trans. Numer. Anal., 25, 309-327 (2006) · Zbl 1160.51304
[21]	Majeau, C.; Agol, E.; Cowan, N. B., A two-dimensional infrared map of the extrasolar planet HD 189733b, Astrophys. J., 747, L20 (2012)
[22]	Malkin, Z., A new equal-area isolatitudinal grid on a spherical surface, Astron. J., 158, 158 (2019)
[23]	Merilees, P. E., The pseudospectral approximation applied to the shallow water equations on a sphere, Atmosphere, 11, 13-20 (1973)
[24]	Michielssen, E.; Boag, A., A multilevel matrix decomposition algorithm for analyzing scattering from large structures, IEEE Trans. Antennas Propag., 44, 1086-1093 (1996)
[25]	Miller, R. S.; Nerurkar, G.; Lawrence, D. J., Enhanced hydrogen at the lunar poles: new insights from the detection of epithermal and fast neutron signatures, J. Geophys. Res., Planets, 117 (2012)
[26]	O’Neil, M.; Woolfe, F.; Rokhlin, V., An algorithm for the rapid evaluation of special function transforms, Appl. Comput. Harmon. Anal., 28, 203-226 (2010) · Zbl 1191.65016
[27]	Paige, C. C.; Saunders, M. A., LSQR: an algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Softw., 8, 43-71 (1982) · Zbl 0478.65016
[28]	Paykari, P.; Starck, J.-L., CMB data analysis, Adv. Mach. Learning Data Mining Astron., 55-87 (2012)
[29]	Percival, W. J.; Cole, S.; Eisenstein, D. J.; Nichol, R. C.; Peacock, J. A.; Pope, A. C.; Szalay, A. S., Measuring the baryon acoustic oscillation scale using the sloan digital sky survey and 2dF galaxy redshift survey, Mon. Not. R. Astron. Soc., 381, 1053-1066 (2007)
[30]	Planck Collaboration 2005, Planck, the scientific programme, ESA publication ESA-SCI(2005)/01, (2005).
[31]	M. Reinecke. personal communication, June 5, 2019.
[32]	Roecker, C.; Bowden, N. S.; Carosi, G.; Heffner, M.; Jovanovic, I., Reconstruction algorithms for directional neutron detection using a time projection chamber, Nucl. Technol., 180, 231-240 (2012)
[33]	Ruiz-Antolín, D.; Townsend, A., A nonuniform fast Fourier transform based on low rank approximation, SIAM J. Sci. Comput., 40, A529-A547 (2018) · Zbl 1382.41006
[34]	Saff, E. B.; Kuijlaars, A. B.J., Distributing many points on a sphere, Math. Intell., 19, 5-11 (1997) · Zbl 0901.11028
[35]	Singer, L. P.; Price, L. R., Rapid Bayesian position reconstruction for gravitational-wave transients, Phys. Rev. D, 93, Article 024013 pp. (2016)
[36]	Slevinsky, R. M., FastTransforms
[37]	Slevinsky, R. M., FastTransforms.jl
[38]	Slevinsky, R. M., Fast and backward stable transforms between spherical harmonic expansions and bivariate fourier series, Appl. Comput. Harmon. Anal., 47, 585-606 (2019) · Zbl 1495.33006
[39]	Starck, J.-L.; Fadili, M. J.; Rassat, A., Low-ℓ CMB analysis and inpainting, Astron. Astrophys., 550 (2013)
[40]	Townsend, A.; Wilber, H.; Wright, G. B., Computing with functions in spherical and polar geometries I. The sphere, SIAM J. Sci. Comput., 38, C403-C425 (2016) · Zbl 1342.65083
[41]	Weimer, D. R.; Sutton, E. K.; Mlynczak, M. G.; Hunt, L. A., Intercalibration of neutral density measurements for mapping the thermosphere, J. Geophys. Res. Space Phys., 121, 5975-5990 (2016)
[42]	White, M., Anisotropies in the CMB, Proceedings of Division of Particles and Fields of the American Physical Society (1999)