快速沃尔什变换

Published: by Creative Commons Licence

  • Tags:

引言

快速沃尔什变换(Fast Walsh Transform)适用于计算一类多项式卷积的高效算法。定义

\[C=A\otimes B=\sum_{k=0}^nX^k\sum_{i\oplus j=k}A_iB_j\]

其中$A$,$B$,$C$均为$n$阶多项式。而$A_i$,$B_j$分别表示多项式$A$中$X^i$项的系数和多项式$B$中$X^j$项的系数。

看着眼熟吧,这不是和多项式的乘法非常像吗,当$i\oplus j=i+j$时,上面就是我们熟知的多项式乘法公式。我们知道解决多项式乘法不仅有$O(n^2)$的朴素算法,还有$O(n\log_2n)$的快速傅里叶变换。快速傅里叶变换实际上是将两个多项式$A$,$B$转换为点值表示法DFT(A)和DFT(B),之后利用向量乘法得到DFT(C)=DFT(A)DFT(B),最后从DFT(C)中还原多项式$C$。我们不免想到,是否能利用同样的技术进行加速呢?

或运算

如果$i\oplus j=i\mid j$,那么我们可以定义:

\[FWT(A)=\sum_{i=0}^{n}X^i\sum_{j\in i}A_j\]

其中$j\in i$表示j中$1$出现的二进制位置是$i$的子集,换言之$i=i\mid j$。我们注意到

\[FWT(C)_k=\sum_{t\in k}C_t=\sum_{t\in k}\sum_{i\mid j=t}A_iB_j=\sum_{i\mid j\in k}A_iB_j\\ =\sum_{i\in k}A_i\sum_{j\in k}B_j=(\sum_{i\in k}A_i)(\sum_{i\in k}B_i)=FWT(A)_k\cdot FWT(B)_k\]

因此我们发现了$FWT(C)=FWT(A)\cdot FWT(B)$。下面我们讨论如何快速计算$FWT(A)$。记$m=\lceil \frac{n}{2} \rceil$,$L(A)=\sum_{i=0}^{m-1}A_iX^i$,$R(A)=\sum_{i=m}^nA_iX^i$。很显然$A=L(A)+R(A)\cdot X^m$。

\[FWT(A)=\sum_{i=0}^{n}X^i\sum_{j\in i}A_j=\sum_{i=0}^{n}X^i(\sum_{j\in i,j<m}A_j+\sum_{j\in i,j\geq m}A_j)\\ =\sum_{i=0}^{m-1}X^i(\sum_{j\in i,j<m}A_j+\sum_{j\in i,j\geq m}A_j)+\sum_{i=m}^{n}X^i(\sum_{j\in i,j<m}A_j+\sum_{j\in i,j\geq m}A_j)\\ =\sum_{i=0}^{m-1}X^i\sum_{j\in i}L(A)_j+X^m\sum_{i=0}^{m-1}X^i(\sum_{j\in i}L(A)_j+\sum_{j+m\in i+m}R(A)_j)\\ =FWT(L(A))+X^m(FWT(L(A))+FWT(R(A)))\]

我们可以简单地记作

\[FWT(A)=(FWT(L(A)), FWT(L(A))+FWT(R(A)))\]

这样我们可以每次都将$A$拆分为前部和后部进行分治计算。时间复杂度为$O(n\log_2n)$。而$FWT$的逆也很容易得到:

\[FWT^{-1}(A)=FWT^{-1}(L(A))+X^mFWT^{-1}(R(A)-L(A))\\ =(FWT^{-1}(L(A)),FWT^{-1}(R(A)-L(A)))\]

同样可以采用分治算法解决。

且运算

如果$\oplus$代表且运算,那么$FWT$函数定义如下:

\[FWT(A)=\sum_{i=0}^nX^i\sum_{i\in j}A_j\]

其余推理类似,不再赘述,直接给出公式:

\[FWT(C)=FWT(A)\cdot FWT(B)\\ FWT(A)=(FWT(L(A))+FWT(R(A)),FWT(R(A)))\\ FWT^{-1}(A)=(FWT^{-1}(L(A)-R(A)),FWT^{-1}(R(A)))\]

异或运算

