Putting one thing after another: The sequencing problem

Alex Pothen Computer Science Department, Old Dominion University, Norfolk, VA and ICASE, NASA Langley Research Center, Hampton, VA USA

We consider the problem of ordering the elements of a set such that closely related elements are placed next to each other. This sequencing problem has many interesting applications: sequencing genes in computational biology, reordering data accesses of irregular computations to reduce cache misses, computing incomplete factor preconditioners in iterative linear equation solvers, and solving systems of equations in structural analysis by skyline methods. We will discuss mathematical formulations of the sequencing problem in these applications, and then describe the algorithmic progress that has been made in the past few years. We show that problems whose computational graphs have good separators possess good solutions to the sequencing problem. Combinatorial algorithms of two different flavors have been developed: algorithms with good performance bounds that are unfortunately not practical, and simpler algorithms that perform well in practice but lacking bounds on the quality of the orderings. We will also discuss an algebraic algorithm with good performance bounds that is more robust than the combinatorial approaches when the data is contaminated with errors in the biological applications.

back to seminar homepage