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.
Return to Bruce's home page