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

International Tables for Crystallography (2010). Vol. B, ch. 1.3, pp. 58-62   | 1 | 2 |

Section 1.3.3.3. Multidimensional algorithms

G. Bricognea

aGlobal Phasing Ltd, Sheraton House, Suites 14–16, Castle Park, Cambridge CB3 0AX, England, and LURE, Bâtiment 209D, Université Paris-Sud, 91405 Orsay, France

1.3.3.3. Multidimensional algorithms

| top | pdf |

From an algorithmic point of view, the distinction between one-dimensional (1D) and multidimensional DFTs is somewhat blurred by the fact that some factoring techniques turn a 1D transform into a multidimensional one. The distinction made here, however, is a practical one and is based on the dimensionality of the indexing sets for data and results. This section will therefore be concerned with the problem of factoring the DFT when the indexing sets for the input data and output results are multidimensional.

1.3.3.3.1. The method of successive one-dimensional transforms

| top | pdf |

The DFT was defined in Section 1.3.2.7.4[link] in an n-dimensional setting and it was shown that when the decimation matrix N is diagonal, say [{\bf N} = \hbox{diag} (N^{(1)}, N^{(2)}, \ldots, N^{(n)})], then [\bar{F} (N)] has a tensor product structure:[\bar{F} ({\bf N}) = \bar{F} (N^{(1)}) \otimes \bar{F} (N^{(2)}) \otimes \ldots \otimes \bar{F} (N^{(n)}).]This may be rewritten as follows:[\eqalign{\bar{F} ({\bf N}) &= [\bar{F} (N^{(1)}) \otimes I_{N^{(2)}} \otimes \ldots \otimes I_{N^{(n)}}] \cr &\quad \times [I_{N^{(1)}} \otimes \bar{F} (N^{(2)}) \otimes \ldots \otimes I_{{N}^{(n)}}] \cr &\quad \times \ldots \cr &\quad \times [I_{N^{(1)}} \otimes I_{N^{(2)}} \otimes \ldots \otimes \bar{F} (N^{(n)}],}]where the I's are identity matrices and × denotes ordinary matrix multiplication. The matrix within each bracket represents a one-dimensional DFT along one of the n dimensions, the other dimensions being left untransformed. As these matrices commute, the order in which the successive 1D DFTs are performed is immaterial.

This is the most straightforward method for building an n-dimensional algorithm from existing 1D algorithms. It is known in crystallography under the name of `Beevers–Lipson factorization' (Section 1.3.4.3.1[link]), and in signal processing as the `row–column method'.

1.3.3.3.2. Multidimensional factorization

| top | pdf |

Substantial reductions in the arithmetic cost, as well as gains in flexibility, can be obtained if the factoring of the DFT is carried out in several dimensions simultaneously. The presentation given here is a generalization of that of Mersereau & Speake (1981)[link], using the abstract setting established independently by Auslander, Tolimieri & Winograd (1982)[link].

Let us return to the general n-dimensional setting of Section 1.3.2.7.4[link], where the DFT was defined for an arbitrary decimation matrix N by the formulae (where [|{\bf N}|] denotes [| \hbox{det }{\bf N}|]):[\eqalign{F ({\bf N})&:\quad X ({\bf k}) \,\,\,= {1 \over |{\bf N}|} {\sum\limits_{{\bf k}^{*}}} \,X^{*} ({\bf k}^{*}) e[-{\bf k}^{*} \cdot ({\bf N}^{-1} {\bf k})] \cr \bar{F} ({\bf N})&:\quad X^{*} ({\bf k}^{*}) = \phantom{{1 \over |{\bf N}|}} {\sum\limits_{{\bf k}}} \,X ({\bf k}) e[{\bf k}^{*} \cdot ({\bf N}^{-1} {\bf k})]}]with[{\bf k} \in {\bb Z}^{n} / {\bf N} {\bb Z}^{n},\quad {\bf k}^{*} \in {\bb Z}^{n} / {\bf N}^{T} {\bb Z}^{n}.]

1.3.3.3.2.1. Multidimensional Cooley–Tukey factorization

| top | pdf |

Let us now assume that this decimation can be factored into d successive decimations, i.e. that[{\bf N} = {\bf N}_{1} {\bf N}_{2} \ldots {\bf N}_{d-1} {\bf N}_{d}]and hence[{\bf N}^{T} = {\bf N}_{d}^{T} {\bf N}_{d - 1}^{T} \ldots {\bf N}_{2}^{T} {\bf N}_{1}^{T}.]Then the coset decomposition formulae corresponding to these successive decimations (Section 1.3.2.7.1[link]) can be combined as follows:[\eqalign{{\bb Z}^{n} &= \bigcup_{{\bf k}_{1}}\, ({\bf k}_{1} + {\bf N}_{1} {\bb Z}^{n}) \cr &= \bigcup_{{\bf k}_{1}}\, \left\{{\bf k}_{1} + {\bf N}_{1} \left[\bigcup_{{\bf k}_{2}}\, ({\bf k}_{2} + {\bf N}_{2} {\bb Z}^{n})\right]\right\} \cr &= \ldots \cr &= \bigcup_{{\bf k}_{1}} \ldots \bigcup_{{\bf k}_{d}}\, ({\bf k}_{1} + {\bf N}_{1} {\bf k}_{2} + \ldots + {\bf N}_{1} {\bf N}_{2} \times \ldots \times {\bf N}_{d - 1} {\bf k}_{d} + {\bf N} {\bb Z}^{n})}]with [{\bf k}_{j} \in {\bb Z}^{n} / {\bf N}_{j} {\bb Z}^{n}]. Therefore, any [{\bf k} \in {\bb Z} / {\bf N} {\bb Z}^{n}] may be written uniquely as[{\bf k} = {\bf k}_{1} + {\bf N}_{1} {\bf k}_{2} + \ldots + {\bf N}_{1} {\bf N}_{2} \times \ldots \times {\bf N}_{d - 1} {\bf k}_{d}.]Similarly:[\eqalign{{\bb Z}^{n} &= \bigcup_{{\bf k}_{d}^{*}}\, ({\bf k}_{d}^{*} + {\bf N}_{d}^{T} {\bb Z}^{n}) \cr &= \ldots \cr &= \bigcup_{{\bf k}_{d}^{*}} \ldots \bigcup_{{\bf k}_{1}^{*}} \,({\bf k}_{d}^{*} + {\bf N}_{d}^{T} {\bf k}_{d - 1}^{*} + \ldots + {\bf N}_{d}^{T} \times \ldots \times {\bf N}_{2}^{T} {\bf k}_{1}^{*} \cr &\quad + {\bf N}^{T} {\bb Z}^{n})}]so that any [{\bf k}^{*} \in {\bb Z}^{n} / {\bf N}^{T} {\bb Z}^{n}] may be written uniquely as[{\bf k}^{*} = {\bf k}_{d}^{*} + {\bf N}_{d}^{T} {\bf k}_{d - 1}^{*} + \ldots + {\bf N}_{d}^{T} \times \ldots \times {\bf N}_{2}^{T} {\bf k}_{1}^{*}]with [{\bf k}_{j}^{*} \in {\bb Z}^{n} / {\bf N}_{j}^{T} {\bb Z}^{n}]. These decompositions are the vector analogues of the multi-radix number representation systems used in the Cooley–Tukey factorization.

We may then write the definition of [\bar{F} ({\bf N})] with [d = 2] factors as[\eqalign{X^{*} ({\bf k}_{2}^{*} + {\bf N}_{2}^{T} {\bf k}_{1}^{*}) &= {\textstyle\sum\limits_{{\bf k}_{1}}} {\textstyle\sum\limits_{{\bf k}_{2}}}\, X ({\bf k}_{1} + {\bf N}_{1} {\bf k}_{2}) \cr &\quad \times e[({\bf k}_{2}^{*T} + {\bf k}_{1}^{*T}{\bf N}_2) {\bf N}_{2}^{-1} {\bf N}_{1}^{-1} ({\bf k}_{1} + {\bf N}_{1} {\bf k}_{2})].}]The argument of e(–) may be expanded as[{\bf k}_{2}^{*} \cdot ({\bf N}^{-1} {\bf k}_{1}) + {\bf k}_{1}^{*} \cdot ({\bf N}_{1}^{-1} {\bf k}_{1}) + {\bf k}_{2}^{*} \cdot ({\bf N}_{2}^{-1} {\bf k}_{2}) + {\bf k}_{1}^{*} \cdot {\bf k}_{2}.]The first summand may be recognized as a twiddle factor, the second and third as the kernels of [\bar{F} ({\bf N}_{1})] and [\bar{F} ({\bf N}_{2})], respectively, while the fourth is an integer which may be dropped. We are thus led to a `vector-radix' version of the Cooley–Tukey algorithm, in which the successive decimations may be introduced in all n dimensions simultaneously by general integer matrices. The computation may be decomposed into five stages analogous to those of the one-dimensional algorithm of Section 1.3.3.2.1[link]:

  • (i) form the [|{\bf N}_{1}|] vectors [{\bf Y}_{{\bf k}_{1}}] of shape [{\bf N}_{2}] by[Y_{{\bf k}_{1}} ({\bf k}_{2}) = X ({\bf k}_{1} + {\bf N}_{1} {\bf k}_{2}),\quad {\bf k}_{1} \in {\bb Z}^{n} / {\bf N}_{1} {\bb Z}^{n},\quad {\bf k}_{2} \in {\bb Z}^{n} / {\bf N}_{2} {\bb Z}^{n}\hbox{\semi}]

  • (ii) calculate the [|{\bf N}_{1}|] transforms [{\bf Y}_{{\bf k}_{1}}^{*}] on [|{\bf N}_{2}|] points:[Y_{{\bf k}_{1}}^{*} ({\bf k}_{2}^{*}) = {\textstyle\sum\limits_{{\bf k}_{2}}}\, e[{\bf k}_{2}^{*} \cdot ({\bf N}_{2}^{-1} {\bf k}_{2})] Y_{{\bf k}_{1}} ({\bf k}_{2}),\quad {\bf k}_{1} \in {\bb Z}^{n} / {\bf N}_{1} {\bb Z}^{n}\hbox{\semi}]

  • (iii) form the [|{\bf N}_{2}|] vectors [{\bf Z}_{{\bf k}_{2}^{*}}] of shape [{\bf N}_{1}] by[\displaylines{Z_{{\bf k}_{2}^{*}} ({\bf k}_{1}) = e[{\bf k}_{2}^{*} \cdot ({\bf N}^{-1} {\bf k}_{1})] Y_{{\bf k}_{1}}^{*} ({\bf k}_{2}^{*}),\quad {\bf k}_{1} \in {\bb Z}^{n} / {\bf N}_{1} {\bb Z}^{n},\cr {\bf k}_{2}^{*} \in {\bb Z}^{n} / {\bf N}_{2}^{T} {\bb Z}^{n}\hbox{\semi}}]

  • (iv) calculate the [|{\bf N}_{2}|] transforms [{\bf Z}_{{\bf k}_{2}^{*}}^{*}] on [|{\bf N}_{1}|] points:[Z_{{\bf k}_{2}^{*}}^{*} ({\bf k}_{1}^{*}) = {\textstyle\sum\limits_{{\bf k}_{1}}}\, e[{\bf k}_{1}^{*} \cdot ({\bf N}_{1}^{-1} {\bf k}_{1})] Z_{{\bf k}_{2}^{*}} ({\bf k}_{1}),\quad {\bf k}_{2}^{*} \in {\bb Z}^{n} / {\bf N}_{2}^{T} {\bb Z}^{n}\hbox{\semi}]

  • (v) collect [X^{*} ({\bf k}_{2}^{*} + {\bf N}_{2}^{T} {\bf k}_{1}^{*})] as [Z_{{\bf k}_{2}^{*}}^{*} ({\bf k}_{1}^{*})].

The initial [|{\bf N}|]-point transform [\bar{F} ({\bf N})] can thus be performed as [|{\bf N}_{1}|] transforms [\bar{F} ({\bf N}_{2})] on [|{\bf N}_{2}|] points, followed by [|{\bf N}_{2}|] transforms [\bar{F} ({\bf N}_{1})] on [|{\bf N}_{1}|] points. This process can be applied successively to all d factors. The same decomposition applies to [F ({\bf N})], up to the complex conjugation of twiddle factors, the normalization factor [1 / |{\bf N}|] being obtained as the product of the factors [1 / |{\bf N}_{j}|] in the successive partial transforms [F ({\bf N}_{j})].

The geometric interpretation of this factorization in terms of partial transforms on translates of sublattices applies in full to this n-dimensional setting; in particular, the twiddle factors are seen to be related to the residual translations which place the sublattices in register within the big lattice. If the intermediate transforms are performed in place, then the quantity[X^{*} ({\bf k}_{d}^{*} + {\bf N}_{d}^{T} {\bf k}_{d - 1}^{*} + \ldots + {\bf N}_{d}^{T} {\bf N}_{d - 1}^{T} \times \ldots \times {\bf N}_{2}^{T} {\bf k}_{1}^{*})]will eventually be found at location[{\bf k}_{1}^{*} + {\bf N}_{1} {\bf k}_{2}^{*} + \ldots + {\bf N}_{1} {\bf N}_{2} \times \ldots \times {\bf N}_{d - 1} {\bf k}_{d}^{*},]so that the final results will have to be unscrambled by a process which may be called `coset reversal', the vector equivalent of digit reversal.

Factoring by 2 in all n dimensions simultaneously, i.e. taking [{\bf N} = 2{\bf M}], leads to `n-dimensional butterflies'. Decimation in time corresponds to the choice [{\bf N}_{1} = 2{\bf I}, {\bf N}_{2} = {\bf M}], so that [{\bf k}_{1} \in {\bb Z}^{n} / 2{\bb Z}^{n}] is an n-dimensional parity class; the calculation then proceeds by[\displaylines{Y_{{\bf k}_{1}} ({\bf k}_{2}) = X ({\bf k}_{1} + 2{\bf k}_{2}),\quad{\bf k}_{1} \in {\bb Z}^{n} / 2{\bb Z}^{n},\quad {\bf k}_{2} \in {\bb Z}^{n} / {\bf M}{\bb Z}^{n}, \cr Y_{{\bf k}_{1}}^{*} = \bar{F} ({\bf M}) [{\bf Y}_{{\bf k}_{1}}],\quad{\bf k}_{1} \in {\bb Z}^{n} / 2{\bb Z}^{n}\hbox{\semi} \cr \eqalign{X^{*} ({\bf k}_{2}^{*} + {\bf M}^{T} {\bf k}_{1}^{*}) &= {\textstyle\sum\limits_{{\bf k}_{1} \in {\bb Z}^{n} / 2{\bb Z}^{n}}} (-1)^{{\bf k}_{1}^{*} \cdot {\bf k}_{1}} \cr &\quad \times e[{\bf k}_{2}^{*} \cdot ({\bf N}^{-1} {\bf k}_{1})] Y_{{\bf k}_{1}}^{*} ({\bf k}_{2}^{*}).}\cr}]Decimation in frequency corresponds to the choice [{\bf N}_{1} = {\bf M}], [{\bf N}_{2} = 2{\bf I}], so that [{\bf k}_{2} \in {\bb Z}^{n} / 2{\bb Z}^{n}] labels `octant' blocks of shape M; the calculation then proceeds through the following steps:[\eqalign{Z_{{\bf k}_{2}^{*}} ({\bf k}_{1}) &= \left[{\textstyle\sum\limits_{{\bf k}_{2} \in {\bb Z}^{n} / 2{\bb Z}^{n}}} (-1)^{{\bf k}_{2}^{*} \cdot {\bf k}_{2}} X ({\bf k}_{1} + {\bf M}{\bf k}_{2})\right] \cr &\quad \times e[{\bf k}_{2}^{*} \cdot ({\bf N}^{-1} {\bf k}_{1})], \cr {\bf Z}_{{\bf k}_{2}^{*}}^{*} &= \bar{F} ({\bf M}) [{\bf Z}_{{\bf k}_{2}^{*}}], \cr X^{*} ({\bf k}_{2}^{*} + 2{\bf k}_{1}^{*}) &= Z_{{\bf k}_{2}^{*}}^{*} ({\bf k}_{1}^{*}),}]i.e. the [2^{n}] parity classes of results, corresponding to the different [{\bf k}_{2}^{*} \in {\bb Z}^{n} / 2{\bb Z}^{n}], are obtained separately. When the dimension n is 2 and the decimating matrix is diagonal, this analysis reduces to the `vector radix FFT' algorithms proposed by Rivard (1977)[link] and Harris et al. (1977)[link]. These lead to substantial reductions in the number M of multiplications compared to the row–column method: M is reduced to [3M/4] by simultaneous [2 \times 2] factoring, and to [15M/32] by simultaneous [4 \times 4] factoring.

The use of a nondiagonal decimating matrix may bring savings in computing time if the spectrum of the band-limited function under study is of such a shape as to pack more compactly in a nonrectangular than in a rectangular lattice (Mersereau, 1979[link]). If, for instance, the support K of the spectrum Φ is contained in a sphere, then a decimation matrix producing a close packing of these spheres will yield an aliasing-free DFT algorithm with fewer sample points than the standard algorithm using a rectangular lattice.

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[link]), 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)[link].

