[ Imager TR Home Page ]
[ Imager Home Page ]
[ UBC CS Home Page ]
Simulated
Annealing for
Profile and
Fill
Reduction of
Sparse
Matrices
Robert
R.
Lewis
Appeared in International Journal for Numerical Methods in Engineering
(Vol. 37, No. 6; pp. 905-926)
TR-93-49
ABSTRACT
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.