FFT가 빠른 이유

 

다항식 A(x)와 B(x)의 곱을 C(x)라고 하자. 

이때 다항식 C(x)의 각 항의 계수들은 다음과 같이 각 항을 차례대로 곱하는 분배법칙을 통해서 구할 수 있다. 

다항식 간의 곱 연산 시 계산되는 요소는 각 항의 계수이므로 다음과 같이

다항식의 각 항의 계수들만 배열의 형태로 나타내는 방법을 Coefficient Representation이라고 한다. 

Coefficient Representation을 이용해 각 항을 곱해나가며 계산을 할 경우 

A(x)의 각 항은 B(x)의 모든 항과 한 번씩 곱연산을 수행해야 한다. 

따라서 A(x), B(x)를 최고차항이 d라고 하면 A(x)의 하나의 항당 B(x)의 모든 d개의 항에 대해서 곱연산을 하며 

이를 A(x)의 모든 d개 항에 실시하므로 기본적으로 총 d*d번의 연산이 필요하며 

이후 각 동차항끼리 정리하는 과정에서 몇 번의 합 연산 k번이 더 필요하다. 

d^2 + k 번의 연산을 Big-O 방법으로 나타내면 $O(d^2)$으로 표현할 수 있다. 

 

 $O(d^2)$ 는 데이터의 수의 제곱에 비례해서 연산 횟수가 증가하기 때문에 연산 자원이 많이 필요하게 된다. 

더 좋은 방법은 없을 까?

 2차원의 좌표평면이 주어졌을 때 하나의 직선을 정의하려면 어떻게 해야 할까?

직선의 방정식은 $y = ax + b$ 형태로 나타난다. 

이는 y-x 좌표평면에서 나타나는 직선은 a, b 두 개의 미지수를 가지며 따라서

하나의 직선의 방정식을 정의하기 위해서는 해당 직선의 방정식 위에 있는 점(해) 두 개를 알아야 한다. 

일차방정식은 점 두개가 필요하다.

 

 

위와 같이 하나의 점만 주어지게 되면 이 점을 지나가는 직선의 수는 무한히 많지만

두 개의 점이 주어지면 좌표평면 상에서 하나의 직선만을 구분하여 정의할 수 있다. 

 특정한 하나의 1차 다항식을 나타내기 위해서는 점 2개가 필요하며

아래와 같이 특정한 하나의 2차 다항식을 나타내기 위해서는 점 3개, 3차 다항식은 점 4개가 필요하다. 

최고차항이 d인 다항식은 상수항까지 포함해서 총 d+1개의 계수가 미지수로 나오며

d+1개의 미지수를 구하기 위해서는 d+1개의 해(직선상의 점)를 차례로 다항식에 대입해서 연립방정식을 풀어야 한다. 

즉 하나의 d차 다항식을 표현하기 위해서는 d+1개의 점이 필요하며 이렇게 표현하는 방식을 

Value Representation이라 한다. 

다항식에 각 점을 대입한 형태를 열거한 형태를 행렬을 이용해서 표현하게 되면 선형대수를 이용해서 효과적인 해석이 가능하다. 



행렬 M은 임의의 점들 $x_0, x_1,... , x_d$에 대해서 역행렬이 존재한다. 

역행렬이 존재한다는 것은 행렬의 행렬식 값이 0이 아니라는 뜻이고 이는 어떠한 벡터 값 세트를 해당 시스템으로 선형 변환 시 

또 다른 하나의 벡터 값 세트로 맵핑되기 때문에 대응관계가 되어 다시 원복 하고자 할 때 역변환이 가능하다는 뜻이다. 

즉 위에서 양쪽의 $M^(-1)$를 하여 고유한 $p_0, p_1,..., p_d$를 찾을 수 있으며 이 계수 세트들로 하나의 다항식을 정의할 수 있다. 

 

 

C(x) = A(x) B(x)를 Coefficient Representation 방법으로 구할 때는

