# 浅谈快速傅里叶变换

### 多项式乘法

$B(x)=\displaystyle\sum_{j=0}^{m-1}b_jx^j$

$\displaystyle\sum_{j=0}^{n+m-2}c_jx^j$

$c_j=\displaystyle\sum_{k=0}^{j}a_kb_{j-k}$

### 系数表达与点值表达

1.求值。将AB两个多项式的系数表达转换为点值表达。
2.点值乘法。用AB两个多项式的点值表达得到C的点值表达。
3.插值。将C的点值表达转换为系数表达。

### 使用快速傅里叶变换（FFT）进行求值

$\omega_{n}^{k+n/2}=e^{2k\pi i/n+\pi i}=-\omega_{n}^{k}$
$\omega_{n/2}^{k+n/2}=e^{2k\pi i/(n/2)+2\pi i}=\omega_{n/2}^{k}$

### 使用逆快速傅里叶变换（逆FFT）实现插值

$[VU]_{jj’}=\displaystyle\sum_{k=0}^{n-1} \omega_n^{k(j’-j)}/n$

$=\omega_n^{j’-j}/n \displaystyle\sum_{k=0}^{n-1}\omega_n^k$
$=\omega_n^{j’-j}/n (\omega_n^n -1)/(\omega_n -1)$
$=0$

### 1 thought on “浅谈快速傅里叶变换”

1. I just wanted to jot down a note so as to thank you for those nice pointers you are placing at this website. My rather long internet look up has at the end of the day been honored with professional facts to go over with my two friends. I ‘d suppose that we site visitors actually are very much blessed to dwell in a magnificent website with so many brilliant individuals with helpful principles. I feel truly privileged to have come across the website and look forward to so many more amazing times reading here. Thanks again for all the details.