Abstract
We show that the class of antenna layouts for telescope arrays allowing cheap analysis hardware (with correlator cost scaling as $N \log N$ rather than $N^2$ with the number of antennas $N$) is encouragingly large, including not only previously discussed rectangular grids but also arbitrary hierarchies of such grids, with arbitrary rotations and shears at each level. We show that all correlations for such a 2D array with an $n$-level hierarchy can be efficiently computed via a fast Fourier transform in not two but $2n$ dimensions. This can allow major correlator cost reductions for science applications requiring exquisite sensitivity at widely separated angular scales, for example, 21 cm tomography (where short baselines are needed to probe the cosmological signal and long baselines are needed for point source removal), helping enable future 21 cm experiments with thousands or millions of cheap dipolelike antennas. Such hierarchical grids combine the angular resolution advantage of traditional array layouts with the cost advantage of a rectangular fast Fourier transform telescope. We also describe an algorithm for how a subclass of hierarchical arrays can efficiently use rotation synthesis to produce global sky maps with minimal noise and a well-characterized synthesized beam.
Introduction: Breaking the $N^2$ Bottleneck
In radio astronomy, imaging the sky traditionally requires correlating the signal from every antenna with every other antenna. For an array with $N$ antennas, this necessitates $N(N-1)/2$ calculations, leading to an $O(N^2)$ scaling. While manageable for current arrays with hundreds of elements, this scaling presents a formidable technical and financial barrier for next-generation experiments. For instance, 21 cm tomography—mapping neutral hydrogen from the cosmic dawn—requires massive sensitivity, potentially demanding $10^5$ to $10^6$ antennas. At such scales, the cost of the correlator hardware would dwarf the cost of the antennas themselves.
Previous attempts to mitigate this cost involved grouping antennas into "tiles" or using simple rectangular grids. However, these solutions often sacrificed either information or resolution. This paper introduces a "best of both worlds" approach: the computational efficiency of a grid combined with the high resolution of a sparse, spread-out array.
Hierarchical Grid Layouts
The core innovation lies in the use of hierarchical grids. These are nested grids where each level can be independently rotated or sheared. This flexibility allows for a wide variety of baseline distributions while maintaining the mathematical structure necessary for efficient computation.
By arranging antennas in these nested structures, the array can capture signals across widely separated angular scales—utilizing short baselines for large-scale cosmological signals and long baselines for high-resolution point-source removal.
The Hypercube Algorithm
The authors propose the Hypercube Algorithm to exploit the inherent symmetry of hierarchical grids. The algorithm maps an $n$-level hierarchy into a $2n$-dimensional "hypercube." In this higher-dimensional space, the antenna distribution is no longer sparse, allowing the use of Fast Fourier Transforms (FFTs) to perform the heavy lifting.
By performing a multi-dimensional FFT, squaring the result, and then performing an inverse FFT, the system can compute all correlations with a scaling of $O(N \log N)$. This mathematical shift makes arrays with millions of antennas technically and economically feasible. Furthermore, the redundancy in these grids—where many antenna pairs measure the same baseline—provides a powerful tool for real-time self-calibration, helping to identify and subtract instrumental and ionospheric distortions.
Performance and Baseline Flexibility
Hierarchical grids are not limited to simple patterns; they can mimic the performance of optimized non-grid designs. The authors evaluate several configurations, demonstrating that hierarchical layouts can produce baseline distributions similar to the $r^{-2}$ radial density often used in optimized random arrays.
While a hierarchical grid may measure fewer unique visibilities in a single snapshot compared to a random array, the authors demonstrate that "rotation synthesis" (using the Earth's rotation to fill the $uv$-plane over time) can compensate for this, resulting in high-quality global sky maps with minimal noise.
Conclusion and Future Outlook
The "Omniscope" concept—an array that is effectively omnidirectional and omnichromatic—represents a significant leap for 21 cm cosmology. By reducing the computational cost from $N^2$ to $N \log N$, hierarchical arrays enable the use of massive numbers of cheap antennas to map the early universe with unprecedented resolution.
Future work will need to address the engineering challenges of physical wiring and synchronization for millions of elements, as well as the impact of large-scale placement errors on the algorithm's efficiency. Nevertheless, the theoretical framework provided here offers a clear path toward overcoming the computational bottleneck in radio astronomy.
Summary updated