Department of Computer Science, Technion

Abstract

Multigrid computational methods are well known to be efficient and reliable iterative solvers for many discretized partial differential equations. There are two general approaches for solving nonlinear problems by multigrid methods: (1) Global Linearization (GL), whereby the discrete equations are linearized by Newton's method (or some inexact variant), and the resulting linear system is solved by a robust and efficient linear multigrid solver; (2) Local Linearization (LL), whereby errors are smoothed by nonlinear relaxation methods, and the convergence is accelerated using nonlinear coarse-grid operators. GL and LL methods have distinct advantages. We propose a new approach, which is expected to be at least as robust as either of these methods, and often better than both. The main idea is to split the operator into a large linear part and a relatively small nonlinear remainder, and to use the nonlinear coarse-grid approximation only for the nonlinear part, while the main term is handled on the coarse grid by a robust linear approximation. Adaptive and parallel variants are also considered.