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

Typ
Examensarbete för masterexamen
Master's Thesis
Program
Computer science – algorithms, languages and logic (MPALG), MSc
Publicerad
2024
Författare
SCHIAVONE, LUKAS
TORPHAGE, FILIP
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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:
Beskrivning
Ämne/nyckelord
Algorithms , randomized algorithms , sketching , matrix multiplication , C++
Citation
Arkitekt (konstruktör)
Geografisk plats
Byggnad (typ)
Byggår
Modelltyp
Skala
Teknik / material
Index