Center for Computing Research (CCR)

Center for Computing Research


Sparse Matrix Reorderings

The number of numerical operations required to factor a sparse matrix depends critically on the ordering of the rows and columns. For Cholesky factorization, it is possible to reorder the matrix at will without causing numerical instability. I have worked on two reordering problems. With Ed Rothberg I have looked at the general problem of minimizing the fill in the matrix. We have used a nested dissection approach building upon my work in Graph Partitioning. We obtain orderings much superior to those produced by minimum degree algorithms on a range of 2D, 3D and linear programming matrices. I have also worked with Erik Boman on multilevel algorithms for producing small envelope orderings. These orderings are quite popular in commercial codes since they require simpler data structures with less indirect addressing.


  • Improving the Runtime and Quality of Nested Dissection Ordering, Bruce Hendrickson and Ed Rothberg. SIAM J. Sci. Comput. 20(2):468-489, 1998.

Paper, Abstract

  • Sparse Matrix Ordering Methods for Interior Point Linear Programming, Ed Rothberg and Bruce Hendrickson. INFORMS J. Comput. 10(1):107-113, 1998.

Paper, Abstract

  • Effective Sparse Matrix Ordering: Just Around the BEND, Bruce Hendrickson and Ed Rothberg. In Proc. Eighth SIAM Conf. Parallel Processing for Scientific Computing.

Paper, Abstract

  • A Multilevel Algorithm for Reducing the Envelope of Sparse Matrices, Erik G. Boman and Bruce Hendrickson, Tech Report SCCM-96-14, Stanford University

Paper, Abstract

Contact: Collis, Samuel Scott,
SAND2015-2641 S