Multidimensional prime factor algorithm

Bricogne, G.

doi:10.1107/97809553602060000551

International
Tables for
Crystallography
Volume B
Reciprocal space
Edited by U. Shmueli

pdf | chapter contents | chapter index | related articles

International Tables for Crystallography (2006). Vol. B. ch. 1.3, p. 56 | 1 | 2 |

Section 1.3.3.3.2.2. Multidimensional prime factor algorithm

G. Bricogne^a

^a MRC Laboratory of Molecular Biology, Hills Road, Cambridge CB2 2QH, England, and LURE, Bâtiment 209D, Université Paris-Sud, 91405 Orsay, France

1.3.3.3.2.2. Multidimensional prime factor algorithm

| top | pdf |

Suppose that the decimation matrix N is diagonal $[{\bf N} = \hbox{diag } (N^{(1)}, N^{(2)}, \ldots, N^{(n)})]$ and let each diagonal element be written in terms of its prime factors: $[N^{(i)} = {\textstyle\prod\limits_{j = 1}^{m}} \;p_{j}^{\nu (i, \, \;j)},]$ where m is the total number of distinct prime factors present in the $[N^{(i)}]$ .

The CRT may be used to turn each 1D transform along dimension i $[(i = 1, \ldots, n)]$ into a multidimensional transform with a separate `pseudo-dimension' for each distinct prime factor of $[N^{(i)}]$ ; the number $[\mu_{i}]$ , of these pseudo-dimensions is equal to the cardinality of the set: $[\{\;j \in \{1, \ldots, m\} | \nu (i,j) \gt 0 \hbox{ for some } i\}.]$ The full n-dimensional transform thus becomes μ-dimensional, with $[\mu = {\textstyle\sum_{i = 1}^{n}} \mu_{i}]$ .

We may now permute the μ pseudo-dimensions so as to bring into contiguous position those corresponding to the same prime factor $[p_{j}]$ ; the m resulting groups of pseudo-dimensions are said to define `p-primary' blocks. The initial transform is now written as a tensor product of m p-primary transforms, where transform j is on $[p_{j}^{\nu (1, \, \;j)} \times p_{j}^{\nu (2, \, j)} \times \ldots \times p_{j}^{\nu (n, \, j)}]$ points [by convention, dimension i is not transformed if $[\nu (i,j) = 0]$ ]. These p-primary transforms may be computed, for instance, by multidimensional Cooley–Tukey factorization (Section 1.3.3.3.1), which is faster than the straightforward row–column method. The final results may then be obtained by reversing all the permutations used.

The extra gain with respect to the multidimensional Cooley–Tukey method is that there are no twiddle factors between p-primary pieces corresponding to different primes p.

The case where N is not diagonal has been examined by Guessoum & Mersereau (1986).

References

Guessoum, A. & Mersereau, R. M. (1986). Fast algorithms for the multidimensional discrete Fourier transform. IEEE Trans. Acoust. Speech Signal Process. 34, 937–943.Google Scholar

International Tables for Crystallography (2006). Vol. B. ch. 1.3, p. 56