NHSE Software Catalog

CHACO

version

2.0

title_line

software for partitioning and ordering graphs

author

Bruce Hendrickson (bahendr@cs.sandia.gov)
Rob Leland (leland@cs.sandia.gov)

abstract

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.

contact

Bruce Hendrickson (bah@cs.sandia.gov)

keywords

data partitioning; unstructured grid