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–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–Tukey in the face of finite numerical precision (Storn, 1993).
Contents
- A polynomial approach to the DFT
- Recursive factorizations and FFTs
- CooleyTukey as polynomial factorization
- The Bruun factorization
- Generalization to arbitrary radices
- References
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.
A polynomial approach to the DFT
Recall that the DFT is defined by the formula:
For convenience, let us denote the N roots of unity by ωNn (n = 0, ..., N − 1):
and define the polynomial x(z) whose coefficients are xn:
The DFT can then be understood as a reduction of this polynomial; that is, Xk is given by:
where mod denotes the polynomial remainder operation. The key to fast algorithms like Bruun's or Cooley–Tukey comes from the fact that one can perform this set of N remainder operations in recursive stages.
Recursive factorizations and FFTs
In order to compute the DFT, we need to evaluate the remainder of
The product of all of the monomials
More explicitly, suppose for example that
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–Tukey as polynomial factorization
The standard decimation-in-frequency (DIF) radix-r Cooley–Tukey algorithm corresponds closely to a recursive factorization. For example, radix-2 DIF Cooley–Tukey factors
The Bruun factorization
The basic Bruun algorithm for powers of two N=2n factorizes z2n-1 recursively via the rules:
where a is a real constant with |a| ≤ 2. If
At stage s, s=0,1,2,n-1, the intermediate state consists of 2s polynomials
By the construction of the factorization of z2n-1, the polynomials ps,m(z) each encode 2n-s values
of the Fourier transform, for m=0, the covered indices are k=0, 2k, 2∙2s, 3∙2s,…, (2n-s-1)∙2s, for m>0 the covered indices are k=m, 2s+1-m, 2s+1+m, 2∙2s+1-m, 2∙2s+1+m, …, 2n-m.
During the transition to the next stage, the polynomial
At the end of the recursion, for s=n-1, there remain 2n-1 linear polynomials encoding two Fourier coefficients X0 and X2n-1 for the first and for the any other kth polynomial the coefficients Xk and X2n-k.
At each recursive stage, all of the polynomials of the common degree 4M-1 are reduced to two parts of half the degree 2M-1. The divisor of this polynomial remainder computation is a quadratic polynomial zm, so that all reductions can be reduced to polynomial divisions of cubic by quadratic polynomials. There are N/2=2n-1 of these small divisions at each stage, leading to an O (N log N) algorithm for the FFT.
Moreover, since all of these polynomials have purely real coefficients (until the very last stage), they automatically exploit the special case where the inputs xn are purely real to save roughly a factor of two in computation and storage. One can also take straightforward advantage of the case of real-symmetric data for computing the discrete cosine transform (Chen and Sorensen, 1992).
Generalization to arbitrary radices
The Bruun factorization, and thus the Bruun FFT algorithm, was generalized to handle arbitrary even composite lengths, i.e. dividing the polynomial degree by an arbitrary radix (factor), as follows. First, we define a set of polynomials φN,α(z) for positive integers N and for α in [0,1) by:
Note that all of the polynomials that appear in the Bruun factorization above can be written in this form. The zeroes of these polynomials are