算法设计与分析 作业4

第四周作业

1. 计算普通FFT算法的数据写入复杂度

设缓存大小为$M$，块大小为$B$，FFT的采样次数为$N$：

前$\log{\frac{N}{B}}$层，每层Cache Miss为$\frac{N}{B}$，总Cache Miss为$1\cdot\dfrac{N}{B} + 2\cdot\dfrac{\frac{N}{2}}{B} + 4\cdot\dfrac{\frac{N}{4}}{B} +\cdots + 2^{\log{\frac{N}{B}}}\cdot\dfrac{\frac{N}{2^{\log{\frac{N}{B}}}}}{B}=\frac{N}{B}\log{\frac{N}{B}}$

后$\log{B}$层，每层块大小$<B$，因此每一个小块都是一次Cache Miss，总Cache Miss为$\frac{N}{B}\cdot 2+\frac{N}{B}\cdot 4+\cdots+\frac{N}{B}\cdot B=2N-2\frac{N}{B}\approx 2N$

所有层的Cache Miss次数为$O(\frac{N}{B}\log{\frac{N}{B}}+N)$

2. 已知向量$w$，$q=v*w=F^{-1}(F(v)\times F(w))$，求向量$v$

将$w$和$q$进行傅里叶变换得到$F(w)$和$F(q)$。根据卷积定理，卷积在时域中等于频域中的乘法，即$F(q)=F(w)\times F(v)$，可得$F(v)=\dfrac{F(q)}{F(w)}$，对$F(v)$进行傅里叶逆变换即得向量$v$。

3. FFT计算多项式减法卷积

减法卷积相当于把$B=b_0+b_1x+\cdots +b_mx^m$变换成$B’=b_mx^{-m}+\cdots+b_1x^{-1}+b_0$，再计算$C=A\cdot B’$的卷积。

首先对$A$、$B’$两个多项式进行FFT，得到$F(A)$、$F(B)$，之后将两个结果相乘后进行傅里叶逆变换，得到卷积结果，再逆变换即得多项式$C$。

不过$A$也需要预处理移位一下，让系数数组的最前一项代表$x^{-m}$项的系数，最终$c_n$其实是结果多项式$C’$系数数组的第$n+m$项（从$0$开始编号）。

4. 求正整数序列有多少连续子序列满足区间和 $=x$

首先计算前缀和$S_m=\sum\limits_{i=1}^{m}{a_i}$，那么求连续区间和$=x$个数就是求满足$S_i-S_{j-1}=x(i\geq j)$的$(i,j)$对个数。那么定义多项式$A=\sum{[S_m=a的次数]x^a}$，使用第三问中方法计算$A$与$A$的减法卷积得到多项式$B$，$B$的$x$次项系数即为子序列数。

5. FFT解决字符串匹配

(a) 给出一个$O(|S|\log{|S|})$的算法，求出所有$T$在$S$中所有出现的位置。

定义多项式$A=\sum\limits_{i=0}^{|S|-1}\text{ascii}(S_i)x^i$，$B=\sum\limits_{i=0}^{|T|-1}\text{ascii}(T_i)x^i$，$C=\sum\limits_{i=0}^{|S|-|T|}{\left( \sum\limits_{j=0}^{|T|-1}{\left( a_{i+j}-b_{j} \right)^2} x^i\right)}$，显然当$c_i=0$时，代表在第$i$位字符串匹配上了。

看一下如何计算$c_n$：$c_i = \sum\limits_{j=0}^{|T|-1}{\left( a_{i+j}-b_{j} \right)^2}= \sum\limits_{j=0}^{|T|-1}{a_{i+j}^2} + \sum\limits_{j=0}^{|T|-1}{b_{j}^2} - 2\sum\limits_{j=0}^{|T|-1}{a_{i+j}b_j}$

其中$\sum\limits_{j=0}^{|T|-1}{a_{i+j}^2}$项可以用前缀和预处理，$\sum\limits_{j=0}^{|T|-1}{b_{j}^2}$是定值，使用时可$O(1)$得到，剩下一项中的$\sum\limits_{j=0}^{|T|-1}{a_{i+j}b_j}$需要再处理一下以方便计算。

把$T$串翻转，反转后字符串对应的多项式$R=\sum\limits_{i=0}^{|T|-1}{r_ix^i},\quad r_i=b_{|T|-1-i}$。那么最后一项变成$p_i=\sum\limits_{j=0}^{|T|-1}{a_{i+j}r_{|T|-1-j}}=\sum\limits_{\substack{s+t=i+|T|-1\\ i\leq s}}{a_sr_t}$，符合卷积形式，可以使用FFT进行计算。

就这样计算出$C$后，遍历$C$的系数，为0处即为匹配上的位置。

(b) 存在通配符（可匹配任何字符）的字符串匹配

由于通配符一定能匹配，所以在通配符那一位的$c_i$一定是$0$，所以修改多项式$A$、$B$的系数定义为$\begin{cases}0&S_i为通配符\\\text{ascii}(S_i)&其他情况\end{cases}$，$c_i=\sum\limits_{j=0}^{|T|-1}{\left( a_{i+j}-b_{j} \right)^2a_{i+j}b_j}$

同样反转$T$串，这样$c_i=\sum\limits_{j=0}^{|T|-1}{(a^3)_{i+j}r_{|T|-1-j}}+\sum\limits_{j=0}^{|T|-1}{a_{i+j}(r^3)_{|T|-1-j}}-2\sum\limits_{j=0}^{|T|-1}{(a^2)_{i+j}(r^2)_{|T|-1-j}}$。显然，这是$3$个卷积，进行$3$次FFT即可解决问题。

6. Cache-Oblivious FFT算法

(a) Cache-Oblivious 矩阵转置算法（数据搬运复杂度$O(\frac{nm}{B})$）

将矩阵从中间分成四部分，递归地转置，大概是这样子：

def trans(&src[N][M], &dst[M][N], s_x, s_y, d_x, d_y, len_n, len_m):
    if n == 1 and m == 1:
        dst[d_x][d_y] = src[s_x][s_y]
        return
    
    mid_n = len_n // 2; mid_m = len_m // 2
    trans(src, dst, s_x        , s_y        , d_x        , d_y        , mid_n        , mid_m        ) //左上
    trans(src, dst, s_x        , s_y + mid_m, d_x + mid_m, d_y        , mid_n        , len_m - mid_m) //右上
    trans(src, dst, s_x + mid_n, s_y        , d_x        , d_y + mid_n, len_n - mid_n, mid_m        ) //左下
    trans(src, dst, s_x + mid_n, s_y + mid_m, d_x + mid_m, d_y + mid_n, len_n - mid_n, len_m - mid_m) //右下
   
	return

这样会尽量在缓存已有的矩阵部分中进行交换。

(b) 在Cache-Oblivious FFT中，能否将两个矩阵$X$、$Y$都设定成$N_1\times N_2$大小以避免转置

不可行。因为转置是为了让维度匹配而非单纯为了能计算，即使$N_1=N_2$也需要转置。

(c) 可否交换求和的顺序来减少转置次数

减少了转置开销，但有可能造成更多的Cache Miss，导致得不偿失。

Solution