A(x), B(x)의 각 계수들을 분배법칙을 통해서 차례대로 곱해가며 구하였다.

 

이번에는 Value Representation 방법을 이용해서 C(x)를 구해 보자. 

C(x)는 A(x)와 B(x)의 곱이기 때문에 최고차항은 2차 * 2차 = 4차이다. 따라서 다항식 C(x)를 Value Representation으로 

구하기 위해서는 4+1로 총 5개의 점이 필요하다.  그러면 이 5개의 점은 어디서 가져올까?

C(x)는 A(x) B(x)이므로 A(x)와 B(x)에서 동일한 x값을 가지는 각 다항식 위의 점 5개씩을 가져와서 이 점들의 y값을 각각 곱하면

C(x) 상의 놓여있는 5개의 점을 찾을 수 있다. 

C(x) 상의 5개의 점을 찾았기 때문에 이를 이용해서 4차 다항식 C(x)를 특정할 수 있다.

 

Value Representation 방법을 이용해 다항식 간의 곱 결과를 찾는 과정을 정리해 보면

 

1. A(x)와 B(x)에서 같은 정의역(x)의 점을 C(x)의 최고차항 d +1 개만큼 뽑는다. 

 

예를 들어 x = -2, -1, 0, 1, 2에 해당하는 점

(-2, A(-2) ) , (-1, A(-1) ), (0, A(0) ), (1, A(1) ), (2, A(2) ), (-2, B(-2) ) , (-1, B(-1) ), (0, B(0) ), (1, B(1) ), (2, B(2) )

 

2. 추출한 점들을 같은 x값의 점끼리 함숫값을 곱한다. 

 

C(-2) = A(-2) X B(-2), C(-1) = A(-1) X B(-1), C(0) = A(0) X B(0), C(0) = A(1) X B(1), C(2) = A(2) X B(2)

 

3. 구한 C(0),... , C(5)를 Value Representation 방법을 통해 C(x)를 구한다. 

 

이러한 과정에서 필요한 연산은 A(x), B(x)에서 각각 추출한 d개의 점을 곱하는 것이다. 

따라서 이를 Big - O로 표현하게 되면 $O(d)$ 가 된다.

 

하지만 Value Representation을 활용하기 위해서는 다항식 형태로 나타난 A(x), B(x)에서 점을 d+1개만 큼

뽑는 과정이 필요하며 이렇게 뽑은 점들을 곱하는 과정을 거친 후에는 d+1개 점들로 나타난 C(x)를 다시 다항식의 형태로

바꾸어주는 과정이 필요하다. 

그리고 각 다항식에서 점을 뽑는 과정을 최적화한 것이 바로 FFT이다. 

FFT와 다항식에서 점을 뽑는 과정이 무슨 상관이 있을까?

 

일단은 각 다항식에서 점을 뽑는 과정인 Evaluation에 대해서 살펴보자. 

최고차항이 d인 다항식 P(x)에서 n(d+1)개의 x값을 정한 뒤에 이를 P(x)에 대입해서 $P(x_n)$값을 구해야 한다. 

P(x)가 d차 다항식이므로 하나의 $x_n$값을 대입하면 다항식 안에서 $p_1$부터 $p_d$까지 상수항을 제외한 d번의 곱 연산이 이루어지고 이를 n개의 점들에 대해서 모두 수행해야 하므로 총 d*n 연산이 필요하며  Big-O로 나타내면 $O(d^2)$이다. 

$O(d^2)$은 다항식 차수에 제곱에 비례해서 연산이 필요하므로 너무 크다. 

이를 줄이는 방법이 바로 FFT이다.  

 

아래와 같이 함수 P(x)가 우함수의 형태를 가지고 있으면 8개의 점을 뽑기 위해서 몇 개의 x값을 다항식 P(x)에 집어넣어야 할까?

우함수의 특징은 y축을 기준으로 하여 같은 절댓값 x에 대한 y값이 동일하다. 따라서 8개의 점을 뽑기 위해서는 4개의 x값만 계산하면

