Skip to ContentSkip to Navigation
Research Bernoulli Institute Calendar

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

When:Mo 02-07-2018 14:30 - 15:00
Where:5161.0041B (Bernoulliborg)


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


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.