About: Prime-factor FFT algorithm     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:Event100029378, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FPrime-factor_FFT_algorithm

The prime-factor algorithm (PFA), also called the Good–Thomas algorithm (1958/1963), is a fast Fourier transform (FFT) algorithm that re-expresses the discrete Fourier transform (DFT) of a size N = N1N2 as a two-dimensional N1×N2 DFT, but only for the case where N1 and N2 are relatively prime. These smaller transforms of size N1 and N2 can then be evaluated by applying PFA recursively or by using some other FFT algorithm.

AttributesValues
rdf:type
rdfs:label
  • Prime-factor FFT algorithm
  • 互質因子算法
rdfs:comment
  • The prime-factor algorithm (PFA), also called the Good–Thomas algorithm (1958/1963), is a fast Fourier transform (FFT) algorithm that re-expresses the discrete Fourier transform (DFT) of a size N = N1N2 as a two-dimensional N1×N2 DFT, but only for the case where N1 and N2 are relatively prime. These smaller transforms of size N1 and N2 can then be evaluated by applying PFA recursively or by using some other FFT algorithm.
  • 互質因子算法(Prime-factor FFT algorithm, PFA),又稱為Good-Thomas算法,是一種快速傅立葉變換(FFT),把N = N1N2大小的離散傅立葉變換重新表示為N1 * N2大小的二維離散傅立葉變換,其中N1與N2需互質。變成N1和N2大小的傅立葉變換後,可以繼續遞迴使用PFA,或用其他快速傅立葉變換算法來計算。 較流行的Cooley-Tukey算法經由mixed-radix一般化後,也是把N = N1N2大小的離散傅立葉變換分割為N1和N2大小的轉換,但和互質因子算法 (PFA)作法並不相同,不應混淆。Cooley-Tukey算法的N1與N2不需互質,可以是任何整數。然而有個缺點是比PFA多出一些乘法,和單位根twiddle factors相乘。相對的,PFA的缺點則是N1與N2需互質 (例如N 是2次方就不適用),而且要藉由中國剩餘定理來進行較複雜的re-indexing。互質因子算法 (PFA)可以和mixed-radix Cooley-Tukey算法相結合,前者將N 分解為互質的因數,後者則用在重複質因數上。 PFA也與nested Winograd FFT算法密切相關,後者使用更為精巧的二維摺積技巧分解成N1 * N2的轉換。因而一些較古老的論文把Winograd算法稱為PFA FFT。
foaf:isPrimaryTopicOf
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
sameAs
dbp:wikiPageUsesTemplate
has abstract
  • The prime-factor algorithm (PFA), also called the Good–Thomas algorithm (1958/1963), is a fast Fourier transform (FFT) algorithm that re-expresses the discrete Fourier transform (DFT) of a size N = N1N2 as a two-dimensional N1×N2 DFT, but only for the case where N1 and N2 are relatively prime. These smaller transforms of size N1 and N2 can then be evaluated by applying PFA recursively or by using some other FFT algorithm. PFA should not be confused with the mixed-radix generalization of the popular Cooley–Tukey algorithm, which also subdivides a DFT of size N = N1N2 into smaller transforms of size N1 and N2. The latter algorithm can use any factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called twiddle factors, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for power-of-two sizes) and that it requires a more complicated re-indexing of the data based on the Chinese remainder theorem (CRT). Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing N into relatively prime components and the latter handling repeated factors. PFA is also closely related to the nested , where the latter performs the decomposed N1 by N2 transform via more sophisticated two-dimensional convolution techniques. Some older papers therefore also call Winograd's algorithm a PFA FFT. (Although the PFA is distinct from the Cooley–Tukey algorithm, Good's 1958 work on the PFA was cited as inspiration by Cooley and Tukey in their 1965 paper, and there was initially some confusion about whether the two algorithms were different. In fact, it was the only prior FFT work cited by them, as they were not then aware of the earlier research by Gauss and others.)
  • 互質因子算法(Prime-factor FFT algorithm, PFA),又稱為Good-Thomas算法,是一種快速傅立葉變換(FFT),把N = N1N2大小的離散傅立葉變換重新表示為N1 * N2大小的二維離散傅立葉變換,其中N1與N2需互質。變成N1和N2大小的傅立葉變換後,可以繼續遞迴使用PFA,或用其他快速傅立葉變換算法來計算。 較流行的Cooley-Tukey算法經由mixed-radix一般化後,也是把N = N1N2大小的離散傅立葉變換分割為N1和N2大小的轉換,但和互質因子算法 (PFA)作法並不相同,不應混淆。Cooley-Tukey算法的N1與N2不需互質,可以是任何整數。然而有個缺點是比PFA多出一些乘法,和單位根twiddle factors相乘。相對的,PFA的缺點則是N1與N2需互質 (例如N 是2次方就不適用),而且要藉由中國剩餘定理來進行較複雜的re-indexing。互質因子算法 (PFA)可以和mixed-radix Cooley-Tukey算法相結合,前者將N 分解為互質的因數,後者則用在重複質因數上。 PFA也與nested Winograd FFT算法密切相關,後者使用更為精巧的二維摺積技巧分解成N1 * N2的轉換。因而一些較古老的論文把Winograd算法稱為PFA FFT。 儘管PFA和Cooley-Tukey算法並不相同,但有趣的是Cooley和Tukey在他們1965年發表的有名的論文中,沒有發覺到高斯和其他人更早的研究,只引用Good在1958年發表的PFA作為前人的FFT結果。剛開始的時候人們對這兩種作法是否不同有點困惑。
prov:wasDerivedFrom
page length (characters) of wiki page
is foaf:primaryTopic of
is Link from a Wikipage to another Wikipage of
is Wikipage redirect of
is Wikipage disambiguates of
Faceted Search & Find service v1.17_git51 as of Sep 16 2020


Alternative Linked Data Documents: PivotViewer | iSPARQL | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3321 as of Jun 2 2021, on Linux (x86_64-generic-linux-glibc25), Single-Server Edition (61 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2021 OpenLink Software