FFT (Fast Fourier Transform) – 고속 푸리에 변환

FFT는 이산 데이터 값들의 푸리에 변환 계산을 위한 알고리즘이다. FFT는 주어진 유한 데이터 점들의 세트, 즉 예를 들어 실세계 신호로부터 주기적으로 얻어지는 견본들을, 그 요소 주파수들의 형태로 표현한다. 이것은 또한 정확하게 반대인 주파수 데이터로부터 신호를 재구성하는 문제도 해결한다. FFT는 수치해석의 가장 중요한 알고리즘이다. Gilbert Strang은 FFT를 가리켜, “우리 세대의 가장 중요한 알고리즘”이라고 말했다. FFT는 또한 두 개의 다항식을 곱하는데 있어 점근적으로 가장 빠르다고 알려진 알고리즘을 제공한다. C나 포트란으로 작성된 알고리즘 버전들을 온라인 상에서 찾아볼 수 있다.