Nicholas McKibben^{1,2} and Edward V. DiBella^{1,2}

^{1}Biomedical Engineering, University of Utah, Salt Lake City, UT, United States, ^{2}Radiology and Imaging Sciences, University of Utah, Salt Lake City, UT, United States

GROG is an attractive alternative to convolutional gridding and non-uniform DFT methods because of comparatively low cost and no density correction. However, for large multicoil datasets, many fractional matrix powers must be performed which scale with the cube of the number of channels. For SC-GROG and real-time SC-GROG, time and memory requirements can be significantly lowered for precomputation and updates of fractional powers by decomposing required powers into smaller, composable pieces. This is an NP-hard combinatorial change-making problem. We propose a simple solution based on prime factorization which leads to significant computational and memory savings with little performance degradation.

We desire to find the fewest fractional matrix powers to produce the

- Seiberlich, Nicole, et al. “Self‐calibrating GRAPPA operator gridding for radial and spiral trajectories.”
*Magnetic Resonance in Medicine: An Official Journal of the International Society for Magnetic Resonance in Medicine*59.4 (2008): 930-935. - Higham, Nicholas J., and Lijing Lin. “An improved Schur--Padé algorithm for fractional powers of a matrix and their Fréchet derivatives.”
*SIAM Journal on Matrix Analysis and Applications*34.3 (2013): 1341-1360. - Saybasili, Haris, et al. “RT‐GROG: parallelized self‐calibrating GROG for real‐time MRI.”
*Magnetic resonance in medicine*64.1 (2010): 306-312. - Wright, J. W. “The change-making problem.”
*Journal of the ACM (JACM)*22.1 (1975): 125-128. - Midorikawa, Shiho, primefac, GitHub repository, https://github.com/elliptic-shiho/primefac-fork

Figure 1: Number of fractional matrix powers required vs number of samples acquired for a radial trajectory. Prime factorization accelerated SC-GROG far outperforms traditional radial SC-GROG in number of required matrix powers.

Figure 2: Comparison of traditional SC-GROG and the proposed prime factorization accelerated SC-GROG. The 8-channel Shepp-Logan phantom was radially-sampled (72 rays, 288 samples per ray). The gridded results are virtually identical while the proposed method yields a 4x speed-up of fractional matrix power dictionary precomputation.

Figure 3: Comparison of traditional SC-GROG and the proposed prime factorization accelerated SC-GROG. The cardiac data was radially sampled (72 rays, 256 samples per ray, 9 channels). The gridded results are again virtually identical with the proposed method yielding a 4.2x speed-up of fractional matrix power dictionary precomputation with negligible error.