TITLE:
Combinatorial Problems in High-Performance Computing

SPEAKER:

Rob Bisseling
Department of Mathematics
Utrecht University
http://www.math.uu.nl/people/bisseling

ABSTRACT:

This talk presents a survey of combinatorial problems
encountered in scientific computations on today's
high-performance architectures, such as parallel computers
with many processors and several cores on each processor,
and with sophisticated memory hierarchies and multiple levels of cache.
For parallelism, the most important problem is to partition
sparse matrices, graphs, or hypergraphs into nearly equal-sized
parts while trying to reduce inter-processor communication.
For better cache performance, the problem is to
reorder sparse matrices by suitable row and column permutations.
Common approaches to such problems involve multilevel
methods based on coarsening and uncoarsening (hyper)graphs,
matching of similar vertices, searching for good separator sets
and good splittings, and two-dimensional matrix splitting methods
such as incorporated in the software package Mondriaan.
We will discuss new algorithms included in version 3.0
of Mondriaan, to be released Spring 2010.

BIO:

Rob Bisseling is a professor in scientific computing
at the Mathematics Institute of Utrecht University
and leader of the Master's programme in scientific computing
in Utrecht. He is author of the book, "Parallel Scientific Computation:
A Structured Approach using BSP and MPI", Oxford University Press,
March 2004.