大概就是myy论文里的那些东西吧,闲着没事整理一下。

记FFT变换的矩阵为$F$(即单位根的范德蒙德矩阵),将FFT视作$F$乘上待变换的行向量:$FFT(a)=Fa$。我们记$\overline F$为$F$的复共轭矩阵(矩阵的每个元素都共轭),$a'$为$a$除了第$0$项外都翻转后的结果(本文的所有矩阵、向量的下标均从$0$开始),即第$a_i$与$a_{n-i}$交换($n$为$a$的长度)。显然$a'$可以写成$a$乘上一个翻转矩阵$T$,即$a'=aT$。

  • 性质 1:$\overline Fa=(Fa)'$

这个根据单位根的性质$\omega^{-k}=\omega^{n-k}$可以轻易得到。

  • 性质 2:$F^{-1}=\overline F/n$

这其实就是IFFT最后一步干的事情。。

技巧 1:快速求两个实多项式的点值(以及插值)

现在有两个实向量$a,b$,我们想计算$Fa,Fb$。按照一般的做法,直接跑两遍FFT就行了。其实这个过程可以做到只用一次FFT。

我们构造复向量$a+bi$,考虑把这个向量FFT: $$F(a+bi)=Fa+F(bi)=Fa+iFb$$

我们把这整个东西取复共轭,看看会发生什么: $$ \begin{aligned} \overline{F(a+bi)}&=\overline {Fa}+\overline {iFb}\\ &=\overline Fa-i\overline Fb\\ &=(Fa)'-i(Fb)'\\ \end{aligned} $$

两边同时乘上$T$,再联立之前FFT的结果: $$ Fa-iFb=(\overline{F(a+bi)})'\\ Fa+iFb=F(a+bi) $$

知道这两个东西之后,可以直接解出$Fa,Fb$。也就是说,我们直接算出$a+bi$的FFT,把它复共轭之后翻转系数(从第$1$项开始翻转),之后就可以解出$Fa$和$Fb$了。

同理,我们也可以同时做两个实多项式点值的插值。把这整个过程反过来做一遍即可。

技巧 2:4次FFT的任意模数多项式乘法

这其实是上面那个东西的一个应用。现在有两个整系数多项式$A(x),B(x)$,我们要算它们循环卷积的结果(如果要做普通卷积,直接把次数扩大一倍即可),所有系数都对一个$10^9$级别的整数$P$取模(这个整数可以什么性质都没有)。我们考虑选取整数$M\approx\sqrt P$,我们把$A,B$的系数对$M$作带余除法,得到$A(x)=A_0(x)+MA_1(x),B(x)=B_0(x)+MB_1(x)$。这里$A_0,A_1,B_0,B_1$的系数都是$M$级别的,他们之间乘起来之后系数是$O(M^2n)=O(Pn)$级别的,$n$不太大的话(大概$5*10^5$以内)可以认为是在double的精度范围内,可以直接用double做乘法后取模。

我们用上面提到的那个技巧,用$2$次FFT算出$A_0,A_1,B_0,B_1$的FFT点值$a_0,a_1,b_0,b_1$,之后根据$$\begin{aligned}A(x)B(x)&=A_0(x)B_0(x)\\&+M(A_0(x)B_1(x)+A_1(x)B_0(x))\\&+M^2A_1(x)B_1(x)\end{aligned}$$我们可以再次使用上面那个技巧,用$2$次FFT算出$a_0\otimes b_0,a_0\otimes b_1,a_1\otimes b_0,a_1\otimes b_1$的IFFT插值,就可以直接进行计算了。

总共$4$次FFT。

技巧 3:2次FFT的实多项式乘法

这个用技巧$1$也可以做到,但较技巧$1$更容易实现。
有两个实多项式$A(x),B(x)$,我们要计算它们的循环卷积。

我们可以用两次FFT计算$(A(x)+iB(x))^2=A^2(x)-B^2(x)+2iA(x)B(x)$。

直接取虚部并除以2即可。