FAST NESTED DISSECTION FOR FINITE-ELEMENT MESHES

We present a randomized O(nloglogn) time algorithm for constructing a recursive separator decomposition for well-shaped meshes in two and th ree dimensions. Our algorithm takes O(nloglogn) time while previous al gorithms require Theta(nlogn) time. It uses techniques from probabilit y theory computational geometry, and graph theory. The new algorithm h as an application in the solution of sparse linear systems that arise in finite element calculations. In particular, it can be used to desig n O(nloglogn) time algorithms for finding a provably good nested-disse ction ordering for 3D finite element systems. It can also be used to i mprove the construction of 3D point location structures, which are use ful in hierarchical methods such as the multigrid and multilevel domai n decompositions.