30. Polynomials and the FFT

빠른 푸리에 변환을 이용해 다항식 곱을 \Theta(n \lg n)에 수행하는 법을 알아보자. 이는 신호 처리 방법의 일종으로 시간 영역에 주어지는 신호를 주파수 영역의 함수의 가중치합으로 변환하는 것이다.

Polynomials

대수체 F 위의 다항식A(x) = \sum_{j=0}^{n-1} a_{j}x^{j} 꼴로 나타내어지는 함수이다. 이 때 a_{0}, \cdots, a_{n-1}계수로 F 내의 원소이다. 0이 아닌 최고차 계수가 a_{k}일 때 차수를 k라 한다. 차수보다 큰 정수를 차수 상한이라 한다. 다항식 덧셈은 두 다항식의 \sum_{j=0}^{n-1} (a_{j} + b_{j})x^{j}를 계산하는 것이다. 다항식의 곱은 체의 모든 원소 x에 대해 C(x)=A(x)B(x)이 되는 다항식 을 계산하는 것이다.

Chapter outline

이 장에서는 빠른 푸리에 변환을 다룬다.

30.1. Representing polynomials

다항식을 어떻게 표현할까?

Coefficient representation

다항식 A(x) = \sum_{j=0}^{n-1} a_{j}x^{j}계수 표현식a = (a_{0}, \cdots, a_{n-1})이다. 이는 여러 연산에 대해 편한데 x = x_{0}에 대해 식을 평가하는 일은 호너의 법칙으로 \Theta(n)에 가능하다. 또는 다항식의 컨볼루션도 계산할 수 있다.

Point-value representation

차수 상한 n인 다항식의 점-값 표현식y_{k} = A(x_{k})일 때 n개의 점-값 쌍 \{(x_{0}, y_{0}), \cdots, (x_{n-1}, y_{n-1})\} 으로 이루어진다. 계수 표현식으로부터 점-값 표현식을 계산하는 것은 쉽고, 역으로 보간하는 방법도 유일하다.

Theorem. (Uniqueness of an interpolating polynomial) 점-값 표현식에서 모든 x_{k}가 서로 다르면 그 점-값 표현식을 갖는 차수 상한 n인 다항식은 유일하다.

이는 라그랑주 식 A(x) = \sum_{k=0}^{n-1} y_{k} \frac{\prod_{j \neq k} (x - x_{j})}{\prod_{j \neq k} (x_{k} - x_{j})}로 더 간단히 구할 수 있다.

Fast multiplication of polynomials in coefficient form

계수 표현식으로 쓰인 다항식의 곱을 빠르게 계산하려면 다음과 같이 수행한다.

  1. A(x)와 B(x)을 앞 계수에 0을 추가해 차수 상한 2n의 계수 표현식을 만든다.
  2. 2n차 FFT를 각각 적용해 점-값 표현식을 계산한다.
  3. 이들로부터 곱한 다항식의 점-값 표현식을 구한다.
  4. 이를 보간해 곱한 다항식의 계수 표현식을 구한다.

Theorem. 계수 표현식이 주어진 차수 상한 n의 다항식 2개는 FFT로 \Theta(n \lg n)로 구할 수 있다.

30.2. The DFT and FFT

DFT와 FFT를 알아보자.

Complex roots of unity

복소 1의 n제곱근\omega^{n} = 1을 만족하는 복소수이다. \omega_{n} = e^{\frac{2 \pi i}{n}}1의 주 n제곱근이라 한다. 이 때 다음이 성립한다.

Lemma. (Cancellation Lemma) $\latex \omega_{dn}^{dk} = \omega_{n}^{k}&s=1$.

Corollary. \omega_{n}^{\frac{n}{2}} = \omega_{2} = -1.

Lemma. (Halving Lemma) n > 0이 짝수이면 복소 1의 n제곱근 n개의 제곱은 복소 1의 (n / 2) 제곱근 (n / 2)개이다.

Lemma. (Summation Lemma) \sum_{j=0}^{n-1} (\omega_{n}^{k})^{j} = 0.

The DFT

다항식 A(x)에 대해 y_{k} = A(\omega_{n}^{k})이라 할 때 y = (y_{0}, \cdots, y_{n-1})이산 푸리에 변환(DFT)이라 한다.

The FFT

빠른 푸리에 변환(FFT)를 통해 이산 푸리에 변환을 \Theta(n \lg n)에 계산할 수 있다. 과정은 다음과 같다.

RECURSIVE-FFT(a)
n = a.length  // n is a power of 2
if n == 1
    return a
ω_n = e^(2πi/n)
ω = 1
a_[0] = (a_0, a_2, ..., a_(n-2))
a_[1] = (a_1, a_3, ..., a_(n-1))
y_[0] = RECURSIVE-FFT(a_[0])
y_[1] = RECURSIVE-FFT(a_[1])
for k = 0 to n/2 - 1
    y_k = y_[0]_k + ωy_[1]_k
    y_(k+(n/2)) = y_[0]_k - ωy_[1]_k
    ω = ωω_n
return y   // y is assumed to be a column vector

\omega_{n}^{k}는 덧셈과 뺄셈 형태로 번갈아서 나타나므로 이를 회전 인자라 부른다.

Interpolation at the complex roots of unity

이제 복소 1의 n제곱근으로 보간을 할 수 있다.

Theorem. y = V_{n} a라 할 때 (V_{n}^{-1})_{jk} = \frac{\omega_{n}^{-kj}}{n}이다.

Theorem. (Convolution theorem) a \otimes b = DFT_{2n}^{-1} (DFT_{2n}(a) DFT_{2n}(b))이다.

30.3. Efficient FFT implementations

효과적인 FFT 구현을 알아보자.

An iterative FFT implementation

공통 부분표현식 \omega_{n}^{k} y_{[1], k}을 캐싱해 두어 나비 연산을 활용하면 좋다. 이를 이용해 반복적으로 구현하면 다음과 같다.

ITERATIVE-FFT(a)
BIT-REVERSE-COPY(a, A)
n = a.length // n is a power of 2
for s = 1 to lg n
    m = 2^s
    ω_m = e^(2πi/m)
    for k = 0 to n - 1 by m
        ω = 1
        for j = 0 to m/2 - 1
            t = ωA[k + j + m/2]
            u = A[k + j]
            A[k + j] = u + t
            A[k + j + m/2] = u - t
            ω = ωω_m
return A

BIT-REVERSE-COPY는 비트 반전 순열을 수행한다.

BIT-REVERSE-COPY(a, A)
n = a.length
for k = 0 to n - 1
    A[rev(k)] = a_k

A parallel FFT circuit

FFT는 특성상 효과적으로 병렬화가 가능하다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중