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

© International Union of Crystallography 2006
International Tables for Crystallography (2006). Vol. B. ch. 1.3, pp. 57-58   | 1 | 2 |

Section 1.3.3.3.3.1. From local pieces to global algorithms

G. Bricognea

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.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.








































to end of page
to top of page