A Whirlwind Tour of Sparse Matrix Orderings 
            for Direct Sparse Methods

              Dr. Cleve Ashcraft
              Boeing Phantom Works 


Sparse systems of linear equations arise in many important
application areas including structural analysis, fluid flow,
and optimization using interior point methods. One way to 
solve a linear system AX = B is directly, i.e., factor the 
matrix A into a product LU where L and U are lower and upper 
triangular matrices, and then solve the simpler systems LY = B 
and UX = Y.

When the matrix A is sparse, i.e., most of the entries are zero,
we hope that the L and U matrices will also be sparse. The more
sparse they are, the less storage they need and fewer operations 
are required to compute the factorization and solve the linear
systems. It is advantageous to to order the equations and unknowns 
so that L and U are as sparse as possible.

Unfortunately, this problem is NP-complete, so we must be satisfied
with heuristics. Research in this area requires many different tools 
from mathematics and computer science, including graph theory, 
numerical analysis, combinatorial optimization, algorithms and 
data structures, and software engineering.

We will survey more than thirty years of ordering algorithms, 
beginning with the profile methods of the 60's and 70's, moving to 
the minimum priority methods of the 80's, and onto the nested 
dissection and multisection methods of the 90's. We will conclude
with several open research problems.

--------------------