Efficient algorithm for computing the time-resolved full-sky cross power in an interferometer with omnidirectional elements

We derive both time- and frequency-domain algorithms for the fast, approximate, numeric evaluation of the cross-correlation integral that appears in a variety of imaging applications. These algorithms possess a number of useful features. Their operation counts are linear in the amount (duration) of data to be processed, which allows them to be run quickly on small amounts of data, thereby allowing one to resolve time dependence in the sources being imaged. The algorithms also provide means by which to systematically increase or decrease their accuracy for increases and decreases in speed, respectively; that is to say, one can choose to obtain the result to lower accuracy and thereby obtain the result more quickly or with more modest computer requirements. The frequency-domain implementation is particularly fast and, on a 32-bit 1.8 GHz Pentium-M computer, has demonstrated the ability to synthesize full-sky cross-power images for a single baseline up to harmonic order 19, with a signal-to-noise ratio of 26 dB, at speeds of over 800 k sample/s.