The Nussbaumer–Quandalle 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. 57 | 1 | 2 |

Section 1.3.3.3.2.4. The Nussbaumer–Quandalle 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.4. The Nussbaumer–Quandalle algorithm

| top | pdf |

Nussbaumer's approach views the DFT as the evaluation of certain polynomials constructed from the data (as in Section 1.3.3.2.4). For instance, putting $[\omega = e(1/N)]$ , the 1D N-point DFT $[X^{*}(k^{*}) = {\textstyle\sum\limits_{k = 0}^{N - 1}} X(k) \omega^{k^{*}k}]$ may be written $[X^{*}(k^{*}) = Q(\omega^{k^{*}}),]$ where the polynomial Q is defined by $[Q(z) = {\textstyle\sum\limits_{k = 0}^{N - 1}} X(k)z^{k}.]$

Let us consider (Nussbaumer & Quandalle, 1979) a 2D transform of size $[N \times N]$ : $[X^{*}(k_{1}^{*}, k_{2}^{*}) = {\textstyle\sum\limits_{k_{1} = 0}^{N - 1}}\; {\textstyle\sum\limits_{k_{2} = 0}^{N - 1}} X(k_{1}, k_{2}) \omega^{k_{1}^{*} k_{1} + k_{2}^{*} k_{2}}.]$ By introduction of the polynomials $[\eqalign{Q_{k_{2}}(z) &= {\textstyle\sum\limits_{k_{1}}}\; X (k_{1}, k_{2})z^{k_{1}} \cr R_{k_{2}^{*}}(z) &= {\textstyle\sum\limits_{k_{2}}}\; \omega^{k_{2}^{*} k_{2}} Q_{k_{2}}(z),}]$ this may be rewritten: $[X^{*}(k_{1}^{*}, k_{2}^{*}) = R_{k_{2}^{*}} (\omega^{k_{1}^{*}}) = {\textstyle\sum\limits_{k_{2}}}\; \omega^{k_{2}^{*} k_{2}} Q_{k_{2}} (\omega^{k_{1}^{*}}).]$

Let us now suppose that $[k_{1}^{*}]$ is coprime to N. Then $[k_{1}^{*}]$ has a unique inverse modulo N (denoted by $[1/k_{1}^{*}]$ ), so that multiplication by $[k_{1}^{*}]$ simply permutes the elements of $[{\bb Z}/N {\bb Z}]$ and hence $[{\textstyle\sum\limits_{k_{2} = 0}^{N - 1}} f(k_{2}) = {\textstyle\sum\limits_{k_{2} = 0}^{N - 1}} f(k_{1}^{*} k_{2})]$ for any function f over $[{\bb Z}/N {\bb Z}]$ . We may thus write: $[\eqalign{X^{*}(k_{1}^{*}, k_{2}^{*}) &= {\textstyle\sum\limits_{k_{2}}} \;\omega^{k_{1}^{*} k_{2}^{*} k_{2}} Q_{k_{1}^{*} k_{2}} (\omega^{k_{1}^{*}}) \cr &= S_{k_{1}^{*} k_{2}} (\omega^{k_{1}^{*}})}]$ where $[S_{k^{*}}(z) = {\textstyle\sum\limits_{k_{2}}}\; z^{k^{*} k_{2}} Q_{k_{2}}(z).]$ Since only the value of polynomial $[S_{k^{*}}(z)]$ at $[z = \omega^{k_{1}^{*}}]$ is involved in the result, the computation of $[S_{k^{*}}]$ may be carried out modulo the unique cyclotomic polynomial [P(z)] such that $[P(\omega^{k_{1}^{*}}) = 0]$ . Thus, if we define: $[T_{k^{*}}(z) = {\textstyle\sum\limits_{k_{2}}} \;z^{k^{*} k_{2}} Q_{k_{2}}(z) \hbox{ mod } P(z)]$ we may write: $[X^{*}(k_{1}^{*}, k_{2}^{*}) = T_{k_{1}^{*} k_{2}^{*}} (\omega^{k_{1}^{*}})]$ or equivalently $[X^{*} \left(k_{1}^{*}, {k_{2}^{*} \over k_{1}^{*}}\right) = T_{k_{2}^{*}} (\omega^{k_{1}^{*}}).]$

For N an odd prime p, all non-zero values of $[k_{1}^{*}]$ are coprime with p so that the $[p \times p]$ -point DFT may be calculated as follows:

(1) form the polynomials $[T_{k_{2}^{*}}(z) = {\textstyle\sum\limits_{k_{1}}} {\textstyle\sum\limits_{k_{2}}} \;X(k_{1}, k_{2})z^{k_{1} + k_{2}^{*} k_{2}} \hbox{ mod } P(z)]$ for $[k_{2}^{*} = 0, \ldots, p - 1]$ ;
(2) evaluate $[T_{k_{2}^{*}} (\omega^{k_{1}^{*}})]$ for $[k_{1}^{*} = 0, \ldots, p - 1]$ ;
(3) put $[X^{*}(k_{1}^{*}, k_{2}^{*}/k_{1}^{*}) = T_{k_{2}^{*}} (\omega^{k_{1}^{*}})]$ ;
(4) calculate the terms for $[k_{1}^{*} = 0]$ separately by $[X^{*}(0, k_{2}^{*}) = {\textstyle\sum\limits_{k_{2}}} \left[{\textstyle\sum\limits_{k_{1}}} \;X(k_{1}, k_{2})\right] \omega^{k_{2}^{*} k_{2}}.]$

Step (1) is a set of p `polynomial transforms' involving no multiplications; step (2) consists of p DFTs on p points each since if $[T_{k_{2}^{*}}(z) = {\textstyle\sum\limits_{k_{1}}}\; Y_{k_{2}^{*}}(k_{1})z^{k_{1}}]$ then $[T_{k_{2}^{*}} (\omega^{k_{1}^{*}}) = {\textstyle\sum\limits_{k_{1}}} \;Y_{k_{2}^{*}}(k_{1}) \omega^{k_{1}^{*} k_{1}} = Y_{k_{2}^{*}}^{*}(k_{1}^{*})\hbox{;}]$ step (3) is a permutation; and step (4) is a p-point DFT. Thus the 2D DFT on $[p \times p]$ points, which takes 2p p-point DFTs by the row–column method, involves only [(p + 1)] p-point DFTs; the other DFTs have been replaced by polynomial transforms involving only additions.

This procedure can be extended to n dimensions, and reduces the number of 1D p-point DFTs from $[np^{n - 1}]$ for the row–column method to $[(p^{n} -1)/(p - 1)]$ , at the cost of introducing extra additions in the polynomial transforms.

A similar algorithm has been formulated by Auslander et al. (1983) in terms of Galois theory.

References

Auslander, L., Feig, E. & Winograd, S. (1983). New algorithms for the multidimensional discrete Fourier transform. IEEE Trans. Acoust. Speech Signal Process. 31, 388–403.Google Scholar

Nussbaumer, H. J. & Quandalle, P. (1979). Fast computation of discrete Fourier transforms using polynomial transforms. IEEE Trans. Acoust. Speech Signal Process. 27, 169–181.Google Scholar

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