Скачать или смотреть Mondriaan sparse matrix distribution

This video presents a recursive algorithm for distributing a sparse matrix over the processors of a parallel computer. The algorithm minimizes the communication volume while balancing the computation within a prescribed maximum allowed imbalance. The algorithm is based on repeated splits of a set of nonzeros into two parts, either by rows or by columns, and taking the best of the two directions, with the lowest communication volume.

Each split of the algorithm is formulated as a hypergraph bipartitioning problem, where a hypergraph is a generalization of a graph. The partitioning is done within a multilevel framework, where the problem is first made smaller by coarsening, and after an initial partitioning, the solution is uncoarsened and further refined.

This video corresponds to Section 4.5 of the book Parallel Scientific Computation: A Structured Approach Using BSP, Second Edition, by Rob H. Bisseling, Oxford University Press, 2020.

An expanded set of slides, solutions to the homework questions, and software accompanying the book can all be found on my personal book page:
https://webspace.science.uu.nl/~bisse...