1.3.3.3.2.3. Nesting of Winograd small FFTs

| top | pdf |

Suppose that the CRT has been used as above to map an n-dimensional DFT to a μ-dimensional DFT. For each [\kappa = 1, \ldots, \mu] [κ runs over those pairs (i, j) such that [\nu (i,j) \,\gt\, 0]], the Rader/Winograd procedure may be applied to put the matrix of the κth 1D DFT in the CBA normal form of a Winograd small FFT. The full DFT matrix may then be written, up to permutation of data and results, as[\bigotimes_{\kappa = 1}^{\mu}({\bf C}_{\kappa} {\bf B}_{\kappa} {\bf A}_{\kappa}).]

A well known property of the tensor product of matrices allows this to be rewritten as[\left(\bigotimes_{\gamma = 1}^{\mu} {\bf C}_{\gamma}\right) \times \left(\bigotimes_{\beta = 1}^{\mu} {\bf B}_{\beta}\right) \times \left(\bigotimes_{\alpha = 1}^{\mu} {\bf A}_{\alpha}\right)]and thus to form a matrix in which the combined pre-addition, multiplication and post-addition matrices have been precomputed. This procedure, called nesting, can be shown to afford a reduction of the arithmetic operation count compared to the row–column method (Morris, 1978[link]).

