Tech Report CS-00-06
Parallel Adaptive Unstructured Computation
Jose Gabriel Castanos
Adaptive computation offers the potential to provide large storage and computational savings on problems with dissimilar scales by focusing the available computational resources on the regions where the solution changes rapidly. Many static problems have regions of high physical activity embedded in large domains in which the solution is smooth. In transient problems, the regions of interest can appear or vanish, and modify their size, shape or location, as occurs in the study of turbulence in fluid flows. In all cases, it is necessary to ``adapt'' the mesh to follow the physical anomalies so that regions of high gradients are not under-resolved while maintaining a coarser mesh everywhere else. Unfortunately, adaptivity significantly increases the complexity of algorithms and software.
In this talk we describe the problems that arise when adaptive schemes are used in a parallel computing environment. We address the difficulties of designing parallel adaptation methods by introducing a new parallel mesh refinement algorithm based on Rivara's bisection algorithm, for triangular and tetrahedral meshes. We have shown that this algorithm generates the same refined meshes in the serial and parallel cases. Because adaptive methods produce imbalances in the work assigned to processors they provide an excellent context for the study of dynamic load balancing schemes on distributed memory parallel computers. We present a new parallel graph partitioning algorithm that has its roots in multilevel algorithms. Compared with other partitioning heuristics, our method greatly reduces the movement of data between processors as a result of small changes in the mesh, by amounts close to those predicted by analysis. We have also designed a data migration procedure to rebalance the work between processors.
To evaluate and test these ideas we have developed and implemented a parallel adaptive system, called PARED, for the solution of PDEs by the finite element method. PARED is an object system that executes in distributed memory machines such as the IBM RS6000/SP and networks of workstations. PARED supports the creation of dynamic distributed data structures. Our system also provides a communications library built on top of MPI that allows for an efficient exchange of objects between processors.