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.