Domain decomposition and multigrid methods for nonlinear problems and variational inequalities

Xue-Cheng Tai

Email: tai@mi.uib.no
Postal address: Mathematics Institute, University of Bergen, Johan. Brunsgate 12, N-5008, Norway
Web: http://www.mi.uib.no/~tai

Domain decomposition (DD) and multigrid (MG) have been intensively studied for linear elliptic problems. In this talk, we will present a general framework, c.f. [3,4], to extend DD and MG methods to general nonlinear problems using the ideas of space decomposition and subspace correction [5].

For variational inequalities like the obstacle problems, there are some algorithms that can be used for solving it. However, a rigorous convergence proof is still missing in the literature. In this work, we use the framework of space decomposition and subspace correction to give some general proofs of convergence for variational inequalities [1,2]. We use this theory to develope several domain decomposition and multigrid algorithms for obstacle problems. These algorithms have a convergence rate independent of the mesh parameters used in finite element approximations. The convergence property is verified theoretically and numerically.

One of the essential difficulties in the convergence analysis for obstacle problems is the estimate for the constant appeared in the so-called partition lemma. For obstacle problems, we need to decompose a given function into a sum of functions from the subspaces. The decompositions should satisfy a norm equivalent estimate. In addition, the decomposed functions also need to satisfy some sub-obstacle constraints. By using a new nonlinear constrained interpolation operator, we are able to show that the constant from the partition lemma is independent of the mesh parameters of finite element approximations, see [1] for the details.

References:

[1] X.-C. Tai, Rate of convergence for some constraint decomposition methods for nonlinear variational inequalities, Numer. Math., 2002.

[2] X.-C. Tai, B. Heimsund, and J. Xu, Rate of convergence for parallel subspace correction methods for nonlinear variational inequalities, in "Proceedings of the Thirteenth international conference on domain decomposition methods", 2001, pp. 127--138.

[3] X.-C. Tai and M.~Espedal.
Rate of convergence of some space decomposition method for linear and  nonlinear elliptic problems. SIAM J. Numer. Anal., 35:1558--1570, 1998.

[4]
X-C. Tai and J.-C. Xu. Global convergence of subspace correction methods for convex optimization problems. Math. Comp., vol. 71, no. 237, pp. 105-124, May  2001.

[5] J.~Xu.
Iteration methods by space decomposition and subspace correction. SIAM Rev., 34:581--613, 1992.