PARTITIONING SPARSE MATRICES WITH EIGENVECTORS OF GRAPHS
PARTITIONING SPARSE MATRICES WITH EIGENVECTORS OF GRAPHS
复制标题
DOI：
10.1137/0611030
复制
发表时间：
1990-07-01
影响因子：
1.5
通讯作者：
LIOU, KP
中科院分区：
文献类型：
--
作者：
POTHEN, A;SIMON, HD;LIOU, KP
计算图中的小顶点分离器的问题出现在计算稀疏对称矩阵的并行因式分解的良好排序的上下文中。本文提出了一种计算顶点分离器的代数方法。它是，示出的分离器的大小的下界可以得到的拉普拉斯矩阵的特征值与一个图。网格图的Laplacian特征向量可以由路图的特征向量的Kronecker积计算出来，这些特征向量可以用来计算网格图中的好分离子。设计了一种启发式算法来计算一般图中的顶点分隔符，该算法首先从Laplacian矩阵的特征向量计算图中的边分隔符，然后使用子图中的最大匹配来计算顶点分隔符。的质量上的分离器计算的谱算法的结果，这些分离器从其他算法计算分离器得到的比较。最后，所需的时间来计算拉普拉斯特征向量的报告，并被认为是准确的特征向量必须计算得到良好的分离器。频谱算法的优点是，它可以实现在一个中等大小的多处理器在一个简单的方式。
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.