Colloquium Mathematics - Prof. dr. H.R. Bisseling

Title:

Optimal 2D sparse matrix partitioning with Mondriaan” (joint work with Daan Pelt and Timon Knigge)

Abstract:

The Mondriaan package for sparse matrix partitioning aims at distributing the data of a parallel sparse matrix-vector multiplication to reduce communication while keeping a good load balance. Mondriaan is based on heuristic multilevel algorithms that produce a good solution in a limited amount of time. One may ask, however, how far is the result from optimal?

We developed an exact branch-and-bound algorithm to answer this question for bipartitioning of small and medium-sized matrices, which can serve as a benchmark to judge the quality of partioners. We will present the algorithm and its implementation in the program MondriaanOpt, and recent improvements to solve larger problems.