Sparse Matrix Multiplication Kernels

The fast progress of information technology in the present years led to a substantial growth in terms of the volume of data to be analyzed and the size of the problems needed to be solved. Since the Eighties, the formulation of out-of-memory models of computation was motivated by the intractability of the problems by the prevailing architectures. This trend is expected to grow even
further. Therefore, algorithm designers have to provide solutions specifically tailored for big data processing.

The design of algorithms often relies on kernels, basic yet essential primitives that may be invoked several times by an algorithm during its execution. It is therefore fundamental to rely on theoretically efficient, highly optimized and high performance kernels.

In the field of linear algebra, the most common primitives concern the manipulation of data vectors, such as matrix-matrix multiplication or matrix-vector multiplication. Matrix multiplication has countless applications, from graph algorithms, machine learning, to computer graphics and image processing. Its prominence is validated by the almost half century old research field that aims at providing optimal algorithms for matrix multiplication and trying to answer a long-standing conjecture.

This dissertation aims at providing efficient kernels for sparse matrix multiplication. The main contributions are the following:
(i) we present new Monte Carlo data structures for sparse outputsensitive matrix multiplication based on repeated predecessor queries that are used to find specific random linear combination of vectors in sparse matrices,
(ii) we introduce new Atlantic City algorithms for sparse Boolean matrix multiplication derived from a novel framework that exploits size estimators for sparse matrix products,
(iii) we design new Monte Carlo algorithms for fast sparse matrix multiplication that combine several existing frameworks to provide improved bounds for sparse matrix multiplication,
(iv) we present new deterministic data structures for permutation matrices in the Parallel External Memory model that translate into efficient and experimentally evaluated algorithms for permuting in concurrent out-of-memory models.

The result is a collection of randomized and deterministic algorithms for sparse matrix computations that are meant to provide improvements over the state of the art in time or memory efficiency.