# An Adaptive Procedure for the Global Minimization of a Class of Polynomial Functions
## 5 Experimentation
### Tensor Factorization for the Matrix Product Complexity  
The theory of matrix multiplication is strictly related to tensor algebra. In particular, the concept of tensor rank plays an important role in the determination of the complexity of the product of matrices [16]. We consider here the case of square matrices. Given \(A,\,B\in\mathbb{R}^{n\times n}\), the elements of \(C=A\,B\) can be written in the form  
\[c_{r,s}=\mathbf{a}^{T}K_{r,s}\,\mathbf{b},\quad r,s=1,\ldots,n,\]  
where \(\mathbf{a}\) and \(\mathbf{b}\) are the vectors obtained by vectorizing columnwise \(A\) and rowwise \(B\), i.e.,  
\[\mathbf{a}^{T} =[a_{1,1},\ldots,a_{n,1},a_{1,2},\ldots,a_{n,2},\ldots,a_{1,n}, \ldots,a_{n,n}]\in\mathbb{R}^{n^{2}},\] \[\mathbf{b}^{T} =[b_{1,1},\ldots,b_{1,n},b_{2,1},\ldots,b_{2,n},\ldots,b_{n,1}, \ldots,b_{n,n}]\in\mathbb{R}^{n^{2}},\]  
and \(K_{r,s}\in\mathbb{R}^{n^{2}\times n^{2}}\) is expressed by the Kronecker product \(K_{r,s}=I_{n}\otimes H_{r,s}\) where the \(n\times n\) matrix \(H_{r,s}\) has elements \(h_{i,j}=\delta_{r,j}\delta_{s,j}\). The associated 3 rd order tensor \(T\in\mathbb{R}^{n^{2}\times n^{2}\times n^{2}}\) is the one whose slides are \(K_{r,s}\), i.e., the elements of \(T\) are \(I_{i,j,k}=(K_{r,s})_{i,j}\), with \(k=n(r-1)+s\). Most elements of \(T\) are null. A reduction of the representation is obtained when \(A\) is triangular. For example, in the case of an upper triangular matrix \(A\) of size \(n\), \(\mathbf{a}\) can be represented by the \(n(n+1)/2\) elements  
\[\mathbf{a}^{T}=[a_{1,1},a_{1,2},a_{2,2},\ldots,a_{1,n},\ldots,a_{n,n}],\]  
with a resulting reduction in the first dimension of the matrices \(K_{r,s}\). If \(B\) is a full matrix, the associated tensor has \(n^{2}\times n(n+1)/2\times n^{2}\) elements. A fact of fundamental relevance is that the complexity of the computation of the product \(A\,B\), i.e., the minimum number of nonscalar multiplications sufficient to compute the product, is equal to the tensor rank of \(T\). In the experimentation we consider problems of the form (9) for a given integer \(\rho\). If the minimum is equal to zero, then the tensor rank of \(T\) is lower than or equal to \(\rho\). The difficulty which characterizes these problems is due to the presence of large regions of near flatness of \(f\), leading to a slow convergence to local minima. The difficulty increases when the parameter \(\rho\) decreases. The dimension of the solution space is \(N=3n^{2}\rho\) when both \(A\) and \(B\) are full, and is \(N=(2n^{2}+n(n+1)/2)\rho\) when one of the matrix is triangular. In the tests we consider the following cases with matrices \(A\) and \(B\) of size \(n=3\) and \(\rho\) such that \(f^{*}=0\). Problems TF3\((\rho)\): \(A\) is a triangular matrix and \(B\) is a full matrix, with \(\rho=16,\,\,17,\,18\),  
Problems FF3\((\rho)\): \(A\) and \(B\) are full matrices, with \(\rho=24,\,\,25,\,26,\,27\). The results are shown in Table 4. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \(m\times n\times\mathbf{\ell}\) (\(\mathbf{h}\), \(\mathbf{\rho}\)) & \(N\) & **Indices** & NM & DE & SA & MS1 & MS2 & AD1 & AD2 \\ \hline \multirow{3}{*}{\(10\times 5\times 15\) (5, 3)} & \multirow{3}{*}{90} & _time_ & 244 & 268 & 217 & 36 & 58 & 17 & 19 \\  & & _lerr_ & 11.3 & 9.6 & 9.8 & 7.1 & 11.1 & 7.1 & 10.9 \\ \hline \multirow{3}{*}{\(10\times 5\times 15\) (5, 5)} & \multirow{3}{*}{150} & _time_ & 805 & 1024 & 580 & 111 & 182 & 32 & 40 \\  & & _lerr_ & 13.1 & 13.0 & 10.2 & 8.1 & 12.0 & 8.1 & 12.0 \\ \hline \multirow{3}{*}{\(10\times 20\times 30\) (8, 4)} & \multirow{3}{*}{240} & _time_ & 6898 & 5743 & 4993 & 195 & 364 & 92 & 109 \\  & & _err_ & 7.8 & 8.7 & 9.3 & 5.3 & 9.3 & 5.2 & 9.1 \\ \hline \multirow{3}{*}{\(10\times 20\times 30\) (5, 5)} & \multirow{3}{*}{300} & _time_ & 2050 & 9782 & 14548 & 223 & 334 & 82 & 92 \\  & & _lerr_ & 12.3 & 14.5 & 9.8 & 8.3 & 12.0 & 8.3 & 12.0 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Execution times and accuracies for nonnegative CANDECOMP/PARAFAC (CP) problems.