ADI methods for the Poisson equation on locally refined othogonal composite grids

Michael Lambert

Center for Applied Scientific Computing LLNL, M.S. L-560 7000 East Ave. Livermore, CA 94550


Since the late 1950s, alternating direction implicit (ADI) methods have been used for modeling diffusive heat transfer and analogous physical processes. In most cases, ADI has been applied to problems with uniform orthogonal grids (UOGs), due to directional operator splitting. Most implementations are second order accurate spatially (as well as temporally when modelling time-dependent linear diffusion). In this regime, ADI has been shown to exhibit at least logarithmic scalability with number of unknowns, and to have good parallel scalability down to fairly small numbers of unknowns, using spatial domain decomposition. But since UOGs are incompatible with most ways of resolving multiple spatial scales, ADI has fallen to the wayside of less spatially structured discretizations on top of Krylov and multigrid iterative linear solvers. But UOGs are only a subset of the grids on which ADI can be defined. ADI discretizations and iterations can be defined for locally refined orthogonal composite grids (LROCGs) as well. This could significantly benefit many LROCG block-structured AMR simulations of diffusive processes. Conceptually, local refinement merely increases the complexity of the line-solves in ADI. In particular, a graph showing interdependence of unknowns along a particular direction is no longer simply connected. Such graphs take on a topology resembling vascular capillaries. On traversal of a coarse-fine boundary into the finer region, the coarser unknown is linked by a matrix coefficient to r^(d-1) finer unknowns, assuming a refinement ratio (r) that is the same in all directions of a d-dimensional space. However, the finer unknowns at the boundary are not linked by matrix coefficients to one another. Of course, spatial accuracy at the boundary is reduced to first order. For N "capillary" unknowns, a direct "capillary" solver necessary for LROCG ADI might take only O(N) FLOPs, but it requires a complex algorithm that transcends the simple tridiagonal solvers used in UOG ADI. For this reason initial studies of LROG ADI are using almost any iterative solvers for the capillaries. In particular, the Portable Extensible Toolkit for Scientific Computations (PETSc), is being investigated due to parallelizability. Overall parallelism of a block-structured AMR based on ADI should not be significantly degraded from UOG ADI once direct capillary solvers commensurate with spatial domain decomposition are implemented. Whether such direct solvers are actually necessary is to be determined. This talk will summarize progress in this area of AMR research.