Abstract:

 Mondriaan is a two-dimensional, multilevel, hypergraph-based package
 for the partitioning of a rectangular sparse matrix,
 to be used as a sequential preprocessing step for parallel sparse
 matrix-vector multiplication. In this talk, the Mondriaan approach
 (reminiscent of the paintings in primary colours by the Dutch painter
 Piet Mondriaan) will be explained and its performance will be compared
 with geometric partitioning. Furthermore, we show how the communication 
 load of the multiplication can be balanced among the processors
 by using improved heuristics for the vector partitioning or,
 in certain special cases, by using an optimal graph-based algorithm.
 This minimises the cost in the metric of the bulk synchronous parallel
 (BSP) model.

 BRIEF BIOGRAPHY:
 Rob Bisseling is an associate professor in computational
 science at the Mathematics Department of Utrecht University,
 the Netherlands. His main research field is parallel computing
 and his current research interests are sparse matrix computations,
 bioinformatics, and fast Fourier transforms.
 He has recently published a book, Parallel Scientific Computation:
 A Structured Approach using BSP and MPI, Oxford University Press, March 2004.