Clearly, the nesting rearrangement need not be applied to all μ dimensions, but can be restricted to any desired subset of them.

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[link]). 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[link]) 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 nonzero 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)[link] is a set of p `polynomial transforms' involving no multiplications; step (2)[link] 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{\semi}]step (3)[link] is a permutation; and step (4)[link] 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)[link] in terms of Galois theory.

1.3.3.3.3. Global algorithm design

| top | pdf |

1.3.3.3.3.1. From local pieces to global algorithms

| top | pdf |

The mathematical analysis of the structure of DFT computations has brought to light a broad variety of possibilities for reducing or reshaping their arithmetic complexity. All of them are `analytic' in that they break down large transforms into a succession of smaller ones.

These results may now be considered from the converse `synthetic' viewpoint as providing a list of procedures for assembling them:

  • (i) the building blocks are one-dimensional p-point algorithms for p a small prime;

  • (ii) the low-level connectors are the multiplicative reindexing methods of Rader and Winograd, or the polynomial transform reindexing method of Nussbaumer and Quandalle, which allow the construction of efficient algorithms for larger primes p, for prime powers [p^{\nu}], and for p-primary pieces of shape [p^{\nu} \times \ldots \times p^{\nu}];

  • (iii) the high-level connectors are the additive reindexing scheme of Cooley–Tukey, the Chinese remainder theorem reindexing, and the tensor product construction;

  • (iv) nesting may be viewed as the `glue' which seals all elements.

