This thesis presents a study of sparse matrix multiplication, a fundamental operation in fields such as machine learning, computational physics, and network
analysis. First, we present the mathematical background and common representations of sparse matrices and review several classical and modern algorithms for
their multiplication. We also describe the computational complexity and the typical application requirements that shape the criteria for algorithm selection.
The main contribution of this thesis is a systematic experimental analysis performed using the tool ALGator. We implemented several approaches to sparse
matrix multiplication in Java.
To ensure the representativeness of the results, we designed and created carefully
defined test suites and carried out measurements across three classes of cases:
small, medium, and large matrices, including edge cases. The analysis shows that
some algorithms are strongly dependent on the density and distribution of nonzero
elements, while for small matrices the overhead of the execution environment plays
a decisive role.
The thesis provides practical guidelines, reproducible experimental procedures,
and an open set of test suites that can serve as a basis for further research and
optimizations in sparse matrix multiplication.
|
