Partitioning sparse matrices with eigenvectors of graphs. (English) Zbl 0711.65034

Pothen, Alex; Simon, Horst D.; Liou, Kang-Pu

SIAM J. Matrix Anal. Appl. 11, No. 3, 430-452 (1990).

An algebraic approach for computing vertex separators is described. It is shown that the eigenvalues of the Laplacian matrix can be used to get lower bounds on the size of separators. The authors give a heuristic algorithm for computing vertex separators from the second eigenvector of the Laplacian. The algorithm uses global information about the graph to determine separators. It is pointed out that it is sufficient to compute the eigenvector to low accuracy to get good separators for most problems.

Reviewer: R.P.Tewarson

MSC:

65F50	Computational methods for sparse matrices
65F05	Direct numerical methods for linear systems and matrix inversion
68R10	Graph theory (including graph drawing) in computer science
65F15	Numerical computation of eigenvalues and eigenvectors of matrices
05C50	Graphs and linear algebra (matrices, eigenvalues, etc.)

Keywords:

graph spectra; ordering algorithms; parallel ordering; sparse matrix; partitioning sparse matrices; graph partitioning; vertex separators; eigenvalues; Laplacian matrix; lower bounds

Software:

Harwell-Boeing sparse matrix collection