  The Spreading Projection Algorithm for Rapid K-space samplING, or SPARKLING,
is an optimization-driven method that has been recently introduced for
accelerated 2D T2*-w MRI using compressed sensing. It has then been extended to
address 3D imaging using either stacks of 2D sampling patterns or a local 3D
strategy that optimizes a single sampling trajectory at a time. 2D SPARKLING
actually performs variable density sampling (VDS) along a prescribed target
density while maximizing sampling efficiency and meeting the gradient-based
hardware constraints. However, 3D SPARKLING has remained limited in terms of
acceleration factors along the third dimension if one wants to preserve a peaky
point spread function (PSF) and thus good image quality. In this paper, in
order to achieve higher acceleration factors in 3D imaging while preserving
image quality, we propose a new efficient algorithm that performs optimization
on full 3D SPARKLING. The proposed implementation based on fast multipole
methods (FMM) allows us to design sampling patterns with up to 10^7 k-space
samples, thus opening the door to 3D VDS. We compare multi-CPU and GPU
implementations and demonstrate that the latter is optimal for 3D imaging in
the high-resolution acquisition regime (600$\mu$m isotropic). Finally, we show
that this novel optimization for full 3D SPARKLING outperforms stacking
strategies or 3D twisted projection imaging through retrospective and
prospective studies on NIST phantom and in vivo brain scans at 3 Tesla. Overall
the proposed method allows for 2.5-3.75x shorter scan times compared to
GRAPPA-4 parallel imaging acquisition at 3 Tesla without compromising image
quality.
