12.多项式相乘,以及快速傅里叶变换

由于两个n次多项式相乘复杂度为n^2过高,本章讨论如何将复杂度降至n*log(n)

记号

多项式A(X)=/sum^{n-1}_{j=0}{a_j*x^j}

• 次数D(degree) 变量最高的次数
• 次数界DB(degree bound) 严格大于次数的数

C(X) = A(X) * B(X)

也即

A(X) * B(X) = c0 + c1*x + c2 * x^2 + ... c_n * x ^n

c_j = /sum^j_{k=0}{a_k*b_{j-k}}

a_k,b_k当k在[0,n-1]才非0

也即积的系数是乘数被乘数的系数的卷积,convolution

多项式的表示法

1. 系数法

Horner法则

A(x_0) = a_0 + x_0 * (a_1 + x_0 *(...+ a_{n-1} * x_0))

2. 点值表示法

使用n个点值对表示多项式

{(x0,y1),...,(x_{n-1},y_{n=1})}

由Horner法则,系数表示法复杂度为n^2

从点值表示法到系数表示法

对于任意的点值表示法集合, 存在唯一的n次多项式,A(x)满足y_k=A(x_k)

范得蒙矩阵

利用拉格朗日插值公式,可以在平方复杂度内完成

点值法用途

加法可以直接加和

乘法可以直接相乘

离散傅里叶变换

n次单位复根恰好有n个,均匀分布在单位圆上

Wn = e^{2pie/n}为主n次单位根,其它的根均为主单位根的幂

n个n次单位根Wn^0,...Wn^{n-1}在乘法运算下构成一个群

引理

相消引理 w_{dn}^{dk}=Wn^k

Wn^{n/2} = -1 当n为偶数