  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.

Computational Engineering, Finance, and Science;Instrumentation and Methods for Astrophysics