The simplest DFT may then be carried out into a global algorithm in many different ways. The diagrams in Fig. 1.3.3.1[link] illustrate a few of the options available to compute a 400-point DFT. They may differ greatly in their arithmetic operation counts.

[Figure 1.3.3.1]

Figure 1.3.3.1 | top | pdf |

A few global algorithms for computing a 400-point DFT. CT: Cooley–Tukey factorization. PF: prime factor (or Good) factorization. W: Winograd algorithm.

1.3.3.3.3.2. Computer architecture considerations

| top | pdf |

To obtain a truly useful measure of the computational complexity of a DFT algorithm, its arithmetic operation count must be tempered by computer architecture considerations. Three main types of trade-offs must be borne in mind:

  • (i) reductions in floating-point (f.p.) arithmetic count are obtained by reindexing, hence at the cost of an increase in integer arithmetic on addresses, although some shortcuts may be found (Uhrich, 1969[link]; Burrus & Eschenbacher, 1981[link]);

  • (ii) reduction in the f.p. multiplication count usually leads to a large increase in the f.p. addition count (Morris, 1978[link]);

  • (iii) nesting can increase execution speed, but causes a loss of modularity and hence complicates program development (Silverman, 1977[link]; Kolba & Parks, 1977[link]).

Many of the mathematical developments above took place in the context of single-processor serial computers, where f.p. addition is substantially cheaper than f.p. multiplication but where integer address arithmetic has to compete with f.p. arithmetic for processor cycles. As a result, the alternatives to the Cooley–Tukey algorithm hardly ever led to particularly favourable trade-offs, thus creating the impression that there was little to gain by switching to more exotic algorithms.

