Heuristic Spectral Techniques for the Reduction of Bandwidth and Work-Bound of Sparse

In this paper we present heuristic techniques for the reduction of the bandwidth of a sparse matrix as well as for the reduction of the cost of the associated Cholesky factorization. Our algorithms are inspired by the Spectral Method of Barnard, Pothen and Simon [BPS95] which derives a permutation for reducing the envelope-size of a sparse matrix by computing the second eigenvector of the associated Laplacian matrix. Two main modifications of that method are proposed and tested. The first is based on the experimental observation that it is often preferable to perform only few iterations of an iterative method converging to the second eigenvector; the second is the introduction of a weighted Laplacian. These simple ideas allows us to obtain a family of spectral methods that have been carefully tested on a set of matrices whose size range from few hundred to one-million.