# On Implementing a Two-Step Interior Point Method for Solving Linear Programs
## 3 Experimental Evaluation
### Experiments on GPU  
A study by [PERSON] et al. (2018) investigated the use of GPU-accelerated linear solvers for optimizing large-scale power grid problems. Motivated by their study, we evaluate the performance of the algorithms on massively parallel hardware (GPU with tensor cores) using library routines to perform factoring.  
We utilized the Pytorch library to develop a GPU-enabled version of our program. The library assumes that all tensors are located on the same device. During our experiments, we utilized the NVIDIA V100 Volta (on the GRAHAM Compute Canada cluster), which has a maximum size limitation due to its 16 GB HBM2 memory. This card features tensor cores that perform certain tensor operations very efficiently in hardware. GPU arithmetic is typically conducted in low precision, ranging from 8 to 32 bits which account for the speed. Unfortunately, the algorithms failed to converge to an optimal solution when we employed low-precision arithmetic on V100. As a result, we opted to use double precision at 64 bits, even though this substantially increased the run time.  
To utilize GPU acceleration, we convert all vectors and matrices into tensors, leveraging the PyTorch library instead of Numpy for computations. In contrast, when running on a CPU, we represent these structures as regular vectors and matrices. By performing essential operations like matrix multiplication, inverse calculation and step size computation in tensor mode. This approach enhances the efficiency of calculations and enables faster reaching the optimal point.  
The computationally expensive steps in the algorithm proposed here (as in any IPM) are (i) the determination of \(\alpha\) and (ii) the computation of the inverse of the Jacobian to determine the step direction. The first expensive step has quadratic complexity (\(O((n+m)^{2})\) when implemented naturally). The second step is computationally more costly \(O((n+m)^{3})\). In the approach here, gains are realized asymptotically in the second step. Therefore, we focus on the time the GPU takes to perform matrix inversions. The raw data is shown in Appendix C. The second and third columns are the iterations needed by the classical and the algorithm proposed here. The last two columns in the table are the times (in seconds) needed by the GPU to perform the matrix inversions.  
Table 14 presents the results for Classical Algorithm and Algorithm 1 on GPU. We report the number of iterations and GPU times for 41 test problems. Note that, Classical algorithm could not reach the optimal solution for 5 test problems and Algorithm 1 could not find the optimal solution for 1 test problem based on the stopping conditions. We remove the results for these 6 test problems and calculate the relative reduction and speed-up. Figure 5 presents the relative reduction and speed-up for 35 test problems. Moreover, we denote the average of the number of iterations and GPU time for these 35 test problems in Table 2. Based on this Table, we can conclude that the new proposed method reduced the number of iterations and GPU by 39% and 30% respectively. Moreover, the standard deviation for the number of iterations indicates that Algorithm 1 has the lowest variability at 60.19.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Methods** & **Aver. Iter.** & **Aver. CPU (s)** & **Std-Iter.** \\ \hline Classical Algorithm & 97.82 & 166.71 & 70.96 \\ \hline Algorithm 1 & **71.34** & 136.29 & **55.64** \\ \hline Algorithm 2 & 72.52 & **135.46** & 57.55 \\ \hline \hline \end{tabular}  
* **Note:** Bold numbers indicate the lowest values in each column.  
\end{table}
Table 1: The average number of iterations, CPU time (s) and standard deviation.