나머지 x값은 우함수의 특징 때문에 동일한 값을 가지게 된다. 

즉 우함수에서 Evaluation을 수행할 때는 $(d+1)/2$ 번만 P(x)에 점을 대입하면 된다. 

그러면 기함수의 경우는 어떨까? 우함수와 마찬가지로 기함수는 x축에 대하여 같은 절댓값 x에 대해서 동일한 y값에 부호 (-) 붙이면 된다. 따라서 기함수의 경우에도 Evaluation을 수행할 때는 $(d+1)/2$ 번만 P(x)에 점을 대입하면 된다. 

우함수와 기함수는 Evaluation 연산을 횟수를 반으로 줄일 수 있다. 하지만 일반적으로 마주하는 다항식의 경우에는 

우함수나 기함수의 형태를 가지고 있지 않다. 그러면 이 방법을 어떻게 써먹을 수 있을까?

 

어떠한 방법이 존재하는 데 해당 시스템에서는 그 방법을 사용하지 못하는 경우

그 시스템을 방법을 적용가능하도록 변형하면 된다. 

 

주어진 P(x)는 5차 다항함수로 Value Representation을 위해서는 d+1 = 6개의 점을 추출해야 한다. 

즉 임의의 x값을 6개 정한 뒤 해당 x값들을 P(x)에 대입하여 (x, P(x)) 값들을 찾아야 한다. 

이 과정에서 $O(d^2)$번의 연산이 필요하고 이를 줄이는 것이 목적이다. 

 

총 6개의 점들을 뽑을 x값을 설정할 때 우함수, 기함수 특징을 활용할 수 있도록 절댓값이 같은 양수, 음수를 3개씩 뽑는다.

(-3, -2, -1, 1, 2, 3) 

 

주어진 다항식 P(x)를 짝수항은 짝수항끼리 홀수항은 홀수항끼리 묶어 우함수, 기함수 형태를 만든다. 

 

$$P(x_i) = 우함수부 + 기함수부$$

$$P(-x_i) = 우함수부 - 기함수부$$

 

양수영역의 x들(1,2,3)들을 대입해서 우함수부와 기함수부를 구하면 

음수영역의 x들(-1,-,2,-3)은 위에서 구한 우함수부 - 기함수부로 구할 수 있기 때문에 별도로 

P(x)에 음수부의  x 값들을 대입할 필요가 없어지며 Evaluation에서 필요한 연산을 절반 줄일 수 있게 된다. 

또한 P(x)를 우함수와 기함수부로 나눈 후 각 항을 제곱항으로 대치하고 $x^2$을 대입하면

각 항에서의 $x^n$ 연산을 $x^{n/2}$로 줄일 수 있게 된다. 

 

정리하면 

위와 같은 과정을 나누어진 우함수부와 기함수부의 최고차항이 2차가 될 때까지 반복적으로 실시하면

기존에 $O(n^2)$이었던 Evaluation 과정이 $O(nlog(n))$으로 줄어든다. 

 

1.  n 부분 :  P(x)의 최고차항 d가 증가할 때마다 d+1 =n인 뽑아야 하는 점의 개수가 선형적으로 증가. 

2. log(n) 부분: 각 과정에서 우함수부와 기함수부, 반으로 쪼개기 때문에 d가 2배 증가해야 위의 과정이 한번 더 반복된다.

 

Evaluation에 필요한 연산을 획기적으로 줄였으나 아직까지는 완전한 방법이 아니다. 

이 방법은 각 phase에서 각 절댓값의 x들이 (+), (-) 페어를 이루어야 우함수, 기함수 성질을 이용할 수 있다. 

하지만 다음의 경우를 살펴보자. 

주어진 P(x)는 3차 다항식으로 4개의 점이 필요하며 따라서 $x_1, x_2$는 각각 양수, 음수가 페어를 이룬다. 