如果$\oplus$代表亦或运算。记$E$为所有二进制形式中1的个数为偶数个的正整数集合,而$O$表示所有二进制形式中1的个数为奇数个的正整数集合。那么$FWT$函数定义如下:

\[FWT(A)=\sum_{i=0}^nX^i(\sum_{i\&j\in E}A_j-\sum_{i\&j\in O}A_j)\]

由于(可以通过枚举证明)

\[(i\&j)\oplus k=(i\oplus k)\&(j\oplus k)\]

因此:

\[FWT(C)_k=\sum_{k\&t\in E}C_t-\sum_{k\&t\in O}C_t\\ =\sum_{k\&t\in E}\sum_{i\oplus j=t}A_iB_j-\sum_{k\&t\in O}\sum_{i\oplus j=t}A_iB_j\\ =\sum_{k\&(i\oplus j)\in E}A_iB_j-\sum_{k\&(i\oplus j)\in O}A_iB_j\\ =\sum_{(k\&i)\oplus (k\& j)\in E}A_iB_j-\sum_{(k\&i)\oplus (k\& j)\in O}A_iB_j\\\]

记$b(i)$表示$i$的二进制形式中$1$的个数。记$r$表示$i\oplus j$中可能的$1$的数量,初始值为$b(i)+b(j)$。遍历每一位,若浏览某一位时,$i$与$j$均为$0$,则$r$不变,若一者为$1$,$r$依旧不变,否则二者都为$1$,则$r$减少2。很显然这个算法最终得到的就是$b(i\&j)$。因此我们证明了$b(i\&j)$与$b(i)+b(j)$的二进制形式中1出现的次数拥有相同的奇偶性。

\[=\sum_{k\&i \in E}A_i\sum_{k\&j\in E}B_j+\sum_{k\&i \in O}A_i\sum_{k\&j\in O}B_j-\sum_{k\&i \in E}A_i\sum_{k\&j\in O}B_j-\sum_{k\&i \in O}A_i\sum_{k\&j\in E}B_j\\ =(\sum_{k\&i \in E}A_i-\sum_{k\&i \in O}A_i)(\sum_{k\&i \in E}B_i-\sum_{k\&i \in O}B_i)\\ =FWT(A)_kFWT(B)_k\]

因此我们可以推出:

\[FWT(C)=FWT(A)\cdot FWT(B)\]

接着我们考虑如何拆分多项式。

\[FWT(A)=\sum_{i=0}^nX^i(\sum_{i\&j\in E}A_j-\sum_{i\&j\in O}A_j)\\ =\sum_{i=0}^nX^i(\sum_{i\&j\in E,j<m}A_j+\sum_{i\&j\in E,j\geq m}A_j-\sum_{i\&j\in O,j<m}A_j-\sum_{i\&j\in O,j\geq m}A_j)\\ =\sum_{i=0}^{m-1}X^i(\sum_{i\&j\in E,j<m}A_j+\sum_{i\&j\in E,j\geq m}A_j-\sum_{i\&j\in O,j<m}A_j-\sum_{i\&j\in O,j\geq m}A_j)\\ +\sum_{i=m}^nX^i(\sum_{i\&j\in E,j<m}A_j+\sum_{i\&j\in E,j\geq m}A_j-\sum_{i\&j\in O,j<m}A_j-\sum_{i\&j\in O,j\geq m}A_j)\\ =\sum_{i=0}^{m-1}X^i(\sum_{i\&j\in E}L(A)_j+\sum_{i\&j\in E}R(A)_j-\sum_{i\&j\in O}L(A)_j-\sum_{i\&j\in O}R(A)_j)\\ +X^m\sum_{i=0}^{m-1}X^i(\sum_{i\&j\in E}L(A)_j+\sum_{i\&j\in O}R(A)_j-\sum_{i\&j\in O}L(A)_j-\sum_{i\&j\in E}R(A)_j)\\ =FWT(L(A))+FWT(R(A))+X^m(FWT(L(A))-FWT(R(A)))\\ =(FWT(L(A))+FWT(R(A)),FWT(L(A))-FWT(R(A)))\]

而逆函数容易得到:

\[FWT^{-1}(A)=(FWT^{-1}(\frac{L(A)+R(A)}{2}),FWT^{-1}(\frac{L(A)-R(A)}{2}))\]

整体的时间复杂度为$O(n\log_2n)$。