Tables for
Volume B
Reciprocal space
Edited by U. Shmueli

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

Section The method of successive one-dimensional transforms

G. Bricognea

aMRC Laboratory of Molecular Biology, Hills Road, Cambridge CB2 2QH, England, and LURE, Bâtiment 209D, Université Paris-Sud, 91405 Orsay, France The method of successive one-dimensional transforms

| top | pdf |

The DFT was defined in Section[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[link]), and in signal processing as the `row–column method'.

to end of page
to top of page