여기서 한 단계 더 나아갔을 때 문제가 생긴다.  $x_1, x_2$의 각각의 제곱은 둘 다 양수이기 때문에 양수, 음수 페어를 이루질 못한다.

 다음 단계를 위해서는 위와 같이 $x_1^2$, $-x_1^2$와 같이 양수와 음수 페어를 이루어야 한다. 

어떻게 전단계에서 제곱을 했는데 음수가 나올 수 있을까? 이제 여기서 허수 $i$가 등장한다. 

처음 4개의 수를 선택할 때 한쪽은 실수부의 양수, 음수를 반대쪽은 허수의 양수, 음수를 택하게 되면 다음 단계에서 

실수의 양수, 음수 페어를 이루기 때문에 한번 더 이 과정의 반복이 가능해진다. 

그러면 이러한 과정을 일반화해 보자.

P(x)의 최고차항이 5인경우, d+1인 6개점이 필요하지만 2의 제곱 형태가 되어야 해당 방법을 반복적으로 수행하기가 편하므로

$2^2=8$개의 점을 뽑는다. 그리고 이점들에 대해서 8 -> 4 -> 2 ->1 순서로 기함수, 우함수 나누고 x를 $x^2$로 치환하는 과정을 

거치면 된다. 따라서 최초의 +-x 페어들은 8 제곱근이 1이 되는 복소수들의 집합으로 구성된다. 

정리하자면 주어진 다항식 P(x)의 최고차항이 $d$일 때 최소 d+1 이상의 점 n개가 필요하게 되며 이후 과정을 편리하도록 만들기 위해

2의 거듭제곱수를 n으로 선택하면 첫 단계에서 추출할 점들은 n개이며, n개의 x값들은 1의 n거듭제곱근들로 구성된다. 

 

여기서 1의 거듭제곱근이 무엇인지 짚고 넘어가자. 

 

실수축과 허수축으로 이루어진 복소평면 상에서 복소수를 표현할 때 

반지름이 $R$인 원에서 삼각함수로 x와 iy 값을 바꾼 뒤에 오일러 공식을 이용하면 복소수를 지름과 각도로 나타낼 수 있다. 

1의 거듭제곱근은 거듭제곱을 했을 때 1이 되는 복소수들을 의미한다. 

임의의 1의 세제곱근을 q라고 해보자. 

$$q^3 =1$$

 

첫 번째로 세 번 제곱했을 때 1이 되는 수는 무엇이 있을까? 

1은 몇번을 제곱하던 1이다. 따라서 1은 모든 거듭제곱의 거듭제곱근이 된다. 

1을 반지름이 1인 단위원위에 $e^{i\phi}$형태로 표현하기 위해서는 지수 부분이 0이 되어야 하므로

$$e^{i0} = 1$$ 복소평면 상에 표현하면 각도가 0이 된다.

 

다음은 $q=e^{i(2\pi/3)}$라하자. 

이때 $q$를 세제곱 하게 되면 $q=e^{i(2\pi/3*3)}=e^{i(2\pi)}$가된다. 

$0 = 2\pi$이므로 1이된다. 

따라서 $q=e^{i(2\pi/3)}$는 1의 세제곱근이다. 

 

마지막으로 $q=e^{i(4\pi/3)}$ 또한

세제곱 하게 되면 $q=e^{i(4\pi/3*3)}=e^{i(4\pi)}$

$0 = 4\pi$이므로 1이 되므로

 $q=e^{i(4\pi/3)}$ 는 1의 세제곱근이다. 

이를 n제곱근에 대하여 일반화하면  1의 n제곱근은 n개가 존재하며 

각 개의 제곱근은 단위원 상에서 각도를 달리하며 나타나는데 이때 해당 각도는 

$$e^{2\pi j/n}$$이다. 이때 j는 0부터 n-1까지(총 n개)의 정수로 이루어진다.

이때 각 $$e^{2\pi j/n}$를 $w_j$라하면 

1의 n제곱근은 ${w_0, w_1, w_2, \dots, w_{n-1}}$이다. 

 

