We investigate several geometric methods for dividing an irregular mesh into pieces of roughly equal size with few interconnecting edges. All these methods are based on cutting a mesh with a line (in two dimensions) or a hyperplane (in any dimension).

Line cuts have often been used in practice, but their quality varies widely. Until now, no theory has existed to predict the effectiveness of any line-cut algorithm. We give rigorous (and tight) bounds on the quality of line cuts for meshes of bounded aspect ratio in terms of a parameter we call that measures the nonuniformity of the mesh. We also give an upper bound on the quality of an exact 50:50 line cut. This is the first proof of a cut size guarantee for any exact bisection induced by a single geometric cut.

We use these bounds to design simple and efficient algorithms that guarantee to find good line cuts. These algorithms are implemented using MPI in Cray parallel machines. The result shows the improvement over the traditional approaches.

This is joint work with Guangye Li, Shanghua Teng and John Gilbert.

Back to Workshop Schedule

1996-1997 Mathematics in High Performance Computing