10.3 고속 푸리에 변환

10.1절의 후반부에서 이산 푸리에 변환을 행과 열 단위로 따로 계산하여 속도를 향상시키는 방법에 대하여 살펴보았다. 그러나 이러한 방법도 실제 프로그램에서 사용하기에는 적합하지 않을 정도의 느린 연산 속도를 보여준다. 이 절에서는 이산 푸리에 변환을 획기적으로 빠르게 계산하는 고속 푸리에 변환^{Fast Fourier Transform} 방법에 대하여 설명한다.