Attributes  Values 

rdf:type
 
rdfs:label
  Primefactor FFT algorithm
 互質因子算法

rdfs:comment
  The primefactor algorithm (PFA), also called the Good–Thomas algorithm (1958/1963), is a fast Fourier transform (FFT) algorithm that reexpresses the discrete Fourier transform (DFT) of a size N = N1N2 as a twodimensional 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.
 互質因子算法（Primefactor FFT algorithm, PFA），又稱為GoodThomas算法，是一種快速傅立葉變換（FFT），把N = N1N2大小的離散傅立葉變換重新表示為N1 * N2大小的二維離散傅立葉變換，其中N1與N2需互質。變成N1和N2大小的傅立葉變換後，可以繼續遞迴使用PFA，或用其他快速傅立葉變換算法來計算。 較流行的CooleyTukey算法經由mixedradix一般化後，也是把N = N1N2大小的離散傅立葉變換分割為N1和N2大小的轉換，但和互質因子算法 (PFA)作法並不相同，不應混淆。CooleyTukey算法的N1與N2不需互質，可以是任何整數。然而有個缺點是比PFA多出一些乘法，和單位根twiddle factors相乘。相對的，PFA的缺點則是N1與N2需互質 (例如N 是2次方就不適用)，而且要藉由中國剩餘定理來進行較複雜的reindexing。互質因子算法 (PFA)可以和mixedradix CooleyTukey算法相結合，前者將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 primefactor algorithm (PFA), also called the Good–Thomas algorithm (1958/1963), is a fast Fourier transform (FFT) algorithm that reexpresses the discrete Fourier transform (DFT) of a size N = N1N2 as a twodimensional 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 mixedradix 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 poweroftwo sizes) and that it requires a more complicated reindexing of the data based on the Chinese remainder theorem (CRT). Note, however, that PFA can be combined with mixedradix 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 twodimensional 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.)
 互質因子算法（Primefactor FFT algorithm, PFA），又稱為GoodThomas算法，是一種快速傅立葉變換（FFT），把N = N1N2大小的離散傅立葉變換重新表示為N1 * N2大小的二維離散傅立葉變換，其中N1與N2需互質。變成N1和N2大小的傅立葉變換後，可以繼續遞迴使用PFA，或用其他快速傅立葉變換算法來計算。 較流行的CooleyTukey算法經由mixedradix一般化後，也是把N = N1N2大小的離散傅立葉變換分割為N1和N2大小的轉換，但和互質因子算法 (PFA)作法並不相同，不應混淆。CooleyTukey算法的N1與N2不需互質，可以是任何整數。然而有個缺點是比PFA多出一些乘法，和單位根twiddle factors相乘。相對的，PFA的缺點則是N1與N2需互質 (例如N 是2次方就不適用)，而且要藉由中國剩餘定理來進行較複雜的reindexing。互質因子算法 (PFA)可以和mixedradix CooleyTukey算法相結合，前者將N 分解為互質的因數，後者則用在重複質因數上。 PFA也與nested Winograd FFT算法密切相關，後者使用更為精巧的二維摺積技巧分解成N1 * N2的轉換。因而一些較古老的論文把Winograd算法稱為PFA FFT。 儘管PFA和CooleyTukey算法並不相同，但有趣的是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  