NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
Partitioning sparse matrices with eigenvectors of graphsThe 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.
Document ID
19950028508
Acquisition Source
Legacy CDMS
Document Type
Reprint (Version printed in journal)
External Source(s)
Authors
Pothen, Alex
(Pennsylvania State Univ. Univ. Park, PA, United States)
Simon, Horst D.
(NASA Ames Research Center Moffett Field, CA, United States)
Liou, Kang-Pu
(Pennsylvania State Univ. Univ. Park, PA, United States)
Date Acquired
August 16, 2013
Publication Date
July 1, 1990
Publication Information
Publication: SIAM Journal on Matrix Analysis and Applications
Volume: 11
Issue: 3
ISSN: 0036-1437
Subject Category
Computer Programming And Software
Accession Number
95A60107
Funding Number(s)
CONTRACT_GRANT: NAS2-12961
CONTRACT_GRANT: CCR-8705110
CONTRACT_GRANT: CCR-8701723
CONTRACT_GRANT: AFOSR-88-0161
Distribution Limits
Public
Copyright
Other

Available Downloads

There are no available downloads for this record.
No Preview Available