CHACO-2.0

From: Bruce Hendrickson
Date: Fri, 8 Sep 95 12:53:54 MDT
Subject: Chaco-2.0: Graph Partitioning Software

ANNOUNCING CHACO-2.0
Software for Partitioning and Ordering Graphs

Many problems which arise in the course of scientific computing can be conveniently described in terms of graph partitioning. A prominent example is the problem of decomposing a large, unstructured grid across the processors of a parallel computer. Other applications include generating nested disection orderings for sparse matrix factorizations and devising efficient circuit layouts.

Version 1 of our graph partitioning code "Chaco" has been licensed to over 100 sites around the world. We are now releasing version 2.0 with greatly enhanced performance, ease of use and functionality. Chaco contains a variety of partitioning algorithms including spectral bisection, quadrisection and octasection, the inertial method, the Kernighan-Lin/Fiduccia-Mattheyses algorithm and multilevel partitioners. Advanced techniques that are new to version 2.0 include terminal propagation (a method for improving data locality adapted from the circuit community), the ability to map partitions intelligently to hypercube and mesh architectures, and easy access to the Fiedler vector to assist the development of new applications of spectral graph algorithms. This capability has already been used in applications ranging from gene sequencing to database design.

A user's guide and papers describing the algorithms are available by anonymous ftp to cs.sandia.gov in the directory pub/tech_reports/bahendr. Academic user's can obtain the code at no charge under a research license agreement and it may also be licensed for commercial application. Interested parties should contact the first author at the address given below.

Bruce Hendrickson (bah@cs.sandia.gov)
Rob Leland (leland@cs.sandia.gov)
Sandia National Laboratories
Albuquerque, NM 87185