A parallel preconditioner for octree meshes
John R. Gilbert, Vikram Aggarwal · 2008
Fully adaptive octree grids are a promising development in the solution of fluid flow problems. While fully adaptive grids make it easier to discretize the domain, solving the linear system is harder, due to the linear system being unsymmetric. Researchers would find it beneficial to solve large systems of equations with such grids, to simulate phenomena that occur at very fine grid spacing. In this work, we develop an octree grid generator which is meant to be a general purpose prototyping framework for researchers interested in octree grids. Using the grid generator, we analyze the structure of fully-adaptive octree grids to identify their salient properties. We evaluate various methods of solving linear systems arising from these grids and find iterative linear solvers like BiCGSTAB to be the most promising. We demonstrate that the performance of iterative solvers is improved considerably by the use of no-fill incomplete factors. We demonstrate that for large octree grids, the preconditioner forms the dominant computation that limits the performance of iterative linear systems on parallel machines. To attempt to speed up the performance of the preconditioner, we exploit the graph structure of the octree grids to develop a novel coloring. This coloring leads to an upper bound on the chromatic number of octree grids for the Poisson problem. Using this coloring, we develop a triangular solver that shows good performance on parallel computers. We demonstrate the performance of the triangular solver as a preconditioner for the BiCGSTAB iteration, which greatly improves the performance of the linear system for these grids.