快速傅里叶变换(FFT)

这几天在家没事慢慢研究了一下集训最后的一个专题FFT, 陈犇讲完还是有点不是很懂, 网上的很多资料都讲的不是很清晰, 由于这个算法太美了, 我有必要写点什么东西表示对前人智慧的赞美! (顺便练练打公式)

1.FFT这玩意是什么?有什么用?

FFT ( fast Fourier transform )的中文名是快速傅里叶变换, 在信号领域有很大的作用, 在ACM中我们常用FFT来求解多项式乘法

举个例子:

y1=2x4+3x2+5x+7
y2=5x3+7x2+11
FFT就是用来快速地计算y1⋅y2所得到的多项式
(y1⋅y2=10x7+14x6+15x5+68x4+70x3+82x2+55x+77)

2.FFT预备知识

1.多项式

1.多项式定义

A(x)=a0+a1x+a2x2+⋯+an−2xn−2+an−1xn−1

A (x) = \sum i = 0 n - 1 a i x i

2.多项式表达方式

系数表达:(a0,a1,a2,⋯,an−2,an−1)
点值表达:选取n个(或以上)不同的值:x0,x1,...xn−2,xn−1, 对多项式A(x)求值得到A(x0),A(x1),⋅⋅⋅,A(xn−1)
那么就称{(xi,A(xi)),0≤i<n,i∈Z}为多项式A(x)的点值表示

举个例子:

f(x)=2+3x+x2这个多项式的系数表达式就是(2,3,1), 点值表达式就是{(0,2),(1,6),(2,12)}或者{(1,6),(2,12),(3,20),(4,30)}
n−1次多项式只要选取任意不同的n个点(或以上)都是可以的

显然不管是点值表达式还是系数表达式都可以唯一确定一个n−1次多项式, 并且它们是可以相互推导的

3.多项式的乘法

系数表达式下的乘法
$A (x) = \sum i = 0 n - 1 a i x i, B (x) = \sum i = 0 n - 1 b i x i$
那么A(x)⋅B(x)就可以表示为
$C (x) = \sum i = 0 2 n - 2 (\sum j = 0 i a j b i - j) x i$
点值表达式下的乘法
${x i, C (x i)} = {x i, A (x i) \cdot B (x i)}$

举个例子:

已知f1(x)=x2+1,f2(x)=x+3
f1(x)的点值表达式是{(0,1),(1,2),(2,5),(3,10)}
f2(x)的点值表达式是{(0,3),(1,4),(2,5),(3,6)}
那么f1(x)⋅f2(x)的点值表达式就是{(0,3),(1,8),(2,25),(3,60)}

2.单位复根

0.引入

先不考虑什么叫做单位复根
先在平面直角坐标系下画一个单位圆, 即{(x,y)|x2+y2=1}
现在我们要在这个圆上取n个点(n>0),使得这n个点恰好把圆弧分成了n等份, 规定第1个点一定是(1,0)

举个例子:

当n=3时, 这些点的坐标按照逆时针顺序分别是

(1, 0), (- 12, 3 \sqrt 2), (- 12, - 3 \sqrt 2)

当n=4时, 这些点的坐标按照逆时针顺序分别是

(1, 0), (0, 1), (- 1, 0), (0, - 1)

当n=8时, 这些点的坐标按照逆时针顺序分别是

(1, 0), (2 \sqrt 2, 2 \sqrt 2), (0, 1), (- 2 \sqrt 2, 2 \sqrt 2),

(- 1, 0), (- 2 \sqrt 2, - 2 \sqrt 2), (0, 1), (2 \sqrt 2, - 2 \sqrt 2)

如果我们把平面直角坐标系看做是复平面, 那么上面那些点就变成了一个复数, 它们正是单位复根

1.单位复根定义

方程xn=1在复数域内一定有n个不同的解
那么规定: wkn是方程xn=1的第k+1个根(0≤k<n)
也就是对应了上面我们从圆上逆时针选取的n个点中的第k个点

举个例子:

w02=1(x2=1的第1个根是 1)
w12=1(x2=1的第2个根是 −1)

w04=1(x4=1的第1个根是 1)
w14=i(x4=1的第2个根是 i)
w24=1(x4=1的第3个根是 −1)
w34=i(x4=1的第4个根是 −i)

w08=1(x8=1的第1个根是 1)
w18=i(x8=1的第2个根是 2√2+2√2i)
w28=1(x8=1的第3个根是 i)
w38=i(x8=1的第4个根是 −2√2+2√2i)
w48=1(x8=1的第5个根是 −1)
w58=i(x8=1的第6个根是 −2√2−2√2i)
w68=1(x8=1的第7个根是 −i)
w78=i(x8=1的第8个根是 2√2−2√2i)

我们不难归纳得到:

w k n = c o s (2 π k n) + s i n (2 π k n) i

规定: 当k≥n时, wkn=wk%nn
例如:w64=w24,w208=w48

2.单位复根性质

下面的只讨论n是2的次方时,即: n=2m,(m≥0)时的性质
画图我们可以很容易的证明

(w k n) 2 = w k n / 2

例如:(w38)2=w34,(w68)2=w64=w24

3.FFT原理

Fast Fourier Transform

用一句话来说就是:将原多项式的系数表达式转换成点值表达式(O(nlog2n)), 再将多项式的点值表达式相乘得到目标表达式的点值表达式(O(n)), 再将点值表达式转换成为系数表达式(O(nlog2n))

为了能够在O(nlog2n)时间内得到多项式的点值表达式, FFT采取了一些小技巧, 选择n个单位复根进行求值, 由于单位复根的一些性质, 我们可以在O(nlog2n)求出它们的值

现在我们有一个最高次幂是m的多项式:

A (x) = a 0 + a 1 x + a 2 x + \dots + a m - 1 x m - 1 + a m x m

1.先将这个多项式的最高次数扩充到2的次方n−1

A (x) = a 0 + a 1 x + a 2 x + \dots + a m x m + 0 \cdot x m + 1 + 0 \cdot x m + 2 + \dots + 0 \cdot x n - 1 (n - 1 \geq m) = a 0 + a 1 x + a 2 x 2 + \dots + a n - 2 x n - 2 + a n - 1 x n - 1

2.分别带入n个不同的单位复根(w0n,w1n,w2n,...,wn−1n)

⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ A (w 0 n) = a 0 + a 1 w 0 n + \dots + a n - 1 (w 0 n) n - 1 A (w 1 n) = a 0 + a 1 w 1 n + \dots + a n - 1 (w 1 n) n - 1 A (w 2 n) = a 0 + a 1 w 2 n + \dots + a n - 1 (w 2 n) n - 1 \dots \dots A (w n - 2 n) = a 0 + a 1 w n - 2 n \dots + a n - 1 (w n - 2 n) n - 1 A (w n - 1 n) = a 0 + a 1 w n - 1 n \dots + a n - 1 (w n - 1 n) n - 1

可以写成一个矩阵:

⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ A (w 0 n) A (w 1 n) A (w 2 n) ⋮ A (w n - 2 n) A (w n - 1 n) ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ = ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 111 ⋮ 11 w 0 n w 1 n w 2 n ⋮ w n - 2 n w n - 1 n (w 0 n) 2 (w 1 n) 2 (w 2 n) 2 ⋮ (w n - 2 n) 2 (w n - 1 n) 2 \dots \dots \dots ⋱ \dots \dots (w 0 n) n - 2 (w 1 n) n - 2 (w 2 n) n - 2 ⋮ (w n - 2 n) n - 2 (w n - 1 n) n - 2 (w 0 n) n - 1 (w 1 n) n - 1 (w 2 n) n - 1 ⋮ (w n - 2 n) n - 1 (w n - 1 n) n - 1 ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ a 0 a 1 a 2 ⋮ a n - 2 a n - 1 ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟

没错我们就是要在O(nlog2n)时间内得到A(w0n),A(w1n),A(w2n),⋯,A(wn−2n),A(wn−1n)这n个值 ! ! !
3.单独考虑其中任意一个方程

A (w k n) = a 0 + a 1 w k n + a 2 (w k n) 2 + \dots + a n - 1 (w k n) n - 1

3.将奇数项和偶数项分开
得到

A (w k n) = (a 0 + a 2 (w k n) 2 + \dots + a n - 2 (w k n) n - 2) + (a 1 w k n + a 3 (w k n) 3 + \dots + a n - 1 (w k n) n - 1) = (a 0 + a 2 (w k n) 2 + \dots + a n - 2 (w k n) n - 2) + w k n (a 1 + a 3 (w k n) 2 + \dots + a n - 1 (w k n) n - 2) = (a 0 + a 2 w k n / 2 + \dots + a n - 2 (w k n / 2) n 2 - 1) + w k n (a 1 + a 3 w k n / 2 + \dots + a n - 1 (w k n / 2) n 2 - 1)

