Nonlinear preconditioning: how to use a nonlinear Schwarz method to precondition Newton's method

V. Dolean, M. J. Gander, W. Kheriji, F. Kwok, R. Masson

Research output: Contribution to journalArticle

10 Citations (Scopus)

Abstract

For linear problems, domain decomposition methods can be used directly as iterative solvers, but also as preconditioners for Krylov methods. In practice, Krylov acceleration is almost always used, since the Krylov method finds a much better residual polynomial than the stationary iteration, and thus converges much faster. We show in this paper that also for non-linear problems, domain decomposition methods can either be used directly as iterative solvers, or one can use them as preconditioners for Newton's method. For the concrete case of the parallel Schwarz method, we show that we obtain a preconditioner we call RASPEN (Restricted Additive Schwarz Preconditioned Exact Newton) which is similar to ASPIN (Additive Schwarz Preconditioned Inexact Newton), but with all components directly defined by the iterative method. This has the advantage that RASPEN already converges when used as an iterative solver, in contrast to ASPIN, and we thus get a substantially better preconditioner for Newton's method. The iterative construction also allows us to naturally define a coarse correction using the multigrid full approximation scheme, which leads to a convergent two level non-linear iterative domain decomposition method and a two level RASPEN non-linear preconditioner. We illustrate our findings with numerical results on the Forchheimer equation and a non-linear diffusion problem.
LanguageEnglish
PagesA3357-A3380
Number of pages24
JournalSIAM Journal on Scientific Computing
Volume38
Issue number6
DOIs
Publication statusPublished - 1 Nov 2016

Fingerprint

Additive Schwarz
Schwarz Methods
Domain decomposition methods
Precondition
Newton-Raphson method
Preconditioning
Newton Methods
Preconditioner
Domain Decomposition Method
Krylov Methods
Iterative Solvers
Nonlinear Problem
Iterative methods
Converge
Iteration
Iterative Solver
Polynomials
Parallel Methods
Nonlinear Diffusion
Diffusion Problem

Keywords

  • linear problems
  • Krylov methods
  • domain decomposition methods
  • restricted additive Schwarz preconditioned exact Newton
  • additive Schwarz preconditioned inexact Newton
  • Forchheimer equation

Cite this

Dolean, V. ; Gander, M. J. ; Kheriji, W. ; Kwok, F. ; Masson, R. / Nonlinear preconditioning : how to use a nonlinear Schwarz method to precondition Newton's method. In: SIAM Journal on Scientific Computing. 2016 ; Vol. 38, No. 6. pp. A3357-A3380.
@article{bd2c2ca204404d54ad2c6ccedfcff741,
title = "Nonlinear preconditioning: how to use a nonlinear Schwarz method to precondition Newton's method",
abstract = "For linear problems, domain decomposition methods can be used directly as iterative solvers, but also as preconditioners for Krylov methods. In practice, Krylov acceleration is almost always used, since the Krylov method finds a much better residual polynomial than the stationary iteration, and thus converges much faster. We show in this paper that also for non-linear problems, domain decomposition methods can either be used directly as iterative solvers, or one can use them as preconditioners for Newton's method. For the concrete case of the parallel Schwarz method, we show that we obtain a preconditioner we call RASPEN (Restricted Additive Schwarz Preconditioned Exact Newton) which is similar to ASPIN (Additive Schwarz Preconditioned Inexact Newton), but with all components directly defined by the iterative method. This has the advantage that RASPEN already converges when used as an iterative solver, in contrast to ASPIN, and we thus get a substantially better preconditioner for Newton's method. The iterative construction also allows us to naturally define a coarse correction using the multigrid full approximation scheme, which leads to a convergent two level non-linear iterative domain decomposition method and a two level RASPEN non-linear preconditioner. We illustrate our findings with numerical results on the Forchheimer equation and a non-linear diffusion problem.",
keywords = "linear problems, Krylov methods, domain decomposition methods, restricted additive Schwarz preconditioned exact Newton, additive Schwarz preconditioned inexact Newton, Forchheimer equation",
author = "V. Dolean and Gander, {M. J.} and W. Kheriji and F. Kwok and R. Masson",
note = "First Published in SIAM Journal on Scientific Computing in 2016, published by the Society for Industrial and Applied Mathematics (SIAM). Copyright {\circledC} by SIAM. Unauthorized reproduction of this article is prohibited.",
year = "2016",
month = "11",
day = "1",
doi = "10.1137/15M102887X",
language = "English",
volume = "38",
pages = "A3357--A3380",
journal = "SIAM Journal on Scientific Computing",
issn = "1064-8275",
number = "6",

}