The advent of new machine architectures with vector and/or parallel processing features has greatly altered this picture (Pease, 1968[link]; Korn & Lambiotte, 1979[link]; Fornberg, 1981[link]; Swartzrauber, 1984[link]):

  • (i) pipelining equalizes the cost of f.p. addition and f.p. multiplication, and the ideal `blend' of the two types of operations depends solely on the number of adder and multiplier units available in each machine;

  • (ii) integer address arithmetic is delegated to specialized arithmetic and logical units (ALUs) operating concurrently with the f.p. units, so that complex reindexing schemes may be used without loss of overall efficiency.

Another major consideration is that of data flow [see e.g. Nawab & McClellan (1979)[link]]. Serial machines only have few registers and few paths connecting them, and allow little or no overlap between computation and data movement. New architectures, on the other hand, comprise banks of vector registers (or `cache memory') besides the usual internal registers, and dedicated ALUs can service data transfers between several of them simultaneously and concurrently with computation.

In this new context, the devices described in Sections 1.3.3.2[link] and 1.3.3.3[link] for altering the balance between the various types of arithmetic operations, and reshaping the data flow during the computation, are invaluable. The field of machine-dependent DFT algorithm design is thriving on them [see e.g. Temperton (1983a[link],b[link],c[link], 1985[link]); Agarwal & Cooley (1986[link], 1987[link])].

