Unstructured Graph Partitioning and Sparse Matrix Ordering System Version 2 . 0
Unstructured Graph Partitioning and Sparse Matrix Ordering System Version 2 . 0
复制标题
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
G. Karypis;Vipin Kumar
中科院分区：
文献类型：
--
作者：
G. Karypis;Vipin Kumar
图划分在科学计算、VLSI设计、任务调度等领域有着广泛的应用。问题是将图的顶点划分为p个大致相等的部分，使得连接不同部分的顶点的边数最小化。例如，在并行计算机上通过迭代方法求解稀疏线性方程组Ax=b就会产生图划分问题。这些方法每次迭代的关键步骤是稀疏矩阵和(稠密)向量的相乘。对对应于矩阵A的图进行划分，显著减少了该步骤[25]所需的通信量。如果使用并行直接方法来求解稀疏方程组，则可以使用图划分算法来计算在因式分解阶段导致高并发性的填充缩减排序[25，10]。在并行直接方法中几乎完全使用的多重最小次数排序不适合于并行直接方法，因为它在并行因式分解阶段提供的并发性很小。METIS是一组实现[22，23]中描述的各种算法的程序。与其他类似的程序包相比，METIS的优势如下：
Graph partitioning has extensive applications in many areas, including scientific computing, VLSI design, and task scheduling. The problem is to partition the vertices of a graph in p roughly equal parts, such that the number of edges connecting vertices in different parts is minimized. For example, the solution of a sparse system of linear equations Ax = b via iterative methods on a parallel computer gives rise to a graph partitioning problem. A key step in each iteration of these methods is the multiplication of a sparse matrix and a (dense) vector. Partitioning the graph corresponding to the matrix A, significantly reduces the amount of communication required by this step [25]. If parallel direct methods are used to solve a sparse system of equations, then a graph partitioning algorithm can be used to compute a fill reducing ordering that lead to high degree of concurrency in the factorization phase [25, 10]. The multiple minimum degree ordering used almost exclusively in serial direct methods is not suitable for parallel direct methods, as it provides very little concurrency in the parallel factorization phase. METIS is a set of programs that implement the various algorithms described in [22, 23]. The advantages of METIS compared to other similar packages are the following: