Partitioning sparse matrices optimally or near-optimally
for the parallel iterative solution of sparse linear systems could potentially
save huge amounts of computation time, as iterative solvers are core
computation kernels in the area of HPC. The partitioning itself
can be costly however, and its cost may not be completely recovered
by the savings of the iterative solver.

In this talk I will present a method that balances the cost
of the partitioner with the savings of the solver,
starting with a simple 1D cyclic partitioning
that gradually improves itself over time and that runs itself in parallel.
The method is based on label propagation steps extended to hypergraphs, possibly mixed
with 2D steps based on medium-grain partitioning.

Furthermore, I will present some of the latest results for the expanding data base
of optimally bipartitioned matrices using the MondriaanOpt program
that implements an exact branch-and-bound algorithm.
The database currently contains optimal bipartitionings for over 200 matrices
from the University of Florida collection.

The research on self-improving partitioning is joint work with Jan-Willem Buurlage.
The work on exact partitioning is joint with Daan Pelt and Timon Knigge.
The data base can be found at
http://www.staff.science.uu.nl/~bisse101/Mondriaan/Opt/