HPC-Netlib

High Performance Math Software

CHACO

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.

DateOfInformation

Thr Oct 15 16:11:21 1998

Domain

Numerical Programs and Routines!Graph and mesh partitioning

Keyword

data partitioning; unstructured grid

Name

CHACO

TargetEnvironment

Not Available

TitleLine

software for partitioning and ordering graphs

Version

1.0

Webpage

http://www.cs.sandia.gov/HPCCIT/chaco.html

ContactIs

Bruce Hendrickson