1.3.3.3.3.3. The Johnson–Burrus family of algorithms

| top | pdf |

In order to explore systematically all possible algorithms for carrying out a given DFT computation, and to pick the one best suited to a given machine, attempts have been made to develop:

  • (i) a high-level notation of describing all the ingredients of a DFT computation, including data permutation and data flow;

  • (ii) a formal calculus capable of operating on these descriptions so as to represent all possible reorganizations of the computation;

  • (iii) an automatic procedure for evaluating the performance of a given algorithm on a specific architecture.

Task (i)[link] can be accomplished by systematic use of a tensor product notation to represent the various stages into which the DFT can be factored (reindexing, small transforms on subsets of indices, twiddle factors, digit-reversal permutations).

Task (ii)[link] may for instance use the Winograd CBA normal form for each small transform, then apply the rules governing the rearrangement of tensor product [\bigotimes] and ordinary product × operations on matrices. The matching of these rearrangements to the architecture of a vector and/or parallel computer can be formalized algebraically [see e.g. Chapter 2 of Tolimieri et al. (1989)[link]].

Task (iii)[link] is a complex search which requires techniques such as dynamic programming (Bellman, 1958[link]).

Johnson & Burrus (1983)[link] have proposed and tested such a scheme to identify the optimal trade-offs between prime factor nesting and Winograd nesting of small Winograd transforms. In step (ii)[link], they further decomposed the pre-addition matrix A and post-addition matrix C into several factors, so that the number of design options available becomes very large: the N-point DFT when N has four factors can be calculated in over 1012 distinct ways.

This large family of nested algorithms contains the prime factor algorithm and the Winograd algorithms as particular cases, but usually achieves greater efficiency than either by reducing the f.p. multiplication count while keeping the number of f.p. additions small.

There is little doubt that this systematic approach will be extended so as to incorporate all available methods of restructuring the DFT.

References

