LANS Informal Seminar: Ilya Safro

Seminar Title: Multilevel algorithms for linear ordering problems
Speaker: Ilya Safro, MCS

Date/Time: 2008-04-30 15:00
Location: Building 221 Conference Room A261

Description:
Linear ordering problems such as the minimum /p/-sum problem (MpSP), the workbound reduction, the wavefront, the envelope size, etc., appear in many applications of large sparse matrix computation, VLSI design, biological applications, graph drawing, etc. For general graphs these problems are NP-hard. Still, many heuristic algorithms (e.g., Spectral Sequencing, Optimally Oriented Decomposition Tree, Multilevel based, Simulated Annealing, Genetic Hillclimbing, etc.) were developed in order to achieve near optimal solution. We present a general framework of linear time multilevel heuristic algorithms (MA) especially designed for linear ordering problems. We demonstrate how the building blocks of the general MA can be used in various ways to make it suitable for solving different functionals. Besides our results for the M1SP and M2SP, we show how the bandwidth of a graph can be approximated by a continuation approach in which a sequence of MpSP solvers are embedded with progressively larger /p/. In addition, we use the M2SP result as a first approximation for the workbound reduction problem, which is then improved by a postprocessing of local minimizations. The M2SP can in fact be used to roughly approximate other functionals.

The main objective of MA is to create a hierarchy of problems, each representing the original problem, but with fewer degrees of freedom. In the context of graphs it is the Laplacian matrix that represents the related set of equations. The main difference between our approach to most other MA is the coarsening scheme. While the previous approaches may be viewed as strict aggregation process, the AMG coarsening is a weighted aggregation: each node may be divided into fractions, and different fractions belong to different aggregates. This enables more freedom in solving the coarser levels and avoids making hardened local decisions, such as edge contractions, before accumulating the relevant global information. It turned out that this general coarsening is suitable for all the different functionals we have tested. The various algorithms thus differ in the disaggregation process which follows by projecting to a finer level the final arrangement obtained on a coarser level. This initial fine level arrangement is being further improved by a general postprocessing which is composed of different local reordering methods. We compared the results obtained by our MA with other algorithms and show an average improvement of about 30% for the bandwidth and workbound problems.