WGPP: Watson Graph Partitioning (and sparse matrix ordering) Package

Graph partitioning is an important problem with extensive application in scientific computing, optimization, VLSI design, task partitioning for parallel processing, etc. The Watson Graph Partitioning Package ({\em WGPP}) is a package of subroutines for partitioning graphs and computing fill-reducing orderings of sparse matrices for their direct factorization. The graph partitioning problem requires dividing the set of nodes of a weighted graph into $k$ disjoint subsets or partitions such that the sum of weights of nodes in each subset is nearly the same (within a user supplied tolerance) and the total weight of all the edges connecting nodes in different partitions is minimized. In the case of unweighted graphs, each node and edge is assumed to have a unit weight. Computing a fill-reducing ordering of a sparse matrix seeks to generate a permutation of the columns (or rows) of a sparse matrix that minimizes the storage and computation required for factoring the sparse matrix. The {\em WGPP} library contains a collection of fast and high quality routines for unstructured graph partitioning and for generating robust fill-reducing orderings for sparse matrices arising in different application domains.

By: Anshul Gupta

Published in: RC20453 in 1996


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .