WinoGrad

FFT
- 两个序列的乘法通过FFT可以从原始O(n^2)复杂度变成O(nlogn)
- 算法性能完全取决于傅立叶变换的性能以及相应卷积参数

WinoGrad
- 通过将卷积中的乘法使用加法来替换，并把一部分替换出来的加法放到 weight 的提前处理中，达到减少卷积运算中乘法的计算总量
- startup：F(2,3)
  - 对一维tensor $d=[d_0,d_1,d_2,d_3]$和kernel size为3的滑动filter $g=[g_0,g_1,g_3]$
  - 计算展开：需要做6次乘法和4次加法
    $F(2,3) = \left( \begin{array}{cc} d_0, d_1, d_2 \\ d_1, d_2, d_3 \end{array} \right) \left(\begin{array}{cc} g_0\\ g_1\\ g_2 \end{array} \right)$
  - 更general的表达：需要做 mk次乘法和m\(k-1)次加法
    $F(m,k) = \left( \begin{array}{cc} x_0, x_1, ..., x_{k-1} \\ x_1, x_2, ..., x_k \\ ...\\ x_{m-1}, x_{m}, ..., x_{n+k-2} \end{array} \right) \left(\begin{array}{cc} g_0\\ g_1\\ ... \\ g_{k-1} \end{array} \right)$
  - 左边的矩阵存在很多重复的数值，推导：https://zhuanlan.zhihu.com/p/260109670，可以得到：
    $\left( \begin{array}{cc} d_0, d_1, d_2 \\ d_1, d_2, d_3 \end{array} \right) \left(\begin{array}{cc} g_0\\ g_1\\ g_2 \end{array} \right) = \left( \begin{array}{cc} n_1+n_2+n_3 \\ n_2-n_3-n_4 \end{array} \right)$

    * 其中：
        $$
        n_1 = (d_0-d_2)g_0 \\
        n_2 = (d_1+d_2)(g_0+g_1+g_2)/2\\
        n_3 = (d_2-d_1)(g_0-g_1+g_2)/2 \\
        n_4 = (d_1-d_3)g_2
        $$

        * g相关的计算可以在推理之前提前处理
        * 简化为4次乘法4次加法

    * 推广到general表达式：$Y=A^T[(Gg)\odot(B^Td)]$

        * G是卷积核变换矩阵，对g做pre-refine的
        * B是输入变换矩阵
        * $\odot$是点乘，就是对应位置的乘法
        * A是输出变换矩阵

    * 推广到2D的general表达式：$Y=A^T[(GgG^T)\odot(B^TdB)]A$

        * 2D的conv可以tile为2x3个1D filter，合并每个1D的F(2,3)以后2D filter又变成了一个F(2,3)
        * 所以乘法次数为4x4=16
        * 原始的im2col的实现，乘法次数为4x9=36

    * 工程实现

        * step0：winograd矩阵获取，https://github.com/andravin/wincnn
        * step1：得到G矩阵，进行卷积核变换
        * step2：得到B矩阵，进行输入变换
        * step3：计算tile矩阵M，$[(GgG^T)\odot(B^TdB)]$
        * step4：得到A矩阵，计算结果Y，$A^TMA$