HVOX: Scalable Interferometric Synthesis and Analysis of Spherical Sky Maps

Analysis and synthesis are key steps of the radio-interferometric imaging process, serving as a bridge between visibility and sky domains. They can be expressed as partial Fourier transforms involving a large number of non-uniform frequencies and spherically-constrained spatial coordinates. Due to the data non-uniformity, these partial Fourier transforms are computationally expensive and represent a serious bottleneck in the image reconstruction process. The W-gridding algorithm achieves log-linear complexity for both steps by applying a series of 2D non-uniform FFTs (NUFFT) to the data sliced along the so-called $w$ frequency coordinate. A major drawback of this method however is its restriction to direction-cosine meshes, which are fundamentally ill-suited for large field of views. This paper introduces the HVOX gridder, a novel algorithm for analysis/synthesis based on a 3D-NUFFT. Unlike W-gridding, the latter is compatible with arbitrary spherical meshes such as the popular HEALPix scheme for spherical data processing. The 3D-NUFFT allows one to optimally select the size of the inner FFTs, in particular the number of W-planes. This results in a better performing and auto-tuned algorithm, with controlled accuracy guarantees backed by strong results from approximation theory. To cope with the challenging scale of next-generation radio telescopes, we propose moreover a chunked evaluation strategy: by partitioning the visibility and sky domains, the 3D-NUFFT is decomposed into sub-problems which execute in parallel, while simultaneously cutting memory requirements. Our benchmarking results demonstrate the scalability of HVOX for both SKA and LOFAR, considering state-of-the-art challenging imaging setups. HVOX is moreover computationally competitive with W-gridder, despite the absence of domain-specific optimizations in our implementation.