FFT 알고리즘 이해하기 (2013)

Discrete Fourier Transform(DFT) 를 빠르게 계산하는 FFT의 핵심 아이디어를 정리한다. DFT는 순진하게 계산하면 O(N^2) 이지만, FFT는 이를 O(N log N) 으로 줄인다.

먼저 DFT를 행렬-벡터 곱으로 표현하고, numpy.fft.fft와 비교해 느린 Python 구현 DFT_slow를 만든다. 이 구현은 정확하지만 1024개 입력 기준으로 훨씬 느리며, 대략 1000배 이상 차이가 난다.

핵심은 DFT의 주기적 대칭성이다. 저자는 X_{N+k} = X_k 성질을 보여 주고, 이를 바탕으로 입력을 짝수 인덱스와 홀수 인덱스로 나눠 더 작은 DFT 두 개로 재귀적으로 분해한다. 이 과정이 Cooley-Tukey FFT의 본질이며, 문제가 충분히 작아질 때까지 계속 반으로 쪼개면 전체 복잡도가 O(N log N) 이 된다.

구현은 두 단계로 제시된다.

• FFT: 재귀적으로 분할 정복을 수행하는 순수 Python + NumPy 버전
• FFT_vectorized: 재귀 호출을 줄이고, 여러 하위 문제를 한꺼번에 계산하는 벡터화 버전

벡터화 버전은 재귀 버전보다 다시 한 단계 빠르며, 1024×16 크기 입력에서 numpy.fft.fft와 비교해도 꽤 근접한 성능을 보인다. 다만 여전히 FFTPACK 기반 구현에는 못 미치는데, 이는 Python 재귀, 임시 배열 생성, 메모리 복사 비용 때문이라고 설명한다.

마지막으로 FFTPACK이 더 빠른 이유를 정리한다.

• 중간 계산 재사용을 극대화함
• Fortran 같은 저수준 언어로 메모리 사용을 더 정밀하게 제어함
• radix-2뿐 아니라 다른 분할 방식도 활용함
• Bluestein, Rader 같은 대체 FFT 계열 알고리즘도 존재함

결국 이 글의 목적은 실무에서 FFT를 블랙박스로 쓰는 데서 멈추지 않고, 왜 빠른지, 어떤 대칭성을 이용하는지, 어떻게 Python으로 직접 구현되는지에 대한 직관을 주는 데 있다.