## Abstract

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.

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.

Originalsprog | Engelsk |
---|

Forlag | IT-Universitetet i København |
---|---|

Antal sider | 131 |

ISBN (Trykt) | 978-87-7949-016-1 |

Status | Udgivet - 2018 |

Navn | ITU-DS |
---|---|

Nummer | 149 |

ISSN | 1602-3536 |