Multigrid Preconditioning of Newton-Krylov Methods

D.A. Knoll

D.A. Knoll and W.J. Rider M.S. K717 Los Alamos National Laboratory Los Alamos, New Mexico 87545


Abstract

We study the application of classic V-cycle multigrid algorithms with standard smothers as a means of preconditioning matrix-free Newton-Krylov methods. Newton-Krylov methods have been applied to a variety of problems using a "mesh-sequencing" algorithm where the solution on a coarse grid is interpolated up and used as an initial guess on a finner grid. This greatly increases the radius of convergence of Newton's method as well as accelerating the nonlinear convergence on a given grid (i.e. reducing the number of required Newton iterations). In the asymptotic limit only one Newton iteration is required per grid. However, as the grid is refined the performance of any single-grid precondtioner, whose memory requirements scale linearly with grid dimension, will degrade. This results in a significant growth in Krylov iterations per Newton iteration. This growth is of great concern if one is using a Krylov algorithm such as GMRES since the storage scales linearly and the work scales quadratically with linear (Krylov) iteration number. We demonstrate the ability of a multigrid V-cycle preconditioner to limit the growth in Krylov iterations per Newton iteration as the grid is refined. Different strategies for constructing the coarse grid Jacobians are compared. Two of the options considered are: 1) Retaining the last Jacobian from all previous grids in the "mesh sequencing" algorithm; 2) Restricting the current solution down through the coarse grids and forming the coarse grid Jacobians from this solution. We will also consider possible methods for forming the coarse grid Jacobians from the existing fine grid Jacobian. Some of the unique properties/capabilities of a multigrid preconditioned matrix-free Newton-Krylov algorithm for nonlinear boundary value problems will be demonstrated. Specifically, the ability to use a lower-order, linear, discretization to precondition a high-order, nonlinear, discretization, while maintaining Newton-like nonlinear convergence characteristics will be demonstrated.