Newton-Krylov-FAC Methods: Infrastructure, Algorithms, and Applications

Michael Pernice

Computer and Computational Sciences Division
Los Alamos National Laboratory
P.O. Box 1663, MS B256
Los Alamos, NM 87545

Richard Hornung

Center for Applied Scientific Computing
Lawrence Livermore National Laboratory
P.O. Box 808, MS L561
Livermore, CA 94551


Problems in computational science and engineering are often nonlinear in nature. Moreover, many such problems have solutions that include spatially localized features, such as boundary layers or sharp fronts, that require very fine grids to resolve. Resolving these features with a globally fine grid is often impractical or prohibitively expensive, especially in three dimensions. Gridding approaches based on adaptive mesh refinement (AMR) attempt to resolve these features by using a fine grid only where it is necessary. Numerous AMR algorithms for hyperbolic problems with explicit timestepping and some classes of linear elliptic problems have been developed. However, much less attention has been given to strategies for solving systems of nonlinear equations discretized on locally refined grids.

Recent efforts have demonstrated the effectiveness of Newton-Krylov methods combined with multigrid preconditioners on a broad range of applications. This suggests that hierarchical methods, such as the Fast Adaptive Composite grid (FAC) method of McCormick and Thomas, should provide effective preconditioning for problems discretized on locally refined grids. The resulting Newton-Krylov-FAC method has been implemented on structured AMR grids. The software infrastructure combines nonlinear solvers from KINSOL or PETSc with the SAMRAI framework, and includes capabilities for implicit timestepping. Convergence rates that are independent of the number of refinement levels have been obtained for simple Poisson-like problems. Additional efforts to employ this infrastructure in a variety of applications are underway.