Technical Reports

The ICICS/CS Reading Room

UBC CS TR-93-49 Summary

Simulated Annealing for Profile and Fill Reduction of Sparse Matrices, March 21, 1993 Robert R. Lewis, 49 pages

Simulated annealing can minimize both profile and fill of sparse matrices. We applied these techniques to a number of sparse matrices from the Harwell-Boeing Sparse Matrix Collection. We were able to reduce profile typically to about 80% of that attained by conventional profile minimization techniques (and sometimes much lower), but fill reduction was less successful (85% at best). We present a new algorithm that significantly speeds up profile computation during the annealing process. Simulated annealing is, however, still much more time-consuming than conventional techniques and is therefore likely to be useful only in situations where the same sparse matrix is being used repeatedly.

If you have any questions or comments regarding this page please send mail to