Bruun's FFT algorithm: Difference between revisions

Revision as of 20:44, 1 May 2009

Revision as of 23:08, 11 January 2010

Line 1:

'''Bruun's algorithm''' is a [[fast Fourier transform]] (FFT) algorithm based on an unusual recursive [[polynomial]]-factorization approach, proposed for powers of two by G. Bruun in 1978 and generalized to arbitrary even composite sizes by H. Murakami in 1996. Because its operations involve only real coefficients until the last computation stage, it was initially proposed as a way to efficiently compute the [[discrete Fourier transform]] (DFT) of real data. Bruun's algorithm has not seen widespread use, however, as approaches based on the ordinary [[Cooley-TukeyCooley–Tukey FFT algorithm]] have been successfully adapted to real data with at least as much efficiency. Furthermore, there is evidence that Bruun's algorithm may be intrinsically less accurate than Cooley-TukeyCooley–Tukey in the face of finite numerical precision (Storn, 1993).

Nevertheless, Bruun's algorithm illustrates an alternative algorithmic framework that can express both itself and the Cooley-Tukey algorithm, and thus provides an interesting perspective on FFTs that permits mixtures of the two algorithms and other generalizations.

Nevertheless, Bruun's algorithm illustrates an alternative algorithmic framework that can express both itself and the Cooley-TukeyCooley–Tukey algorithm, and thus provides an interesting perspective on FFTs that permits mixtures of the two algorithms and other generalizations.

== A polynomial approach to the DFT ==

Line 13 ⟶ 11:

k = 0,\dots,N-1. </math>

For convenience, let us denote the ''N'' [[root of unity|roots of unity]] by ω_''N''^''n'' (''n''&nbsp;=&nbsp;0&nbsp;..&nbsp;''N''-&nbsp;&minus;&nbsp;1):

:<math>\omega_N^n = e^{-\frac{2\pi i}{N} n }</math>

Line 25 ⟶ 23:

:<math>X_k = x(\omega_N^k) = x(z) \mod (z - \omega_N^k)</math>

where '''mod''' ([[modulo]]) denotes the [[Polynomial remainder theorem|polynomial remainder]] operation. The key to fast algorithms like Bruun's or Cooley-TukeyCooley–Tukey comes from the fact that one can perform this set of ''N'' remainder operations in recursive stages.

== Recursive factorizations and FFTs ==

Line 39 ⟶ 37:

Moreover, as long as the polynomial factors at each stage are [[relatively prime]] (which for polynomials means that they have no common roots), one can construct a dual algorithm by reversing the process with the [[Chinese Remainder Theorem]].

====Cooley-TukeyCooley–Tukey as polynomial factorization====

The standard decimation-in-frequency (DIF) radix-''r'' Cooley-TukeyCooley–Tukey algorithm corresponds closely to a recursive factorization. For example, radix-2 DIF Cooley-TukeyCooley–Tukey factors <math>z^N-1</math> into <math>F_1 = (z^{N/2}-1)</math> and <math>F_2 = (z^{N/2}+1)</math>. These modulo operations reduce the degree of <math>x(z)</math> by 2, which corresponds to dividing the problem size by 2. Instead of recursively factorizing <math>F_2</math> directly, though, Cooley-TukeyCooley–Tukey instead first computes ''x''₂(''z'' ω_''N''), shifting all the roots (by a ''twiddle factor'') so that it can apply the recursive factorization of <math>F_1</math> to both subproblems. That is, Cooley-TukeyCooley–Tukey ensures that all subproblems are also DFTs, whereas this is not generally true for an arbitrary recursive factorization (such as Bruun's, below).

== The Bruun factorization ==