4.假设两个新的多项式:
A0(x)=a0+a2x+⋯+an−2xn2−1
A1(x)=a1+a3x+⋯+an−1xn2−1
那么A(wkn)=A0(wkn/2)+wknA1(wkn/2)
我们只要再次用同样的方法计算A0(x)以及A1(x)就可以在O(nlog2n)时间内求出A(x)的所有点值表达式了

举个例子:

多项式f(x)=a0+a1x+a2x2+a3x3, 我们要计算A(w04),A(w14),A(w24),A(w34)这4个点的值
1.
A(w04)=A0(w02)+w04A1(w02)
A(w14)=A0(w12)+w14A1(w12)
A(w24)=A0(w02)+w24A1(w02)
A(w34)=A0(w12)+w34A1(w12)
2.
A(w02)=A0(w01)+w02A1(w01)
A(w12)=A0(w01)+w12A1(w01)
3.
因为w01=1所以可以直接得到它的值, 也就是当前的系数

上述过程就称为离散傅里叶变换(Discrete Fourier Transform)

我们将多个多项式的点值表达式相乘, 获得了目标表达式的点值表达式
那么: 怎么获得目标表达式的系数表达式呢?

下面我们将要介绍逆离散傅里叶变换(Inverse Discrete Fourier Transform)

⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ A (x 0) A (x 1) A (x 2) ⋮ A (x n - 2) A (x n - 1) ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ = ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 111 ⋮ 11 x 0 x 1 x 2 ⋮ x n - 2 x n - 1 (x 0) 2 (x 1) 2 (x 2) 2 ⋮ (x n - 2) 2 (x n - 1) 2 \dots \dots \dots ⋱ \dots \dots (x 0) n - 2 (x 1) n - 2 (x 2) n - 2 ⋮ (x n - 2) n - 2 (x n - 1) n - 2 (x 0) n - 1 (x 1) n - 1 (x 2) n - 1 ⋮ (x n - 2) n - 1 (x n - 1) n - 1 ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ a 0 a 1 a 2 ⋮ a n - 2 a n - 1 ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟

上面的矩阵就是DFT的过程, 下面的矩阵就是IDFT的过程

⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ a 0 a 1 a 2 ⋮ a n - 2 a n - 1 ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ = 1 n ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 111 ⋮ 11 x - 1 0 x - 1 1 x - 1 2 ⋮ x - 1 n - 2 x - 1 n - 1 (x 0) - 2 (x 1) - 2 (x 2) - 2 ⋮ (x n - 2) - 2 (x n - 1) - 2 \dots \dots \dots ⋱ \dots \dots (x 0) - n + 2 (x 1) - n + 2 (x 2) - n + 2 ⋮ (x n - 2) - n + 2 (x n - 1) - n + 2 (x 0) - n + 1 (x 1) - n + 1 (x 2) - n + 1 ⋮ (x n - 2) - n + 1 (x n - 1) - n + 1 ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ A (x 0) A (x 1) A (x 2) ⋮ A (x n - 2) A (x n - 1) ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟

其实差异并不大, 我们只需要将原来DFT中wkn换成w−kn,结果再乘上1n就从DFT变成了IDFT

Fast Fourier Transform

快速傅里叶变换(FFT)

1.FFT这玩意是什么?有什么用?

举个例子:

2.FFT预备知识

1.多项式

1.多项式定义

2.多项式表达方式

举个例子:

3.多项式的乘法

举个例子:

2.单位复根

0.引入

举个例子:

1.单位复根定义

举个例子:

2.单位复根性质

3.FFT原理

举个例子:

上述过程就称为 离散傅里叶变换(Discrete Fourier Transform)

下面我们将要介绍 逆离散傅里叶变换(Inverse Discrete Fourier Transform)

上面的矩阵就是DFT的过程, 下面的矩阵就是IDFT的过程

相关推荐

上述过程就称为离散傅里叶变换(Discrete Fourier Transform)

下面我们将要介绍逆离散傅里叶变换(Inverse Discrete Fourier Transform)