Self-Improving Sparse Matrix Partitioning and Bulk-Synchronous Pseudo-Streaming

Abstract

One of the backbone operations in numerical mathematics is multiplying a sparse matrix with a vector. In computations involving very large linear systems, the sparse matrix-vector multiplication (SpMV) can be sped up tremendously by performing it on a parallel computer. Effective parallelization of a SpMV requires an efficient distribution of the matrix over processing elements. To this end hypergraph models associated to the matrix are partitioned while optimizing against an appropriate metric. In the first part of this thesis a new approach to this partitioning problem is presented that attempts to minimize the cumulative running time of a linear solver involving the matrix, and the partitioning algorithm.

In the second part, general matrix algorithms are considered that target many-core coprocessors. These specialized chips are a recent development in parallel hardware, and have proven to be very energy efficient. We extend the bulk-synchronous parallel model so that it is possible to develop general algorithms that target this specific class of parallel computers. We also discuss a number of examples of such algorithms.