Engineering an Efficient Implementation of Pagh’s Compressed Matrix Multiplication Algorithm
Ladda ner
Typ
Examensarbete för masterexamen
Master's Thesis
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++