Partitioning Sparse Matrices with Eigenvectors of Graphs

TLDR

Computing a small vertex separator is key for ordering sparse symmetric matrices for parallel factorization. The paper explores an algebraic method for computing vertex separators. The authors use Laplacian eigenvectors—computed via Kronecker products for grid graphs and directly for general graphs—to first find an edge separator, then apply a maximum‑matching subgraph step to obtain a vertex separator. The spectral algorithm yields separators whose sizes are bounded by Laplacian eigenvalues, performs competitively with existing methods, runs efficiently, and can be implemented straightforwardly on a medium‑size multiprocessor.

Abstract

The problem of computing a small vertex separator in a graph arises in the context of computing a good ordering for the parallel factorization of sparse, symmetric matrices. An algebraic approach for computing vertex separators is considered in this paper. It is, shown that lower bounds on separator sizes can be obtained in terms of the eigenvalues of the Laplacian matrix associated with a graph. The Laplacian eigenvectors of grid graphs can be computed from Kronecker products involving the eigenvectors of path graphs, and these eigenvectors can be used to compute good separators in grid graphs. A heuristic algorithm is designed to compute a vertex separator in a general graph by first computing an edge separator in the graph from an eigenvector of the Laplacian matrix, and then using a maximum matching in a subgraph to compute the vertex separator. Results on the quality of the separators computed by the spectral algorithm are presented, and these are compared with separators obtained from other algorithms for computing separators. Finally, the time required to compute the Laplacian eigenvector is reported, and the accuracy with which the eigenvector must be computed to obtain good separators is considered. The spectral algorithm has the advantage that it can be implemented on a medium-size multiprocessor in a straightforward manner.