| Revision as of 09:39, 22 November 2024 edit Kkuhts (talk | contribs)34 edits ←Created page with '소인수 알고리즘(Prime-Factor Algorithm, PFA) Prime-factor FFT 알고리즘(PFA)은 Good-Thomas 알고리즘으로도 알려져 있으며, N = N 1 N 2 크기의 이산 푸리에 변환을 N 1 * N 2 크기의 2차원 이산 푸리에 변환으로 다시 표현하는 고속 푸리에 변환(FFT)입니다. 여기서 N 1과 N 2는 서로소입니다. N 1과 N 2 크기의 푸리에 변환으로 변환되면 PFA를 재귀적으로 사용하거나 다...'Tag: large unwikified new articleNext edit → |
| (No difference) |
Revision as of 09:39, 22 November 2024
소인수 알고리즘(Prime-Factor Algorithm, PFA)
Prime-factor FFT 알고리즘(PFA)은 Good-Thomas 알고리즘으로도 알려져 있으며, N = N 1 N 2 크기의 이산 푸리에 변환을 N 1 * N 2 크기의 2차원 이산 푸리에 변환으로 다시 표현하는 고속 푸리에 변환(FFT)입니다. 여기서 N 1과 N 2는 서로소입니다. N 1과 N 2 크기의 푸리에 변환으로 변환되면 PFA를 재귀적으로 사용하거나 다른 고속 푸리에 변환 알고리즘을 사용하여 계산할 수 있습니다.
혼합 근으로 일반화된 후 더 인기 있는 Cooley-Tukey 알고리즘도 N = N 1 N 2 크기의 이산 푸리에 변환을 N 1과 N 2 변환으로 분할하지만 서로소 인수 분해 알고리즘(PFA)과 다르므로 혼동해서는 안 됩니다. Cooley-Tukey 알고리즘의 N 1과 N 2는 서로소일 필요가 없으며 어떤 정수라도 될 수 있습니다. 그러나 한 가지 단점은 PFA보다 곱셈이 많고 단위근이 있는 곱셈은 인수를 꼬아 버립니다. 반면에 PFA의 단점은 N 1과 N 2가 서로소여야 한다는 것입니다(예를 들어, N이 2의 거듭제곱일 때는 적용할 수 없음). 그리고 중국 나머지 정리를 사용하여 더 복잡한 재색인을 수행해야 합니다. 서로소 인수분해 알고리즘(PFA)은 혼합 근 Cooley-Tukey 알고리즘과 결합할 수 있으며, 전자는 N을 서로소 인수로 분해하고 후자는 반복된 소인수에 사용됩니다.
PFA는 또한 N 1 * N 2 변환으로 분해하기 위해 보다 정교한 2차원 합성곱 기술을 사용하는 중첩 Winograd FFT 알고리즘과 밀접한 관련이 있습니다. 따라서 일부 오래된 논문에서는 Winograd 알고리즘을 PFA FFT라고 합니다.
PFA와 Cooley-Tukey 알고리즘은 동일하지 않지만, Cooley와 Tukey가 유명한 1965년 논문에서 Gauss와 다른 사람들의 초기 작업을 인식하지 못하고 Good의 1958년 PFA만 이전 FFT 결과로 인용한 것은 흥미롭습니다. 처음에는 사람들이 이 두 가지 접근 방식이 다른지 약간 혼란스러워했습니다.