Nonlinear preconditioning : how to use a nonlinear Schwarz method to precondition Newton's method. / Dolean, V.; Gander, M. J.; Kheriji, W.; Kwok, F.; Masson, R.

In: SIAM Journal on Scientific Computing, Vol. 38, No. 6, 01.11.2016, p. A3357-A3380.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Nonlinear preconditioning

T2 - SIAM Journal on Scientific Computing

AU - Dolean, V.

AU - Gander, M. J.

AU - Kheriji, W.

AU - Kwok, F.

AU - Masson, R.

N1 - First Published in SIAM Journal on Scientific Computing in 2016, published by the Society for Industrial and Applied Mathematics (SIAM). Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

PY - 2016/11/1

Y1 - 2016/11/1

N2 - For linear problems, domain decomposition methods can be used directly as iterative solvers, but also as preconditioners for Krylov methods. In practice, Krylov acceleration is almost always used, since the Krylov method finds a much better residual polynomial than the stationary iteration, and thus converges much faster. We show in this paper that also for non-linear problems, domain decomposition methods can either be used directly as iterative solvers, or one can use them as preconditioners for Newton's method. For the concrete case of the parallel Schwarz method, we show that we obtain a preconditioner we call RASPEN (Restricted Additive Schwarz Preconditioned Exact Newton) which is similar to ASPIN (Additive Schwarz Preconditioned Inexact Newton), but with all components directly defined by the iterative method. This has the advantage that RASPEN already converges when used as an iterative solver, in contrast to ASPIN, and we thus get a substantially better preconditioner for Newton's method. The iterative construction also allows us to naturally define a coarse correction using the multigrid full approximation scheme, which leads to a convergent two level non-linear iterative domain decomposition method and a two level RASPEN non-linear preconditioner. We illustrate our findings with numerical results on the Forchheimer equation and a non-linear diffusion problem.

AB - For linear problems, domain decomposition methods can be used directly as iterative solvers, but also as preconditioners for Krylov methods. In practice, Krylov acceleration is almost always used, since the Krylov method finds a much better residual polynomial than the stationary iteration, and thus converges much faster. We show in this paper that also for non-linear problems, domain decomposition methods can either be used directly as iterative solvers, or one can use them as preconditioners for Newton's method. For the concrete case of the parallel Schwarz method, we show that we obtain a preconditioner we call RASPEN (Restricted Additive Schwarz Preconditioned Exact Newton) which is similar to ASPIN (Additive Schwarz Preconditioned Inexact Newton), but with all components directly defined by the iterative method. This has the advantage that RASPEN already converges when used as an iterative solver, in contrast to ASPIN, and we thus get a substantially better preconditioner for Newton's method. The iterative construction also allows us to naturally define a coarse correction using the multigrid full approximation scheme, which leads to a convergent two level non-linear iterative domain decomposition method and a two level RASPEN non-linear preconditioner. We illustrate our findings with numerical results on the Forchheimer equation and a non-linear diffusion problem.

KW - linear problems

KW - Krylov methods

KW - domain decomposition methods

KW - restricted additive Schwarz preconditioned exact Newton

KW - additive Schwarz preconditioned inexact Newton

KW - Forchheimer equation

U2 - 10.1137/15M102887X

DO - 10.1137/15M102887X

M3 - Article

VL - 38

SP - A3357-A3380

JO - SIAM Journal on Scientific Computing

JF - SIAM Journal on Scientific Computing

SN - 1064-8275

IS - 6

ER -