Sparse Matrix Computations and their I/O Complexity

For many computational tasks, the performance bottleneck is caused by memory accesses instead of CPU time. To tackle this problem in a theoretical way, the I/O-model and the Parallel External Memory (PEM) model were introduced. The PEM model describes several parallel processors, each assigned to a private internal memory (cache) of limited capacity. Communication and the storage of input, output, and intermediate results is realised by a shared external memory (disk) which is organised in blocks. This thesis considers the parallel I/O complexity of several tasks that are based on sparse matrix computations over a semiring. We present upper and lower bounds for the multiplication of a sparse matrix with (i) several vectors, including bilinear forms, (ii) a dense matrix, (iii) another sparse matrix. The work is complemented by a consideration of the MapReduce framework in the PEM model.
Bei viele Berechnungsaufgaben wird die Berechnungsdauer maßgeblich durch Speicherzugriffe bestimmt. Um diese theoretisch zu erfassen wurden das I/O-Model und das Parallel External Memory Model (PEM) erdacht. Im PEM Model werden mehrere parallel Prozessoren modelliert, welche je an einen privaten Cache (Internspeicher) mit limitierter Kapazität angebunden sind. Zusätzlich steht ein Shared-Memory-Speicher (Externspeicher) für Eingabe, Ausgabe und Kommunikation zur Verfügung. In dieser Dissertation werden mehrere Aufgaben untersucht, die auf dünnbesetzten Matrizen in einem Semiring basieren. Es werden obere und untere Schranken für die I/O Komplexität der Multiplikation einer dünnbesetzten Matrix mit (i) mehreren Vektoren, (ii) einer dichten Matrix und (iii) einer weiteren dünnbesetzten Matrix gezeigt. Zusätzlich wird die Arbeit mit einer Untersuchung des MapReduce frameworks komplementiert.