An Efficient Technique to Determine the Power Spectrum from Cosmic Microwave Background Sky Maps

There is enormous potential to advance cosmology from statistical characterizations of cosmic microwave background sky maps. The angular power spectrum of the microwave anisotropy is a particularly important statistic. Existing algorithms for computing the angular power spectrum of a pixelized map typically require O(N^3) operations and O(N^2) storage, where N is the number of independent pixels in the map. The MAP and Planck satellites will produce megapixel maps of the cosmic microwave background temperature at multiple frequencies; thus, existing algorithms are not computationally feasible. In this article, we introduce an algorithm that requires O(N^2) operations and O(N^1.5) storage that can find the minimum variance power spectrum from sky map data roughly one million times faster than was previously possible. This makes feasible an analysis that was hitherto intractable.