Agarwal, R. C. & Cooley, J. W. (1986). Fourier transform and convolution subroutines for the IBM 3090 Vector facility. IBM J. Res. Dev. 30, 145–162.
Agarwal, R. C. & Cooley, J. W. (1987). Vectorized mixed radix discrete Fourier transform algorithms. Proc. IEEE, 75, 1283–1292.
Auslander, L., Feig, E. & Winograd, S. (1983). New algorithms for the multidimensional discrete Fourier transform. IEEE Trans. Acoust. Speech Signal Process. 31, 388–403.
Auslander, L., Tolimieri, R. & Winograd, S. (1982). Hecke's theorem in quadratic reciprocity, finite nilpotent groups and the Cooley–Tukey algorithm. Adv. Math. 43, 122–172.
Bellman, R. (1958). Dynamic programming and stochastic control processes. Inf. Control, 1, 228–239.
Burrus, C. S. & Eschenbacher, P. W. (1981). An in-place, in-order prime factor FFT algorithm. IEEE Trans. Acoust. Speech Signal Process. 29, 806–817.
Fornberg, A. (1981). A vector implementation of the fast Fourier transform algorithm. Math. Comput. 36, 189–191.
Guessoum, A. & Mersereau, R. M. (1986). Fast algorithms for the multidimensional discrete Fourier transform. IEEE Trans. Acoust. Speech Signal Process. 34, 937–943.
Harris, D. B., McClellan, J. H., Chan, D. S. K. & Schuessler, H. W. (1977). Vector radix fast Fourier transform. Rec. 1977 IEEE Internat. Conf. Acoust. Speech Signal Process. pp. 548–551.
Johnson, H. W. & Burrus, C. S. (1983). The design of optimal DFT algorithms using dynamic programming. IEEE Trans. Acoust. Speech Signal Process. 31, 378–387.
Kolba, D. P. & Parks, T. W. (1977). A prime factor FFT algorithm using high-speed convolution. IEEE Trans. Acoust. Speech Signal Process. 25, 281–294.
Korn, D. G. & Lambiotte, J. J. Jr (1979). Computing the fast Fourier transform on a vector computer. Math. Comput. 33, 977–992.
Mersereau, R. & Speake, T. C. (1981). A unified treatment of Cooley–Tukey algorithms for the evaluation of the multidimensional DFT. IEEE Trans. Acoust. Speech Signal Process. 29, 1011–1018.
Mersereau, R. M. (1979). The processing of hexagonally sampled two-dimensional signals. Proc. IEEE, 67, 930–949.
Morris, R. L. (1978). A comparative study of time efficient FFT and WFTA programs for general purpose computers. IEEE Trans. Acoust. Speech Signal Process. 26, 141–150.
Nawab, H. & McClellan, J. H. (1979). Bounds on the minimum number of data transfers in WFTA and FFT programs. IEEE Trans. Acoust. Speech Signal Process. 27, 393–398.
Nussbaumer, H. J. & Quandalle, P. (1979). Fast computation of discrete Fourier transforms using polynomial transforms. IEEE Trans. Acoust. Speech Signal Process. 27, 169–181.
Pease, M. C. (1968). An adaptation of the fast Fourier transform for parallel processing. J. Assoc. Comput. Mach. 15, 252–264.
Rivard, G. E. (1977). Direct fast Fourier transform of bivariate functions. IEEE Trans. Acoust. Speech Signal Process. 25, 250–252.
Silverman, H. F. (1977). An introduction to programming the Winograd Fourier transform algorithm (WFTA). IEEE Trans. Acoust. Speech Signal Process. 25, 152–165.
Swartzrauber, P. N. (1984). FFT algorithms for vector computers. Parallel Comput. 1, 45–63.
Temperton, C. (1983a). Self-sorting mixed-radix fast Fourier transforms. J. Comput. Phys. 52, 1–23.
Temperton, C. (1983b). A note on the prime factor FFT algorithm. J. Comput. Phys. 52, 198–204.
Temperton, C. (1983c). Fast mixed-radix real Fourier transforms. J. Comput. Phys. 52, 340–350.
Temperton, C. (1985). Implementation of a self-sorting in place prime factor FFT algorithm. J. Comput. Phys. 58, 283–299.
Tolimieri, R., An, M. & Lu, C. (1989). Algorithms for Discrete Fourier Transform and Convolution. New York: Springer-Verlag.
Uhrich, M. L. (1969). Fast Fourier transforms without sorting. IEEE Trans. AU, 17, 170–172.








































to end of page
to top of page