## Algorithms and Software for Partitioning Meshes

* A decomposition of a finite element part prior to a parallel calculation. The different colored regions will be assigned to different processors. For high performance, the regions must be identically sized, and the interface between them (gray color) must be small.*

Related Papers-This is a page with some related papers to download.

Slide Show Page-This is a page with slide shows of mesh decompositions on different objects.

More Pretty Pictures-More pictures of decompositions.

Before a calculation can be performed on a parallel computer, it must
first be decomposed into tasks which are assigned to different processors.
Efficient use of the machine requires that each processor have about the
same amount of work to do and that the quantity of interprocessor
communication is kept small. Finding an optimal decomposition is
provably hard, but due to its practical importance, a great deal
of effort has been devoted to developing heuristics for this problem.

Researchers at Sandia Labs have developed a variety of innovative
algorithms for this decomposition problem and implemented them in
a software package called Chaco. This code is being used at most
of the major parallel computing centers in the country to simplify
the development of parallel applications, and to ensure that optimal
performance is obtained. Chaco has contributed to a wide variety
of computational studies including investigation of the molecular
structure of liquid crystals, evaluating the design of a chemical
vapor deposition reactor and modeling automobile collisions.

The algorithms developed for Chaco have also been successfully
applied to a number of problems which have nothing to do with
parallel computing. These include the determination of genomic
sequences (a critical part of the Human Genome Project), the
design of space-efficient circuit placements, organization of
databases for efficient retrieval, and ordering
of sparse matrices for efficient factorization.

*Last Updated: February 12, 1997 WWW Administration (www-admin@www.cs.sandia.gov) Bruce A. Hendrickson (bahendr@cs.sandia.gov)
*

*Page 2*