Draft:소인수 알고리즘(Prime-Factor Algorithm, PFA)
 | This is a draft article. It is a work in progress open to editing by anyone. Please ensure core content policies are met before publishing it as a live Wikipedia article. Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL Last edited by BoyTheKingCanDance (talk | contribs) 66 minutes ago. (Update)
Finished drafting? or |
소인수 알고리즘(Prime-Factor Algorithm, PFA)
Prime-factor FFT 알고리즘(PFA)은 Good-Thomas 알고리즘[1][2]으로도 알려져 있으며, N = N1 N2 크기의 이산 푸리에 변환을 N = N1x N2 크기의 2차원 이산 푸리에 변환으로 다시 표현하는 고속 푸리에 변환(FFT)입니다. 여기서 N1과 N2는 서로소입니다. N1과 N2 크기의 푸리에 변환으로 변환되면 PFA를 재귀적으로 사용하거나 다른 고속 푸리에 변환 알고리즘을 사용하여 계산할 수 있습니다.
혼합 근으로 일반화된 후 더 인기 있는 Cooley-Tukey 알고리즘도 N = N1 N2 크기의 이산 푸리에 변환을 N1과 N2 변환으로 분할하지만 서로소 인수 분해 알고리즘(PFA)과 다르므로 혼동해서는 안 됩니다. Cooley-Tukey 알고리즘의 N1과 N2는 서로소일 필요가 없으며 어떤 정수라도 될 수 있습니다. 그러나 한 가지 단점은 PFA보다 곱셈이 많고 단위근이 있는 곱셈은 인수를 꼬아 버립니다. 반면에 PFA의 단점은 N1과 N2가 서로소여야 한다는 것입니다(예를 들어, N이 2의 거듭제곱일 때는 적용할 수 없음). 그리고 중국 나머지 정리를 사용하여 더 복잡한 재색인을 수행해야 합니다. 서로소 인수분해 알고리즘(PFA)은 혼합 근 Cooley-Tukey 알고리즘과 결합할 수 있으며, 전자는 N을 서로소 인수로 분해하고 후자는 반복된 소인수에 사용됩니다.
PFA는 또한 N1 * N2 변환으로 분해하기 위해 보다 정교한 2차원 합성곱 기술을 사용하는 중첩 Winograd FFT 알고리즘과 밀접한 관련이 있습니다. 따라서 일부 오래된 논문에서는 Winograd 알고리즘을 PFA FFT라고 합니다.
PFA와 Cooley-Tukey 알고리즘은 동일하지 않지만, Cooley와 Tukey가 유명한 1965년 논문에서 Gauss와 다른 사람들의 초기 작업을 인식하지 못하고 Good의 1958년 PFA만 이전 FFT 결과로 인용한 것은 흥미롭습니다. 처음에는 사람들이 이 두 가지 접근 방식이 다른지 약간 혼란스러워했습니다.