1.fast convolution

原理:用非耗时运算操作(如加法)替代耗时运算操作(如乘法)达到减少算法时间度的。

例子:通过复数乘法减少乘法时间复杂度

假设:

                      

将该乘法式表示为矩阵形式,其需要4个乘法和2个加法。将等式转变后变成3个乘法和5个加法





转变后的等式转变为矩阵形式,它的系数矩阵能够被分解为 2X3(C) , 3X3(H) 和 3X2(D) 的矩阵:



2. 多项式乘法与卷积

多项式 h(x) 与 g(x) 相乘,假设 h(x) 与 g(x) 分别为:

 





将多项式看做是以 ,,... 为基的空间向量,该多项式乘积就可以写为矩阵卷积形式



示例:存在两个多项式





h(x) 与 g(x) 对应的空间向量为:
h=[1,1,1,1]; g=[1,1,1];
h(x)*g(x) 得到的多项式的空间向量为上两向量的卷积:
1 2 3 3 2 1


3.Winograd Algorithms

对于一维卷积,当输出为m,卷积核长度为r时,需要乘法数量为:



将一维卷积扩展到二维,如果输出维mxn,卷积核维rxs,需要乘法数量为:



3.1 F(2X2,3X3)

直接计算一维卷积F(2X3)需要2x3=6次乘法。

输入:[ d0, d1, d2, d3], 卷积核为 [g0,g1,g2],没有padding,步长为1,写成矩阵形式为:



即:









这种计算方式需要2+3-1=4次乘法,4次加法,还有可以预计算的3次加法和2次乘法(卷积核默认为已知项)

将这种算法写成矩阵形式



表示点乘,对于F(2,3),以上矩阵分别为:











扩展为二维卷积的形式:



winograd算法的OpenGL实现 <https://blog.csdn.net/koibiki/article/details/83024514>