CSE Seminar
SPEAKER: Ilya Safro,
Argonne National Laboratory
TITLE:
Multilevel Algorithms for Linear Ordering Problems
DATE: Wednesday, April 23, 2008
TIME: 12:00 Noon
PLACE: 2240 DCL
1304 W. Springfield Ave., Urbana, IL
ABSTRACT
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.
Joint work with Dorit Ron and Achi Brandt.