# A Faster Algorithm for Reducing the Computational Complexity of Convolutional Neural Networks
## 2 Related Work
### Winograd Algorithm  
We denote an r-tap FIR filter with m outputs as \(F(m,r)\). The conventional algorithm for \(F(2,3)\) is shown in Equation (6), where \(d_{0}\), \(d_{1}\), \(d_{2}\) and \(d_{3}\) are the inputs of the filter, and \(h_{0}\), \(h_{1}\) and \(h_{2}\) are the parameters of the filter. As Equation (6) shows, it uses 6 multiplications and 4 additions to compute \(F(2,3)\). \[F(2,3)=\left[ \begin{array}{ccc}d_{0}&d_{1}&d_{2}\\ d_{1}&d_{2}&d_{3}\end{array} \right]\left[ \begin{array}{c}h_{0}\\ h_{1}\\ h_{2}\end{array} \right]=\left[ \begin{array}{c}d_{0}h_{0}+d_{1}h_{1}+d_{2}h_{2 }\\ d_{1}h_{0}+d_{2}h_{1}+d_{3}h_{2}\end{array} \right] \tag{6}\]  
If we use the minimal filtering algorithm [19] to compute \(F(m,r)\), it requires \((m+r-1)\) multiplications. The process of the algorithm for computing \(F(2,3)\) is shown in Equations (7)-(11). \[m_{1}=(d_{0}-d_{2})h_{0} \tag{7}\]  
\[m_{2}=(d_{1}+d_{2})\frac{1}{2}(h_{0}+h_{1}+h_{2}) \tag{8}\]  
\[m_{3}=(d_{2}-d_{1})\frac{1}{2}(h_{0}-h_{1}+h_{2}) \tag{9}\]  
\[m_{4}=(d_{1}-d_{3})h_{2} \tag{10}\]  
\[F(2,3)=\left[ \begin{array}{c}d_{0}h_{0}+d_{1}h_{1}+d_{2}h_{2}\\ d_{1}h_{0}+d_{2}h_{1}+d_{3}h_{2}\end{array} \right]=\left[ \begin{array}{c}m_ {1}+m_{2}+m_{3}\\ m_{2}-m_{3}-m_{4}\end{array} \right] \tag{11}\]  
The computation can be written in matrix form as Equation (12). \[F(2,3)=\left[ \begin{array}{ccc}1&1&1&0\\ 0&1&-1&-1\end{array} \right]\left(\left(\left[ \begin{array}{ccc}1&0&0\\ \frac{1}{2}&\frac{1}{2}&\frac{1}{2}\\ \frac{1}{2}&-\frac{1}{2}&\frac{1}{2}\\ 0&0&1\end{array} \right]\left[ \begin{array}{c}h_{0}\\ h_{1}\\ h_{2}\end{array} \right]\right)\bullet\left(\left[ \begin{array}{ccc}1&0&-1&0 \\ 0&1&1&0\\ 0&-1&1&0\\ 0&1&0&-1\end{array} \right]\left[ \begin{array}{c}d_{0}\\ d_{1}\\ d_{2}\\ d_{3}\end{array} \right]\right)\right) \tag{12}\]  
We substitute \(A\), \(G\) and \(B\) for the matrices in Equation (12). Equation (12) can then be rewritten as Equation (13). \[Y=A^{T}((Gh)\bullet(B^{T}d)), \tag{13}\]  
\[A=\left[ \begin{array}{ccc}1&0\\ 1&1\\ 1&-1\\ 0&-1\end{array} \right],G=\left[ \begin{array}{ccc}1&0&0\\ \frac{1}{2}&\frac{1}{2}&\frac{1}{2}\\ \frac{1}{2}&-\frac{1}{2}&\frac{1}{2}\\ 0&0&1\end{array} \right],B=\left[ \begin{array}{ccc}1&0&0&0\\ 0&1&-1&1\\ -1&1&1&0\\ 0&0&0&-1\end{array} \right] \tag{14}\]  
In Equation (13), \(\bullet\) indicates element-wise multiplication, and the superscript \(T\) indicates the transpose operator. \(A\), \(G\) and \(B\) are defined in Equation (14). We can see from Equation (7) to Equation (11) that the whole process needs 4 multiplications. However, it also needs 4 additions to transform data, 3 additions and 2 multiplications by a constant to transform the filter, and 4 additions to transform the final result. (To compare the complexity easily, we regard the multiplication by a constant as an addition.) The 2-dimensional filters F(m \(\times\) m, r \(\times\) r) can be generalized by the filter F(m, r) as Equation (15) [22]. \[\mathrm{Y}=\mathrm{A}^{\mathrm{T}}((\mathrm{G}\mathrm{h}\mathrm{G}^{\mathrm{ T}})\bullet(\mathrm{B}^{\mathrm{T}}\mathrm{d}\mathrm{B}))\mathrm{A} \tag{15}\]  
F(2 \(\times\) 2, 3 \(\times\) 3) needs 4 \(\times\) 4 = 16 multiplications, 32 additions to transform data, 28 additions to transform the filter, and 24 additions to transform the final result. The conventional algorithm needs 36 multiplications to calculate the result. This algorithm can reduce the number of multiplications from 36 to 16. F(2 \(\times\) 2, 3 \(\times\) 3) can be used to compute the convolutional layer with 3 \(\times\) 3 kernels. Each input feature map can be divided into smaller feature maps in order to use Equation (15). If we substitute U = GwG\({}^{\mathrm{T}}\) and V = B\({}^{\mathrm{T}}\)\(\times\) B, then Equation (3) can be rewritten as Equation (16). \[