Likelihood analysis of mega-pixel maps

The derivation of cosmological parameters from astrophysical data sets rout inely involves operations counts which scale as O(N-3), where N is the numb er of data points. Currently planned missions, including Microwave Anisotro py Probe and Planck, will generate sky maps with N-d = 10(6) or more pixels . Simple "brute-force" analysis, applied to such mega-pixel data, would req uire years of computing even on the fastest computers. We describe an algor ithm that allows estimation of the likelihood function in the direct pixel basis. The algorithm uses a conjugate gradient approach to evaluate chi(2) and a geometric approximation to evaluate the determinant. Monte Carlo simu lations provide a correction to the determinant, yielding an unbiased estim ate of the likelihood surface in an arbitrary region surrounding the likeli hood peak. The algorithm requires O(N-d(3/2)) operations and O(N-d) storage for each likelihood evaluation and allows for significant parallel computa tion.