우리는 지금 Value Representation 방법을 이용하여 다항식간의 곱을 계산하는 방법에 대하여 다루었으며 

C(x) = A(x) B(x)라 할 때 C(x)의 최고차항이 d인 경우 A(x)와 B(x) 각각에서 최소 d+1개의 x값에 대하여 함숫값을 계산한 다음

같은 $x_n$의 $A(x_n)$와 $B(x_n)$을 각각 곱하여 d+1개의 $C(x_n)$를 찾아 이들을 이용해 다항식 C(x)를 찾는 것이다. 

 

이때 문제가 $A(x_n)$와 $B(x_n)$에 값을 계산하기 위해서는 d+1개의 x값을 각 함수에 대입하여 y값을 계산할 때 

각 다항식의 차수*점의 개수만큼의 곱연산이 필요하기 때문에 $O(d^2)$이 되어 Evaluation 과정에서 연산이 너무 많이 든다는 것이었다.

 

이를 해결하기 위하여 FFT방법을 도입하여 최고차항이 d인 P(x)에서 d+1개의 x값에 대하여 다항식의 함숫값을 계산할 때

기함수와 우함수의 성질을 이용하여 연산을 줄이는 방법을 고안하였으며 

d+1개의 점을 뽑을 때 양수, 음수 페어가 되도록 뽑은 뒤 다항함수를 우함수, 기함수 파트를 나누면 

함숫값 계산 시 양수부만 계산을 해도 우함수, 기함수 성질에 따라 음수부를 바로 구할 수 있게 되었다. 

또한 기함수부와 우함수부의 x값을 $x^2$으로 치환하여 각 항의 차수를 줄임으로써 다항함수 내에서의 연산을 더 줄일 수 있었다.

 

여기까지 Evaluation의 방법은

1. 양수, 음수 페어를 이루는 x 세트에 대하여

2. 다항함수를 우함수, 기함수 부로 나눈 뒤

3. x를 $x^2$으로 치환한다. 

 

이 방법을 우함수부, 기함수로 나누어진 부분들에 대하여 반복적으로 수행하여

Evaluation시 필요한 연산을 $O(nlog(n))$으로 줄였는데 

이 방법을 반복적으로 사용하기 위해서는 반드시 각 단계에서 짝수부와 음수부가 페어를 이루어야 한다. 

따라서 이를 만족하기 위하여 허수를 도입하여 각 단계에서 페어를 이루는 묶음을 찾았으며 

이를 일반화한 결과 첫 번째 단계에서 선택해야 하는 x값들은 

P(x)의 최고차항이 d일 때 d+1 이상의 값들 중에 2의 거듭제곱이 되는 값을 n으로 선택하면

1의 n제곱근들의 집합으로 이루어진다.

이때 각 x값들은 $e^{2\pi j/n}$이다. (이때 k는 0부터 n-1까지의 정수)

 

 

1의 n제곱근들이 각 단계마다 양수, 음수 페어를 진짜 이루는지 확인해 보자. 

선택된 $w_j$는 $w_{j+n/2}$과 모두 짝을 이룬다. 

양수부 음수부 페어가 제곱을 했을 때 반으로 줄어들지만 여전히 양수부, 음수부 짝을 이룬다. 

따라서 Evaluation시 $e^{2\pi j/n}$들을 초기 x값들로 정하면 된다. 

---

 

앞에서 다루었던 모든 것들이 DFT를 FFT로 바꾸는 과정이다. 

이제 푸리에 변환에서 위의 과정들이 어떻게 적용되어 이름도 빠른 Fast Fourier Transform을 만들었는지 살펴보도록 하자. 

 

푸리에 변환은 시간 도메인에서 나타나는 파형을 진동수 도메인으로 옮겨 파형을 구성하는 진동수들을 파악할 수 있도록 해준다. 

이 과정을 푸리에 급수부터 순차적으로 알아보자. 

 

