Winograd Fourier transform algorithm

WFT algorithm

2020 Mathematics Subject Classification: Primary: 65T50 [MSN][ZBL]

An algorithm exploiting multiplicative structure on the data indexing set to transform a Fourier transform computation into a cyclic convolution computation [BoMu], [Wi], [Wi2]. Divide-and-conquer fast Fourier transform algorithms, such as the Cooley–Tukey fast Fourier transform algorithms [CoTu], depend on the existence of non-trivial divisors of the transform size, which determine subgroups of the additive group structure of the indexing set and split the global computation into local computations. This divide-and-conquer strategy does not apply to prime size Fourier transform computations.

C. Rader [ToAn] observed that a Fourier transform computation of prime size $p$ could be computed by a $(p-1)$-point cyclic convolution. S. Winograd [Wi] extended Rader's result to Fourier transform computations of prime power size $p^N$ and introduced cyclic convolution algorithms based on the polynomial version of the Chinese remainder theorem to compute the resulting cyclic convolutions (cf. Winograd small convolution algorithm). The overall strategy is usually called the Winograd fast Fourier transform algorithm, or Winograd FFT algorithm. Rader computed the $(p-1)$-point cyclic convolution by calling on the convolution theorem to turn the $(p-1)$-point convolution into several $(p-1)$-point Fourier transform computations.

The Winograd FFT algorithm tends to reduce the number of multiplications at the price of increased additions. For large transform sizes a direct application of the Winograd FFT algorithm entails a prohibitively large number of additions, especially on modern RISC-architectures with multiply and accumulate facilities which mask multiplications inside additions. However, hybrid strategies can be effective when build on small-size Winograd core routines and when these cores are nested in the Good–Thomas prime-factor fast Fourier transform. The resulting strategy is usually called the Winograd large Fourier transform algorithm, or Winograd large FFT algorithm [ToAn]. An alternative approach has been suggested in [KoPa], using the Good–Thomas prime-factor fast Fourier transform to decompose the global computation into smaller Fourier transform computations, implemented by the Winograd small fast Fourier transform algorithm and reducing some of the additions at the cost of some multiplications.

In [ToAn], the Winograd class of fast Fourier transform algorithms was modeled in tensor product formalism, leading to algorithmic versions and programming strategies based on the use of macros and reduction rules.

References

[BoMu]	A. Borodin, I. Munro, "Computational complexity and algebraic and numeric problems", Amer. Elsevier (1975)
[CoTu]	J.W. Cooley, J.W. Tukey, "An algorithm for the machine calculation of complex Fourier series" Math. Comp., 19 (1965) pp. 297–301
[KoPa]	D.P. Kolba, T.W. Parks, "Prime factor FFT algorithm using high speed convolution" IEEE Trans. Acoustics, Speech and Signal Processing, ASSP–25 (1977) pp. 281–294
[ToAn]	R. Tolimieri, M. An, C. Lu, "Algorithms for discrete Fourier transform and convolution", Springer (1989) pp. 197
[Wi]	S. Winograd, "On computing the discrete Fourier transform" Math. Comp., 32 (1978) pp. 175–199
[Wi2]	S. Winograd, "On the multiplicative complexity of the discrete Fourier transform" Adv. Math., 32 (1979) pp. 83–117