Parallel computation with adaptive methods for elliptic and hyperbolic systems

We consider the solution of two-dimensional vector systems of elliptic and hyperbolic partial differential equations on a shared memory parallel computer. For elliptic problems, the spatial domain is discretized using a finite quadtree mesh generation procedure and the differential system is discretized by a finite element-Galerkin technique with a piecewise linear polynomial basis. Resulting linear algebraic systems are solved using the conjugate gradient technique with element-by-element and symmetric successive over-relaxation preconditioners. Stiffness matrix assembly and linear system solutions are processed in parallel with computations schedules on noncontiguous quadrants of the tree in order to minimize process synchronization. Determining noncontiguous regions by coloring the regular finite quadtree structure is far simpler than coloring elements of the unstructured mesh that the finite quadtree procedure generates. We describe linear-time complexity coloring procedures that use six and eight colors. For hyperbolic problems, the rectangular spatial domain is discretized into a grid of rectangular cells, and the differential system is discretized by an explicit finite difference technique. Recursive local refinement of the time steps and spatial cells of a coarse base mesh is performed in regions where a refinement indicator exceeds a prescribed tolerance. Data management involves the use of a tree of grids with finer grids regarded as offspring of coarser ones. Computational procedures that sequentially traverse the tree structure while processing solutions on each grid in parallel and that process solutions at the same tree level in parallel have been developed. Computational results using the sequential tree traversal scheme are presented and compared with results using a non-adaptive strategy. Heuristic processor load balancing techniques are suggested for the parallel tree traversal procedure.