푸리에 급수는 주기함수를 진동수가 k인 각 코사인파와 사인파로 분해하는 과정이다. 

푸리에 급수 과정에서 핵심은 분해하려 하는 파형을 기저가 되는 파형인 $cos(kx), sin(kx)$와 내적 하는 것이다. 

함수 간의 내적은 함수간의 유사한 성분을 추출하는 과정으로서 파형을 진동수가 k인 코사인파와 사인파를 내적 하면 

해당 파형이 진동수가 k인 성분이 얼마나 들어있는지 뽑아낼 수 있다. 

 

따라서 푸리에 급수는 기저가 되는 사인파와 코사인파의 진동수 k를 증가시켜 가며 내적을 하여 각 진동수 k의 성분들을 

원래의 파형에서 추출한 뒤 이들의 합으로 원래의 함수를 풀어서 나타내는 것이다. 

 

또한 오일러 공식을 활용하면 사인과 코사인 조합으로 표현되는 푸리에 급수를 복소수 공간에서 표현할 수 있다. 

이때 $e^{ikx}$ 진동수가 k인 사인과 코사인 기저로서 분해하려는 함수와 내적을 하여

진동수 k성분이 얼마나 들어있는지를 계수 $c_k$로 표현한다. 

복소수 공간에서의 푸리에 급수

이때 기저가 되는$e^{ikx}$는 직교 기저이다. 

이 말은 서로 다른 진동수 k를 가지는 $e^{ikx}$는 서로 직교하기 때문에 내적시 값이 0으로 서로 겹치는 성분이 없다는 뜻이다. 

즉 분해하려는 함수에 기저를 내적시 각 기저만의 고유한 성분만 추출한다는 의미로 뽑아낸 진동수들 간의 서로 간섭이 없다. 

푸리에 급수는 내적을 통해 주기 함수를 기저와 해당기저가 원래의 함수에 얼마나 들어있는지를 나타내는 계수들로 나타난다고 하였다. 

아직 시간 도메인에서 주파수 도메인으로 넘어가지 못하고 시간 도메인 내에서 여러 기저의 파형으로 쪼개진 상태이다. 

 

주기란 어떠한 현상이 반복적으로 일어날 때 현상이 다시 한번 반복되기까지 걸리는 시간을 의미한다. 

진동수는 주기의 역수로서 단위시간 동안 주기적 현상이 몇 번 반복되는지를 나타낸다. 

따라서 푸리에 급수에서 주기가 유한한 경우 시간축에서 각 진동수로 분리된 파형들의 각각의 진동수가 의미를 갖는다. 

각 진동수마다 일정한 시간 간격에서 파형의 반복 횟수가 달리 나타날 것이기 때문이다. 

 

우리가 원하는 건 각 진동수가 얼마큼 있는지이지 진동수에 따라 달라지는 파형의 개수를 보고 싶은 게 아니다. 

푸리에 급수를 통해 각 진동수로 분해해 놓았기 때문에 각 파형이 가진 진동수는 이미 알고 있는 상태이다.  

이때 주기를 무한으로 보낸다. 주기를 무한으로 보낸다는 것은 파형이 한번 반복되는 데 걸리는 시간이 무한이 된다는 뜻이다. 

따라서 진동수에 상관없이 반복되는 파형 하나, 파형의 크기만 남게 된다.  

 

최종적으로 각 진동수에 대한 크기를 알게 되었으며 이 말은 즉슨 시간 도메인을 진동수 도메인으로 옮겼다는 것이다.

 

여기까지 해서 푸리에 변환으로 어떻게 시간 도메인에서 나타난 파형을 분해하여

어떤 진동수들로 구성되어 있는지 진동수 도메인에서 표현할 수 있는지에 대해서 알아보았다.  

 

이제 이 푸리에 변환을 활용해서 마음껏 진동수를 뽑아낼 수 있으면 좋겠지만 현실에서 얻을 수 있는 데이터는 위에서 다루었던 

