Namespaces
Variants
Actions

Difference between revisions of "Winograd Fourier transform algorithm"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (moved MSC above TEXdone)
 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
''WFT algorithm''
 
''WFT algorithm''
  
An algorithm exploiting multiplicative structure on the data indexing set to transform a [[Fourier transform|Fourier transform]] computation into a cyclic convolution computation [[#References|[a1]]], [[#References|[a4]]], [[#References|[a5]]]. Divide-and-conquer fast Fourier transform algorithms, such as the Cooley–Tukey fast Fourier transform algorithms [[#References|[a6]]], 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.
+
{{MSC|65T50}}
 +
{{TEX|done}}
  
C. Rader [[#References|[a2]]] observed that a Fourier transform computation of prime size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110090/w1100901.png" /> could be computed by a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110090/w1100902.png" />-point cyclic convolution. S. Winograd [[#References|[a4]]] extended Rader's result to Fourier transform computations of prime power size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110090/w1100903.png" /> and introduced cyclic convolution algorithms based on the polynomial version of the [[Chinese remainder theorem|Chinese remainder theorem]] to compute the resulting cyclic convolutions (cf. [[Winograd small convolution algorithm|Winograd small convolution algorithm]]). The overall strategy is usually called the Winograd fast Fourier transform algorithm, or Winograd FFT algorithm. Rader computed the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110090/w1100904.png" />-point cyclic convolution by calling on the convolution theorem to turn the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110090/w1100905.png" />-point convolution into several <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110090/w1100906.png" />-point Fourier transform computations.
+
An algorithm exploiting multiplicative structure on the data indexing set to transform a [[Fourier transform|Fourier transform]] computation into a cyclic convolution computation {{Cite|BoMu}}, {{Cite|Wi}}, {{Cite|Wi2}}. Divide-and-conquer fast Fourier transform algorithms, such as the Cooley–Tukey fast Fourier transform algorithms {{Cite|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.
  
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 [[#References|[a2]]]. An alternative approach has been suggested in [[#References|[a3]]], 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.
+
C. Rader {{Cite|ToAn}} observed that a Fourier transform computation of prime size $p$ could be computed by a $(p-1)$-point cyclic convolution. S. Winograd {{Cite|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|Chinese remainder theorem]] to compute the resulting cyclic convolutions (cf. [[Winograd small convolution algorithm|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 {{Cite|ToAn}}. An alternative approach has been suggested in {{Cite|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 {{Cite|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.
  
In [[#References|[a2]]], 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====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> A. Borodin,  I. Munro,  "Computational complexity and algebraic and numeric problems" , Amer. Elsevier  (1975)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> R. TolimieriM. An,  C. Lu,  "Algorithms for discrete Fourier transform and convolution" , Springer (1989)  pp. 197</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> 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</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> S. Winograd,  "On computing the discrete Fourier transform" ''Math. Comp.'' , '''32''' (1978)  pp. 175–199</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> S. Winograd,  "On the multiplicative complexity of the discrete Fourier transform"  ''Adv. Math.'' , '''32'''  (1979)  pp. 83–117</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top"> J.W. Cooley,  J.W. Tukey,  "An algorithm for the machine calculation of complex Fourier series"  ''Math. Comp.'' , '''19'''  (1965)  pp. 297–301</TD></TR></table>
+
{|
 +
|-
 +
|valign="top"|{{Ref|BoMu}}||valign="top"| A. Borodin,  I. Munro,  "Computational complexity and algebraic and numeric problems", Amer. Elsevier  (1975)
 +
|-
 +
|valign="top"|{{Ref|CoTu}}||valign="top"| J.W. CooleyJ.W. Tukey,  "An algorithm for the machine calculation of complex Fourier series" ''Math. Comp.'', '''19''' (1965)  pp. 297–301
 +
|-
 +
|valign="top"|{{Ref|KoPa}}||valign="top"| 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
 +
|-
 +
|valign="top"|{{Ref|ToAn}}||valign="top"| R. Tolimieri,  M. An,  C. Lu,  "Algorithms for discrete Fourier transform and convolution", Springer (1989)  pp. 197
 +
|-
 +
|valign="top"|{{Ref|Wi}}||valign="top"| S. Winograd,  "On computing the discrete Fourier transform"  ''Math. Comp.'', '''32'''  (1978)  pp. 175–199
 +
|-
 +
|valign="top"|{{Ref|Wi2}}||valign="top"| S. Winograd,  "On the multiplicative complexity of the discrete Fourier transform"  ''Adv. Math.'', '''32'''  (1979)  pp. 83–117
 +
|-
 +
|}

Latest revision as of 00:23, 26 April 2012

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.

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
How to Cite This Entry:
Winograd Fourier transform algorithm. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Winograd_Fourier_transform_algorithm&oldid=15268
This article was adapted from an original article by R. Tolimieri (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article