.png){kind=icon}
返回
A parallel algorithm for multilevel graph partitioning and sparse matrix ordering
.png){kind=icon}
PRE
AI
DOI：10.1006/jpdc.1997.1403.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this paper we present a parallel formulation of the multilevel graph partitioning and sparse matrix ordering algorithm. A key feature of our parallel formulation (that distinguishes it from other proposed parallel formulations of multilevel algorithms) is that it partitions the vertices of the graph into root p parts while distributing the overall adjacency matrix of the graph among all p processors. This mapping results in substantially smaller communication than one-dimensional distribution for graphs with relatively high degree, especially if the graph is randomly distributed among the processors. We also present a parallel algorithm for computing a minimal cover of a bipartite graph which is a key operation for obtaining a small vertex separator that is useful for computing the fill reducing ordering of sparse matrices. Our parallel algorithm achieves a speedup of up to 56 on 128 processors for moderate size problems, further reducing the already moderate serial run time of multilevel schemes. Furthermore, the quality of the produced partitions and orderings are comparable to those produced by the serial multilevel algorithm that has been shown to outperform both spectral partitioning and multiple minimum degree. (C) 1998 Academic Press.
Keyword:
parallel graph partitioning
multilevel partitioning methods
fill reducing ordering
numerical linear algebra
期刊
IF:
4
论文数:
3.8K
被引数:
4.8K
机构
暂无机构信息
引用论文
High-Density Autologous Chondrocyte Implantation as Treatment for Ankle Osteochondral Defects.png)
CARTILAGE
OAAI
CARTILAGEIF0
OAAI分享收藏
分享收藏分享收藏分享收藏 没有更多内容
没有更多内容