# A Faster Algorithm for Reducing the Computational Complexity of Convolutional Neural Networks
## 3 Proposed Algorithm  
As we can see from Section 2.2, the Winograd algorithm incurs more additions. To avoid repeating the transform of W and X in Equation (16), we calculate the matrices U and V separately. This can reduce the number of additions incurred by this algorithm. The practical implementation of this algorithm is listed in Algorithm 1. The calculation of output M in Algorithm 1 is the main complexity of multiplication in the whole computation process. To reduce the computational complexity of output M, we can use the Strassen algorithm. Before using the Strassen algorithm, we need to reform the expression of M as follows. The output M in Algorithm 1 can be written as the equation  
\[\mathrm{M}_{\mathrm{r},\mathrm{p}}=\sum_{q=1}^{Q}\left(\mathrm{A}^{T}(\mathrm{ U}_{r,q}\bullet\mathrm{V}_{q,\mathrm{p}})\mathrm{A}\right), \tag{30}\]  
where \(\mathrm{U}_{r,q}\) and \(\mathrm{V}_{q,\mathrm{p}}\) are temporary matrices, and \(\mathrm{A}\) is the constant parameter matrix. To show the equation easily, we ignore matrix A. (Matrix A is not ignored in the actual implementation of the algorithm.) The output M can then be written as shown in Equation (31). \[\mathrm{M}_{\mathrm{r},\mathrm{p}}=\sum_{q=1}^{Q}\left(\mathrm{U}_{r,q}\bullet \mathrm{V}_{q,\mathrm{p}}\right) \tag{31}\]  
We denote three special matrices M, U and V. \(\mathrm{M}_{\mathrm{r},\mathrm{p}}\), \(\mathrm{U}_{r,q}\), and \(\mathrm{V}_{q,\mathrm{p}}\) are the elements of the matrices M, U and V, respectively, as shown in Equation (33). The output M can then be written as a multiplication of matrix U and matrix V.  
\[\mathrm{M}=\mathrm{U}\times\mathrm{V} \tag{32}\]  
\[\mathrm{M}=\left[ \begin{array}{ccc}\mathrm{M}_{1,1}&\cdots&\mathrm{M}_{ 1,\mathrm{P}}\\ \vdots&\ddots&\vdots\\ \mathrm{M}_{\mathrm{R},1}&\cdots&\mathrm{M}_{\mathrm{R},\mathrm{P}}\end{array}  \right]\mathrm{U}=\left[ \begin{array}{ccc}\mathrm{U}_{1,1}&\cdots&\mathrm{ U}_{1,\mathrm{Q}}\\ \vdots&\ddots&\vdots\\ \mathrm{U}_{\mathrm{R},1}&\cdots&\mathrm{U}_{\mathrm{R},\mathrm{Q}}\end{array}  \right]\mathrm{V}=\left[ \begin{array}{ccc}\mathrm{V}_{1,1}&\cdots&\mathrm{ V}_{1,\mathrm{P}}\\ \vdots&\ddots&\vdots\\ \mathrm{V}_{\mathrm{Q},1}&\cdots&\mathrm{V}_{\mathrm{Q},\mathrm{P}}\end{array}  \right] \tag{33}\]  
In this case, we can partition the matrices M, U and V into equal-sized block matrices, and then use the Strassen algorithm to reduce the number of multiplications between \(\mathrm{U}_{r,q}\) and \(\mathrm{V}_{q,\mathrm{p}}\). The multiplication in the Strassen algorithm is redefined as the element-wise multiplication of matrices \(\mathrm{U}_{r,q}\) and \(\mathrm{V}_{q,\mathrm{p}}\). We name this new combination as the Strassen-Winograd algorithm. ```
1 forr = 1 to the number of output maps
2 forq = 1 to the number of input maps
3U = GwG\({}^{\mathrm{T}}\)
4 end
5 end
6 forp = 1 to batch size
7 forq = 1 to the number of input maps
8 fork = 1 to the number of image tiles
9V = B\({}^{\mathrm{T}}\)xB
10 end
11 end
12 end
13 forp = 1 to batch size
14 forr = 1 to the number of output maps
15 forj = 1 to the number of image tiles
16M = zero;
17 forq = 1 to the number of input maps
18M = M + A\({}^{\mathrm{T}}\)(U\(\blacktriangleright\)V)A
19 end
20 end
21 end
22 end
```  
**Algorithm 1**Implementation of the Winograd algorithm. To compare theoretically the computational complexity of the conventional algorithm, Strassen algorithm, Winograd algorithm, and Strassen-Winograd algorithm, we list the complexity of multiplication and addition in Table 1. The output feature map size is set to 64 \(\times\) 64, and the kernel size is set to 3 \(\times\) 3. We can see from Table 1 that, although the algorithms cause more additions when the matrix size is small, the number of extra additions is less than the number of decreased multiplications. Moreover, multiplication usually costs more time than addition. Hence the three algorithms are all theoretically effective in reducing the computational complexity. Figure 2 shows a comparison of the computational complexity ratios.