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:
1. we present new Monte Carlo data structures for sparse output-sensitive matrix multiplication
based on repeated predecessor queries that are used to find specific random linear combination
of vectors in sparse matrices,
2. we introduce new Atlantic City algorithms for sparse Boolean matrix multiplication derived
from a novel framework that exploits size estimators for sparse matrix products,
3. we design new Monte Carlo algorithms for fast sparse matrix multiplication that combine
several existing frameworks to provide improved bounds for sparse matrix multiplication,
4. 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.