Engineering an Efficient Implementation of Pagh’s Compressed Matrix Multiplication Algorithm

Abstract

Matrix multiplication is a foundational operation in many fields of science such as machine learning, scientific computing and statistics. Simultaneously, matrix multiplication is an expensive operation to perform, with the mathematical definition requiring O(n3) arithmetic operations to compute all the elements in a product of two matrices. In this thesis we implement the algorithm for approximating matrix multiplication described in Rasmus Pagh’s paper Compressed Matrix Multiplication (2013) in C++. The performance of the implementation of the algorithm is evaluated for different sizes of input matrices as well as varying input parameters and using different classes of hash functions. The results show that due to having a lower asymptotic complexity than traditional matrix multiplication methods, our implementation will regardless of the input parameters eventually be faster. The input parameters used will determine at which point this will occur. We also measure the degree of parallelism available in Pagh’s algorithm in this thesis and present the results in graphs to show the performance gained from increasing the number of utilized cores. In addition, we have applied our implementation to the problem of calculating sample covariance matrices and studied which values of the input parameters are suitable for this problem. The accuracy of the approximations of Pagh’s algorithm for computing sample covariance matrices are measured for varying parameters to determine this. Keywords: