##### Actions

WFT algorithm

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