함수처럼 연속적이지가 않다. 

 

함수가 연속적이면 함수간의 내적을 이용하면 되지만 실제로 다루어야 하는 값들은 측정이 동반되기 때문에 이산적인 형태를 나타난다. 

이를 위해 이산푸리에변환(DFT)가 등장한다. 

 

이산 푸리에 변환은 푸리에 변환과 크게 다르지 않다. 다만 내적의 계산 시 함수 간의 내적이 아니라 

기저가 되는 함수를 이산적인 형태로 표현된 점들과 측정을 통해 얻은 분해할 파형의 점들의 내적을 통해

각 진동수의 성분을 추출한다는 것이다.

 

위의 그림은 실제로는 아날로그 형태일 파형 $f(t)$을 측정시 일정한 간격으로 점을 빼내는 샘플링 과정을 나타낸 것이다. 

 

DFT의 목적은 이렇게 샘플링한 점을 푸리에 변환하여 진동수 성분들을 추출하는 것이다.

이산 푸리에 변환시 사용할 식은 아래와 같다. 복소수 형태의 푸리에 변환 식에서

측정된 전체 샘플 개수를 의미하는 n항과 측정된 샘플들의 순서를 나타내는 인덱스 j가 추가된 모습이다.

 

 

다루어야 하는 데이터가 이산적이므로 곱해져야 하는 각 진동수 기저들도 이에 맞춘 형태로 변형되며 

보기 편하게 행렬의 형태로 나타 낼 수 있다. 

 

0부터 n-1까지 n개의 측정값 $f_j$를 각 진동수 k의 기저를 구성하는 성분들과 짝지어서 내적을 수행한다. 

 

이산 푸리에 변환(DFT)를 이용할 경우에는 $n$개의 $f_n$이 $w^{jk}$ 행렬의 각 행에서 $n$번 곱을 수행하며 이러한 연산을 모든 $n$개의 행에 대해서 반복적으로 수행하므로 빅오 표기법으로 나타내면 DFT 알고리즘의 계산 복잡도는 $O(N^2)$이다. 

 

$O(N^2)$의 경우 주어진 데이터의 개수가 늘어날 때 연산 횟수가 제곱에 비례하여 늘어나므로 연산에 필요한 자원이 엄청나다.  

따라서 DFT는 데이터의 개수가 조금만 늘어나도 연산이 어려움을 겪으므로 

DFT와 똑같은 output을 갖으면서도 연산의 양을 줄일 수 있는 방법이 필요하다. 

 

각 데이터점 $f$를 푸리에 변환하는 $w^{jk}$행렬을 조작하여

좀 더 효율적인 연산이 가능토록 하는 알고리즘이  Fast Fourier Transform (FFT)이다.

 

 FFT 알고리즘의 계산 복잡도는 $O(n*log(n))$이므로 데이터 개수가 늘어날수록 DFT에 비하여 훨씬 빠른 연산이 가능하다.

 

 

푸리에 변환을 살펴보기 전에 다루었던 다항함수를 Value Representation을 통해 연산량을 $O(d^2)$에서 $O(n)$으로 줄이는 과정에서 각 다항함수에서 점을 뽑는 방법인 Evaluation을 최적화한 방법을 이용하면  

DFT를 FFT로 바꿀 수 있다. 

 

Evaluation을 최적화한 방법은 다항함수에 n개의 x값에 대한 함수값을 계산하는 과정을 

1. 우함수, 기함수부 나누기

2. 제곱항으로 대체하기 

3. 이때 x값은 +,-페어를 이루어야함. 

위의 방법을 통해 연산량을 줄인 것이다. 

 

DFT 행렬도 마찬가지로 입력 값을 계수로 하는 다항식 P(x)에 점 n개의 값을 대입하여 n개의 함수값을 구하는 과정이다.

이때 각 점이 스칼라값이 아니라 벡터로 주어지기 때문에 x값의 나열이 아닌 행렬의 형태로 나타난 것이다. 

 

---