Department of Computer Science, Technion 32000, Haifa, Israel

Gregory Dardyk

Abstract

Robust multigrid algorithms for linear boundary-value problems are well-researched. For nonlinear problems, two general approaches are used widely: Global Linearization (GL) and Local Linearization (LL). In the GL approach, e.g., Newton's method, the discretized problem is linearized and the resulting linear system is solved approximately by a (robust) linear multigrid algorithm. This is repeated iteratively. In the LL approach, the nonlinear fine-grid operator is approximated nonlinearly on the coarser grids, and explicit linearization is only performed locally, in the relaxation process. The best known of the LL methods is the so-called FAS (Full Approximation Scheme). For simple problems, the two approaches often perform similarly, but a distinct behavior is exhibited in more complicated situations, with the GL approach performing better in some cases and the LL approach in others. We propose a Multilevel Nonlinear Method (MNM) which is designed to be at least as robust as either one of the classical approaches and often more robust than both. A heuristic analysis, supported by numerical experiments, suggests that MNM indeed yields superior convergence behavior for difficult nonlinear problems.