Spindle: An Algorithmic Laboratory for Ordering Algorithms
Collaborators:
Gary Kumfert
Objective:
We have developed an algorithmic laboratory
for quickly prototyping promising algorithms and
experimenting with a collection of algorithmic variants for
several ordering problems.
Among these are the fill reduction problem:
Order the rows and columns of the coefficient matrix
to reduce the fill in sparse
Gaussian elimination (both complete and incomplete factorizations);
and the sequencing problem: Given a set of elements, and
pairs of elements that are related, order the elements such that
related elements are numbered consecutively.
Approach:
We employ object-oriented design techniques (OOD) to make the laboratory
flexible and easy to extend.
OOD manages complexity by means of decomposition and abstraction.
We decompose our software into two main types of objects:
structural objects corresponding to data structures, and algorithmic
objects corresponding to algorithms. This design decouples
data structures from algorithms, permitting a user to experiment with
different algorithms and different data structures,
and if necessary develop new algorithms and data structures.
We have implemented seven variants from the
family of minimum degree ordering algorithms
using this design paradigm.
Prior to our work,
there was no single code
that implemented all of these algorithms.
Our implementation makes it possible for us to change
ordering algorithms midstream while ordering a problem.
We have found this to be of benefit, since a hybrid algorithm
that employs the multiple minimum degree
(MMD) algorithm and switches at later stages to the
approximate minimum degree (AMD) algorithm can improve performance
for problems where either algorithm has poor performance.
We are currently considering the extension of our methods
to ordering unsymmetric problems.
This is joint work with Gary Kumfert, who defended
his Ph.D. thesis at Old Dominion University in 1999, and
who was also affiliated with ICASE. He has joined
the Center for Advanced Scientific Computing at Lawrence Livermore
National Lab as a computer scientist.
back to
Projects page