Prime-factor FFT algorithm (original) (raw)

About DBpedia

Алгоритм Гуда — Томаса — алгоритм вычисления быстрого преобразования Фурье, применяющийся к последовательностям, длина которых равна произведению двух взаимно простых чисел. Алгоритм Гуда — Томаса не следует путать с алгоритмом Кули — Тьюки, где делители длины преобразования не обязаны быть взаимно простыми. Алгоритм Гуда — Томаса ограничен этим условием, а также задействует более сложную схему переиндексации, чем алгоритм Кули — Тьюки, но при этом не требует промежуточного умножения на комплексные множители и потому несколько проще с точки зрения вычислений.

Property Value
dbo: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 more complicated re-indexing of the data based on the additive group isomorphisms. 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.) (en) Алгоритм Гуда — Томаса — алгоритм вычисления быстрого преобразования Фурье, применяющийся к последовательностям, длина которых равна произведению двух взаимно простых чисел. Алгоритм Гуда — Томаса не следует путать с алгоритмом Кули — Тьюки, где делители длины преобразования не обязаны быть взаимно простыми. Алгоритм Гуда — Томаса ограничен этим условием, а также задействует более сложную схему переиндексации, чем алгоритм Кули — Тьюки, но при этом не требует промежуточного умножения на комплексные множители и потому несколько проще с точки зрения вычислений. (ru) 互質因子算法（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結果。剛開始的時候人們對這兩種作法是否不同有點困惑。 (zh)
dbo:wikiPageExternalLink http://infoscience.epfl.ch/record/59946
dbo:wikiPageID 241490 (xsd:integer)
dbo:wikiPageLength 9583 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1117514792 (xsd:integer)
dbo:wikiPageWikiLink dbr:Power_of_two dbr:Principal_root_of_unity dbr:Algebra_homomorphism dbr:Cooley–Tukey_FFT_algorithm dbr:Automorphism dbr:Additive_group dbr:Central_idempotent dbr:Cyclic_group dbr:Euler's_totient_function dbr:Bluestein's_FFT_algorithm dbr:Fast_Fourier_transform dbr:Rader's_FFT_algorithm dbr:Recursion dbr:Tensor_product dbr:Chinese_remainder_theorem dbc:FFT_algorithms dbr:Tensor_product_of_algebras dbr:Discrete_Fourier_transform dbr:Group_isomorphism dbr:I._J._Good dbr:Twiddle_factor dbr:Relatively_prime dbr:Winograd_FFT_algorithm
dbp:wikiPageUsesTemplate dbt:Cite_book dbt:Cite_journal dbt:Reflist dbt:Short_description dbt:Use_American_English dbt:JSTOR
dcterms:subject dbc:FFT_algorithms
rdf:type yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatFFTAlgorithms
rdfs:comment Алгоритм Гуда — Томаса — алгоритм вычисления быстрого преобразования Фурье, применяющийся к последовательностям, длина которых равна произведению двух взаимно простых чисел. Алгоритм Гуда — Томаса не следует путать с алгоритмом Кули — Тьюки, где делители длины преобразования не обязаны быть взаимно простыми. Алгоритм Гуда — Томаса ограничен этим условием, а также задействует более сложную схему переиндексации, чем алгоритм Кули — Тьюки, но при этом не требует промежуточного умножения на комплексные множители и потому несколько проще с точки зрения вычислений. (ru) 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. (en) 互質因子算法（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。 (zh)
rdfs:label Prime-factor FFT algorithm (en) Алгоритм Гуда — Томаса (ru) 互質因子算法 (zh)
owl:sameAs freebase:Prime-factor FFT algorithm yago-res:Prime-factor FFT algorithm wikidata:Prime-factor FFT algorithm dbpedia-ru:Prime-factor FFT algorithm dbpedia-zh:Prime-factor FFT algorithm https://global.dbpedia.org/id/4tUzC
prov:wasDerivedFrom wikipedia-en:Prime-factor_FFT_algorithm?oldid=1117514792&ns=0
foaf:isPrimaryTopicOf wikipedia-en:Prime-factor_FFT_algorithm
is dbo:wikiPageDisambiguates of dbr:PFA
is dbo:wikiPageRedirects of dbr:Prime-factor_FFT_algorithm.
is dbo:wikiPageWikiLink of dbr:List_of_algorithms dbr:List_of_numerical_analysis_topics dbr:Cooley–Tukey_FFT_algorithm dbr:PFA dbr:FFTW dbr:Fast_Fourier_transform dbr:Chinese_remainder_theorem dbr:Discrete_Hartley_transform dbr:Twiddle_factor dbr:Prime-factor_FFT_algorithm.
is foaf:primaryTopic of wikipedia-en:Prime-factor_FFT_algorithm