Since the arrays described above are sparse, it makes sense to try to deal with only the 1-D arrays corresponding to the 9 UV circles themselves. This strategy, however, has its own inefficiencies. For example, if one wanted to use a Fourier transform of the visibilities to make a map, one would have to compute the quantities:
for all the (uk,vk) points and all the (x,y) map points. The minimum number of x values required for 9-collimator maps is about 360, corresponding to one pitch of the coarsest collimator and 1'' pixels. Using a brute-force method, a map would require calculations of the exponentials in the above equation. Rough timing measurements in IDL show that this is about 80 times slower than computing the FFT of a complex array. So, although we have reduced memory requirements by about a factor of 129 (40962/3602), we have lost a factor of 80 in time.
Considerable savings in storage and computations, fortunately, can be gotten by exploiting the facts that the exponentials in equation (1) need only be computed along on one row and one column of the map, and that the map's rows and columns are equally spaced, so one may compute the other entries by recursive multiplication by a constant phasor:
This reduces the storage and computational requirements by a factor proportional to the map dimension, M. In practice, IDL tests with M=360 give a speedup by a factor of about 3.5. The overall speed would still be slower than the rectangular (FFT) method.