Winograd算法原理

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>

热门工具换一换

Winograd算法 原理