Printer Friendly

An overlapping additive Schwarz-Richardson method for monotone nonlinear parabolic problems.

AMS subject classifications. 65M55, 651105

1. Introduction. In recent years, domain decomposition methods have been extended in different ways to nonlinear problems arising in many application areas. As a first approach, domain decomposition methods provide preconditioners for the Jacobian system in a Newton-like iteration. In this context, Schwarz-type preconditioners have been successfully used by Cai et al. to solve problems from various applied fields, e.g., computational fluid dynamics [11, 17], full potential problems [10], cardiac electrical activity [25], and unsteady nonlinear radiation diffusion [27]. Additive Schwarz methods have been used not only as inner iterations in a Newton-Krylov-Schwarz (NKS) scheme, but also as outer iterations in nested solvers such as ASPIN [12, 1] or in the nonlinear additive Schwarz method by Dryja and Hackbusch [15]. Different approaches have been studied by Lui [19, 20] using the method of monotone iterations for continuous nonlinear elliptic and parabolic PDEs and by Boglaev [4] using monotone Schwarz methods at the discrete level for singularly perturbed reaction-diffusion problems. Extensions of the classical additive and multiplicative Schwarz methods have been studied by Tai and Espedal [31, 32] for convex programming problems and by Badea [2] for constrained minimization problems.

In this paper, we follow instead the work of Cai and Dryja [9] for monotone elliptic problems and extend it to monotone nonlinear parabolic problems. The main idea is to build an overlapping additive Schwarz preconditioner for the linear part of the operator, partitioning the domain of the problem into overlapping subdomains, solving local problems on these subdomains, and solving an additional coarse problem associated with the subdomain mesh. This preconditioner is then applied to the nonlinear operator using a Richardson iteration. The linearity of the preconditioner allows us to employ the main technical tools of the classical abstract theory of additive Schwarz methods (see, e.g., [33]), and prove an abstract convergence result for the resulting iterative method. With this result, we can then obtain precise convergence estimates for the Additive Schwarz-Richardson (ASR) method applied to the time discretization of monotone nonlinear parabolic problems. The two-level ASR method turns out to be scalable and with a convergence rate depending only on the ratio H/[delta] as in the linear case, where H is the subdomain characteristic size and [delta] the overlap size. Without a coarse space, the one-level ASR method can still have a constant upper bound if the time step size [tau] is small enough. Otherwise, the convergence rate depends on the ratio [tau]/(H[delta]) and scalability is lost as in the linear case. In case of generous overlap [delta] = CH, these estimates agree with the estimates obtained by Cai [7, 8] for linear parabolic problems.

The rest of the paper is organized as follows. In Section 2, we introduce the nonlinear parabolic problem, its main properties and time discretization. In Section 3, we define the ASR method in both its functional and matrix form. An abstract convergence result is given in Section 4, where we prove some technical lemmas leading to the main result of Theorem 4.7. In Section 5, this abstract result is applied to the time discretization of our nonlinear parabolic problem and convergence rate estimates are obtained for both one- and two-level ASR methods. Section 6 concludes the paper with the results of several numerical experiments in the plane, confirming the theoretical results obtained and illustrating the scalability of the ASR method. We also compare the ASR method with the Linearly Implicit Euler method, based on solving an appropriate linear system involving the Jacobian of the nonlinear operator by using GMRES with the Additive Schwarz preconditioner as in ASR and we show that the ASR method is asymptotically less expensive.

2. Continuous and discrete nonlinear parabolic problems. We consider a polyhedral domain [OMEGA] [subset] [R.sup.d], d = 2, 3, with Lipschitz continuous boundary [partial derivative][OMEGA], the spaces

V = {v [member of] [H.sup.1]([OMEGA]) : v = 0 on [[GAMMA].sub.1] [subset] [partial derivative], meas([[GAMMA].sub.1]) > 0}, [L.sup.2]([OMEGA]),

and the nonlinear form b : [H.sup.1]([OMEGA]) x [H.sup.1]([OMEGA]) [right arrow] R satisfying the following properties:

1. b is Lipschitz continuous: [there exists]L > 0 such that, [for all]v, w, z [member of] [H.sup.1]([OMEGA]), [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

2. b is bounded: [there exists]C > 0 such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [for all]v, w [member of] [H.sup.1]([OMEGA]);

3. b is hemicontinuous: [for all]u, v, w [member of] [H.sup.1]([OMEGA]), the function [alpha] [right arrow] b(u+[alpha]v, w) is continuous;

4. b is strictly monotone: b(v, v - w) - b(w, v - w) [greater than or equal to] 0, [for all]v, w [member of] [H.sup.1]([OMEGA]), and equality holds only for v = w;

5. b is linear in its second argument: b(v, [n.summation over (i=1)] [[alpha].sub.i][w.sub.i]) = [n.summation over (i=1)][[alpha].sub.i]b(v, [w.sub.i]), [for all]v, [w.sub.i] [member of] [H.sup.1]([OMEGA]), [for all][[alpha].sub.i] [member of] R, i = 1, ..., n;

6. b(v, v) [greater than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where c > 0, [c.sub.0] > 0, [c.sub.1] [greater than or equal to] 0, [c.sub.2] [greater than or equal to] 0 are constants.

We consider the following nonlinear parabolic problem: given [u.sub.0] [member of] [L.sup.2]([OMEGA]) and f [member of] [L.sup.2]((0, T); [V.sup.*]), find u [member of] W [equivalent to] {u [member of] [L.sup.2]((0, T); V), u' [member of] [L.sup.2]((0, T); V)}, such that

(2.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [E.sub.w] [subset] (0, T) is a set of measure zero that depends on the function w.

The continuous problem (2.1) is discretized implicitly in time by the backward Euler method and in space by the finite element method. We suppose for simplicity that the time interval (0, T) is discretized with a uniform time step [tau] = T/M into M equal subintervals and that the domain is discretized with a regular finite element triangulation [T.sub.h] with mesh size h. The associated piecewise linear finite element space [V.sub.h] is defined by

[V.sub.h] = {v|v is continuous on [bar.[OMEGA]], v[|.sub.k] is linear [for all]k [member of] [T.sub.h], v = 0 on [bar.[[GAMMA]].sub.1]}.

We denote by [u.sup.m.sub.h] [member of] [V.sub.h] the finite element approximation of a function u [member of] V at time [t.sup.m] = m[tau] and let [f.sup.m] = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] f(t)dt. We then obtain the following fully discrete problem: given an arbitrary sequence {[u.sup.0.sub.h]} [subset] [L.sup.2]([OMEGA]) of approximations of [u.sup.0], such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], find [u.sup.m.sub.h] [member of] [V.sub.h], such that

(2.2) ([u.sup.m.sub.h] - [u.sup.m-1.sub.h]/[tau], v) + b([u.sup.m.sub.h], v) = < [f.sup.m], v >, [for all]v [member of] [V.sub.h]

Results on the existence and uniqueness of the solution of the discrete and continuous parabolic problems can be found, e.g., in [35, Theorems 45.3 and 46.4], respectively. The convergence of the discrete solution to the continuous one is presented in [35, Theorems 46.4 and 47.1].

3. An Additive Schwarz-Richardson algorithm. Since in the rest of the paper we only consider discrete functions, for simplicity, we drop the indices h and m and denote by u both the finite element approximation u = [n.summation over (j=1)] [u.sub.j][[phi].sub.j] of the continuous solution in the finite element basis {[[phi].sub.j], j = 1, ..., n} of [V.sub.h], and its vector representation u = [[[u.sub.1], ..., [u.sub.n]].sup.T]. Problem (2.2) can then be written as the nonlinear algebraic system,

(3.1) B(u) = [??],

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Following the abstract Schwarz theory, presented, e.g., in [33], we consider a family of subspaces [V.sub.i] [subset] [V.sub.h], i = 0, ..., N, and interpolation (or extension) operators [R.sup.T.sub.i] : [V.sub.i] [right arrow] [V.sub.h], and assume that [V.sub.h] admits the decomposition

[V.sub.h] = [N.summation over (i=0)] [R.sup.T.sub.i] [V.sub.i].

We suppose that there exists a symmetric, continuous and coercive bilinear form a : V x V [right arrow] R, such that

(3.2) b(u, v) = a(u, v) + [??](u, v),

with [??] a nonlinear form, monotone and Lipschitz continuous with Lipschitz constant [??]. Nonlinear forms b(u, v) with such a structure arise, e.g., in the field of computational electrocardiology, where research on parallel solvers for the associated nonlinear parabolic reaction-diffusion models (known as monodomain and bidomain models) is currently very active; see, e.g., [25, 13, 30, 22, 24, 21, 23, 28].

Since the bilinear form

[a.sub.[tau]] (u, v) = (u, v) + [tau]a(u, v)

defines a scalar product on V, we can introduce local symmetric, positive definite bilinear forms [[??].sub.[tau],i] : [V.sub.i] x [V.sub.i] [right arrow] R, and we make the standard three assumptions of the abstract Schwarz theory (see [33] for more details):

* stable decomposition: there exists a constant [C.sub.0], such that every u [member of] [V.sub.h] admits a decomposition u = [N.summation over (i=0)] [R.sup.T.sub.i] [u.sub.i], [u.sub.i] [member of] [V.sub.i], i = 0, ..., N that satisfies

(3.3) [N.summation over (i=0)] [[??].sub.[tau],i] ([u.sub.i], [u.sub.i]) [less than or equal to] [C.sup.2.sub.0] [a.sub.[tau]] (u, u);

* strengthened Cauchy-Schwarz inequality: [there exists] [[epsilon].sub.ij] [member of] [0, 1] i, j = 1, ..., N, such that [for all][u.sub.i] [member of] [V.sub.i], [for all][u.sub.j] [member of] [V.sub.j]

(3.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(we denote by [rho]([epsilon]) the spectral radius of the matrix [epsilon] = ([[epsilon].sub.ij]))

* local stability: there exists [omega] > 0, such that

(3.5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We define the "projection"-like operators [[??].sub.i] : [V.sub.h] [right arrow] [V.sub.i] by

(3.6) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and their extensions [Q.sub.i] : [V.sub.h] [right arrow] [R.sup.T.sub.i] [V.sub.i] [subset] [V.sub.h] defined by

[Q.sub.i](u) = [R.sup.T.sub.i] [[??].sub.i](u) and Q(u) = [N.summation over (i=0)] [Q.sub.i](u).

Let [[??].sub.[tau],i] [equivalent to] [([[??].sub.[tau],i]([[phi].sub.j], [[phi].sub.l])).sub.j,l] be the matrix representation of the local bilinear form [[??].sub.[tau],i].

LEMMA 3.1. The matrix form of Q(u) is

(3.7) Q(u) = [M.sub.-1]B(u),

where M = [(N.summation over (i=0)] [R.sup.T.sub.i] [[??].sup.-1.sub.[tau],i][R.sub.i]).sub.-1].

Proof. Let {[[psi].sup.k.sub.i], k = 1, ..., [n.sub.i]} be a basis of the local subspace [V.sub.i]. Then [[??].sub.i](u) [member of] [V.sub.i] can be written as [[??].sub.i](u) = [summation over l] [[??].sub.i][(u).sup.l] [[psi].sup.l.sub.i] and the two terms in (3.6) become

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The definition of [[??].sub.i](u) implies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and consequently

[[??].sub.[tau],i] [[??].sub.i](u) = [R.sub.i]B(u), [for all]u [member of] [V.sub.h].

The matrix form of [[??].sub.i](u) is then

[[??].sub.i](u) = [[??].sup.-1.sub.[tau],i] [R.sub.i]B(u).

Since [Q.sub.i](u) = [R.sup.T.sub.i] [[??].sub.i](u), the matrix form of [Q.sub.i](u) is

[Q.sub.i](u) = [R.sup.T.sub.i] [[??].sup.-1.sub.[tau],i] [R.sub.i]B(u).

Hence,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where M = [([N.summation over (i=0)] [R.sup.T.sub.i] [[??].sup.-1.sub.[tau],i][R.sub.i]).sub.-1].

REMARK 3.2. Since the matrix M is symmetric and positive definite, it defines the M-norm [[parallel]u[parallel].sub.M] = [([u.sup.T]Mu).sup.1/2].

We define [[??].sub.i] = [Q.sub.i]([u.sup.*]), where [u.sup.*] is the exact solution of (3.1), i.e: B([u.sup.*]) = [??]. We consider the nonlinear system

(3.8) Q(u) = [??],

where [??] = [N.summation over (i=0)] [[??].sub.i]. As in the linear case (see [29, p. 150]), [??] can be computed without knowing the exact solution [u.sup.*], since

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using the matrix form of the nonlinear operator Q and the definition of [??], it is straightforward to prove that the nonlinear system B(u) = [??] is equivalent to the nonlinear system Q(u) = [??]. In other words, we use the symmetric positive definite part as a preconditioner for the original nonlinear system. This idea has already been used by Cai and Xu [34] for nonsymmetric or indefinite problems. We can then define the Additive Schwarz-Richardson (ASR) algorithm for Problem (3.1).

ASR algorithm: given initial guesses [u.sup.0], [r.sup.0] = Q([u.sup.0]) - [??] and a stopping criterion, iterate for k = 0, 1, ... until convergence

(3.9) solve the preconditioned system: [Mr.sup.k] = B([u.sup.k]) - [??], update the solution: [u.sup.k+1] = [u.sup.k] - [lambda][r.sup.k],

where [lambda] is a properly chosen parameter; see Theorem 4.7.

We prove in the next section that the ASR iterations converge if [lambda] is chosen properly, and its convergence rate depends on the parameters [C.sub.0], [[epsilon].sub.ij], [omega] defined previously.

4. An abstract convergence result. In order to prove our main result, Theorem 4.7, we need a few technical results established in the next few lemmas. We start by recalling a lemma due to Zhang [36], that plays an important role in proving the equivalence between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

LEMMA 4.1. Let [[??].sub.i] be the projection-like operator from V onto [V.sub.i] defined by [[??].sub.[tau],i]([[??].sub.i]u, [v.sub.i]) = [a.sub.[tau]] (u,[R.sup.T.sub.i] [v.sub.i]), [v.sub.i] [member of] [V.sub.i] and [P.sub.ad] = [N.summation over (i=0)] [R.sup.T.sub.i] [[??].sub.i] = [M.sup.-1][A.sub.[tau]]. Then

(4.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

LEMMA 4.2. The M-norm and [a.sub.[tau]]-norm are equivalent, i.e.,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [C.sub.0], [omega] and [rho](E) are the constants defined in the three assumptions of the abstract Schwarz theory, inequalities (3.3)-(3.5).

Proof. a) Lower bound. Using Lemma 4.1 and the stable decomposition assumption (3.3), we have

b) Upper bound. Let [bar.u] = [N.summation over (i=1)] [R.sup.T.sub.i] [u.sub.i]. From the strengthened Cauchy-Schwarz inequality (3.4) and the local stability assumption (3.5), it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Each element u [member of] [V.sub.h] can be written as u = [R.sup.T.sub.0] [u.sub.0] + [bar.u]. Using the bilinearity of [a.sub.[tau]], the local stability assumption and the last bound, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Taking the minimum over the all decompositions of u and using Lemma 4.1, we conclude

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

LEMMA 4.3. There exists a constant [[delta].sub.0] = 1/[C.sup.2.sub.0] > 0, such that

[(Q(u + z) Q(u), z).sub.M] [greater than or equal to] [[delta].sub.0][[parallel]z[parallel].sup.2.sub.M], [for all]u, z [member of] [V.sub.h].

Proof. The definition of Q(u), the linearity of b in the second argument, the strict monotonicity of [??], and the lower bound of Lemma 4.2 imply

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using a particular decomposition of z, we are able to give another proof of this lemma. Since [P.sub.ad] is invertible (see [33, Lemma 2.5]), we can decompose z [member of] [V.sub.h] as z = [summation over j] [R.sup.T.sub.j] [z.sub.j], where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using the monotonicity of [??], we can write

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By the definition of [z.sub.j], [[??].sub.j] = [[??].sup.-1[tau]j] [R.sub.j][A.sub.[tau]], [P.sub.ad] = [M.sup.-1] [A.sub.[tau]], and we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We conclude the proof by using Lemma 4.2.

LEMMA 4.4. For i = 0, 1, ..., N, we have that

a) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

b) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof. a) Using the definition of [Q.sub.i], the local stability assumption, the definition of [[??].sub.i], the linearity of [a.sub.[tau]], and the Lipschitz continuity of [??], we have,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

b) By the Cauchy-Schwarz inequality, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The coercivity of the bilinear form a(x, x) implies that [tau][parallel]z[parallel].sup.2] [less than or equal to] c[tau]a(z, z) [less than or equal to] c[a.sub.[tau]] (z, z) and consequently we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

LEMMA 4.5. There exists a constant [[??].sub.2.sup.1] = 2[[omega].sup.2]([rho]([epsilon]).sub.2] + 1)[(1 + c[??]).sub.2] > 0, such that

[parallel]Q(u + z) Q(u)[parallel][a.sub.[tau]] [less than or equal to] [[delta].sub.1][parallel]z[parallel][a.sub.[tau]], [for all]u, v [member of] [V.sub.h].

Proof. Define [bar.Q](u) = [N.summation over (i=1)] [Q.sub.i](u), as in the proof of the upper bound of Lemma 4.2. The bilinearity of [a.sub.[tau]], the definition of [Q.sub.i](u), and the strengthened Cauchy-Schwarz inequality, imply that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

From Lemma 4.4, we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence,

(4.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since Q(u) = [Q.sub.0](u) + [bar.Q](u), relation (4.2) and Lemma 4.4 give us

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

LEMMA 4.6. There exists a constant [[delta].sub.1] = [C.sup.2.sub.0] [[delta].sub.1.suo.2] 2[omega](1 + [rho]([epsilon])), such that

[[parallel]Q(u + z) Q(u)[parallel].sup.2.sub.M] [less than or equal to] [[delta].sub.1][[parallel]z[parallel].sup.2.sub.M].

Proof. This bound is a direct consequence of Lemma 4.2 and Lemma 4.5:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using these lemmas, we are now in a position to prove the main convergence result for our ASR method.

THEOREM 4.7. If 0 < [lambda] < 2[[delta].sub.0]/[[delta].sup.2.sub.1], then the ASR method for Problem (3.8) converges, i.e.,

[[parallel][u.sup.k] - [u.sup.*][parallel].sup.2.sub.M] [less than or equal to] P[([lambda]).sup.k][[parallel][u.sup.0] - [u.sup.*][parallel].sup.2.sub.M],

where P([lambda]) = 1 2[lambda][[delta].sub.0] + [[lambda].sup.2][[delta].sup.2.sub.1] and [[delta].sub.0], [[delta].sub.1] are the constants defined in Lemma 4.3 and Lemma 4.6, respectively.

Proof. Let [e.sup.k] = [u.sup.k] - [u.sup.*] and [r.sup.k] = Q([u.sup.k]) - Q([u.sup.*]) be the error and the residual at step k.

Then

[e.sup.k+1] = [u.sup.k+1] [u.sup.*] = [u.sup.k] - [lambda][r.sup.k] - [u.sup.*] = [e.sup.k] - [lambda][r.sup.k],

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Lemma 4.3 with u = [u.sup.*] and z = [u.sup.k] - [u.sup.*] yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using Lemma 4.6 with u = [u.sup.*] and z = [u.sup.k] - [u.sup.*], we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Therefore

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If we choose 0 < [lambda] < 2[[delta].sub.0]/[[delta].sup.2.sub.1], then P([lambda]) < 1, and we obtain the convergence of the ASR method.

REMARK 4.8. P([lambda]) attains its minimum at [[lambda].sub.min] = [[delta].sub.0]/[[delta].sup.2.sub.1] and P([[lambda].sub.min]) = 1 - [[delta].sub.2.sub.0]/[[delta].sup.2.sub.1] < 1.

REMARK 4.9. If we drop the coarse space [V.sub.0] and define Q(u) = [N.summation over (i=1)] [Q.sub.i](u), the ASR algorithmis convergent. It is easy to see that in this case [[delta].sub.0] = 1/[C.sup.2.sub.0] and [[delta].sub.1] = [C.sub.0][rho]([epsilon])[omega](1+c[??]).

REMARK 4.10. The ASR performance depends on the choice of the parameter [lambda] in the Richardson iteration. This parameter can be chosen:

i) theoretically, by approximately minimizing the quadratic function P([lambda]) in Theorem 4.7 if the constants d0 and d1 can be estimated;

ii) numerically, by running a few tests cases (as we have done in Section 6, Figure 6.1) and selecting a value which gives an approximate minimum of the ASR iteration count;

iii) automatically, by using one of the step-length strategies available in the literature of numerical optimization, such as the one described in [26]; see the results reported in Section 6, Table 6.2.

We remark that the numerical results of Figure 6.1 show that the ASR iteration count is not very sensitive to the choice of [??] near the minimum, but only near the endpoints of the convergence interval.

5. Convergence estimates for parabolic problem. Our additive Schwarz preconditioner is build as in the linear case. We partition the domain [OMEGA] into shape regular nonoverlapping subdomains [[OMEGA].sub.i], 1 [less than or equal to] i [less than or equal to] N, of characteristic diameter H, defining a shape-regular coarse mesh [T.sub.H]. Each subdomain [[OMEGA].sub.i] is extended to a larger one, [[OMEGA]'.sub.i], by adding the elements of the fine mesh [T.sub.h] within a distance [[delta].sub.i] from its boundary. We assume that the partition {[[OMEGA]'.sub.i]} satisfies the finite covering assumption (see, e.g., [33]), and we denote by [delta] = [max.sub.i] [[delta].sub.i] the overlap size. Using the above decomposition, a one-level method is defined by the local spaces [V.sub.i] = {v [member of] [H.sup.1.sub.0] ([[OMEGA]'.sub.i]) [[absolute value of v].sub.T] is linear, [for all]T [member of] [T.sub.h,i]}, 1 [less than or equal to] i [less than or equal to] N, and the local bilinear forms [[??].sub.[tau],i]([u.sub.i], [v.sub.i]) = [[??].sub.[tau]] ([R.sup.T.sub.i] [u.sub.i], [R.sup.T.sub.i] [v.sub.i]), [for all][u.sub.i], [v.sub.i] [member of] [V.sub.i], with interpolation operators [R.sup.T.sub.i] : [V.sub.i] [right arrow] V, 1 [less than or equal to] i [less than or equal to] N. We then build a two-level algorithm by defining the coarse finite element space [V.sub.0] = {v [member of] [H.sup.1.sub.0] ([OMEGA])|v is continuous and v[|.sub.T] is linear, [for all]T [member of] [T.sub.H]} and the operator [R.sup.T.sub.0], which interpolates the coarse functions onto the fine mesh.

We consider the variational parabolic problem: given u([t.sub.0], x) = [u.sub.0](x) and right-hand side G, find u(t) [member of] [H.sup.1]([OMEGA]), such that [for all]t [member of] ([t.sub.0], T),

(5.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

with [a.sub.ij] [member of] [C.sup.1]([OMEGA]), such that [a.sub.ij](x) = [a.sub.ji](x), [for all]x [member of] [subset] [R.sup.d] for all i, j = 1, ..., d and F a monotone nonlinear function.

The abstract convergence result of Theorem 4.7 now can be applied to get explicit bounds in terms of the discretization parameters. For simplicity, we consider the simplest case, where we use exact solvers (i.e., [[??].sub.[tau],i]([u.sub.i], [v.sub.i]) = [a.sub.[tau]] ([R.sup.T.sub.i] [u.sub.i], [R.sup.T.sub.i] [v.sub.i]), [for all][u.sub.i], [v.sub.i] [member of] [V.sub.i]), so that [omega] = 1 in the local stability assumption. We also assume that there are at most [N.sup.c] nonzero elements in each row of [epsilon] [less than or equal to] [N.sup.c], so that [rho](E) [less than or equal to] [N.sup.c] in the strengthened Cauchy-Schwarz inequality; see [33, Lemma 2.10]. Therefore, we need only to bound the constant [C.sub.0] in the stable decomposition assumption.

LEMMA 5.1. The stable decomposition constant C0 can be bounded by

a) [C.sup.2.sub.0] [less than or equal to] C max {1 + H/[delta], 1 + [tau]/H[delta]}, in the one-level case,

b) [C.sup.2.sub.0] [less than or equal to] C (1 + [H/[delta]), in the two-level case,

where C is a constant independent of H, h and [delta].

Proof. a) One-level case. Following the classical proof for the linear elliptic case (see, e.g., [33]), we define [u.sub.i] = [R.sub.i]([I.sup.h]([[theta].sub.i]u)), i = 1, ..., N, where {[[theta].sub.i] [member of] [W.sup.1,8, 1 [less than or equal to] i [less than or equal to] N} defines a partition of unity and [I.sup.h] is the nodal piecewise linear interpolant on the fine mesh Th. By the approximations properties of [I.sup.h] and the small overlap lemma (see [33], Lemma 3.10 and eqs.(3.20) - (3.23) or the original Lemma 3.1 in [16]), we obtain

(5.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The equivalence between the [L.sup.2]([OMEGA])-norm and the discrete [L.sup.2]([OMEGA])-norm implies that

(5.3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using the coercivity of a(x, x), (5.2), (5.3), and the finite covering assumption, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The coercivity of the bilinear form a(x, x) implies that |u|2[H.sup.1]([OMEGA]) [less than or equal to] Ca(u, u) and therefore

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

b) Two-level case. Suppose that the coarse mesh is quasi-uniform. Then the bound for [C.sup.2.sub.0] can be obtained as in [33] by letting [I.sup.H] : [L.sup.2]([OMEGA]) [right arrow] [V.sub.0] be the [L.sup.2]-projection of u, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

REMARK 5.2. The bound a) of Lemma 5.1 implies that if the ratio t/(Hd) is small enough, then a constant upper bound C20 [less than or equal to] C _1 + Hh _ still holds for the one-level ASR algorithm.

REMARK 5.3. In case of small overlap [delta] = h, the estimates of Lemma 5.1 become a) [C.sup.2.sub.0] [less than or equal to] C max{1 + H/h, 1 + [tau]/Hh), in the one-level case,

b) [C.sup.2.sub.0] [less than or equal to] C (1 + H/h), in the two-level case.

Therefore, in scaled speed-up tests with constant ratio H/h only the two-level ASR algorithm is scalable, since the term [tau]/(Hh) asymptotically dominates the one-level bound for any fixed value of t. Nevertheless, for a moderate number of subdomains (i.e., for 1/H small enough), the one-level bound is dominated by the first term 1 + H/h, which yields a "temporary" scalability; see Figure 6.2.

REMARK 5.4. In case of generous overlap d = CH, the estimates of Lemma 5.1 agree with the estimates obtained by Cai [7, 8] for linear parabolic problems. In such case, Cai proved that if [tau]/[H.sup.2] is small enough, then the one-level Schwarz algorithm is scalable and the two-level algorithm satisfies an optimal constant bound. Lemma 5.1 extends these estimates to nonlinear parabolic problems and to the case of variable overlap.

The elliptic coefficients [[sigma].sub.i] are equal to 1 in Tables 6.2-6.4, while they are piecewise constant with jump discontinuities across subdomain boundaries in the last tests of Figures 6.3 and 6.4. The domain is the unit square [OMEGA] and the right-hand side g is chosen so that [u.sup.*] (t, x) = t sin([pi]x) sin([pi]y) is the exact solution when [[sigma].sub.i] = 1. We consider [t.sub.0] = 0, [u.sub.0](x) = 0, and we compute the solution for [tau] = [tau] = 0.01. The iteration process is stopped when [[parallel][r.sub.k][parallel].sub.M]/[[parallel][r.sub.0][parallel].sub.M] [less than or equal to] 1e8, and we denote the relative error by err = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Comparison between ASR and Linearly Implicit Euler methods. We start with a comparison between our ASR method (3.9) and the Linearly Implicit Euler method, consisting in applying to the original nonlinear problem (2.2) a single Newton step, see e.g. Deuflhard [14], Lang [18], and solve the resulting linear system by GMRES with the Additive Schwarz preconditioner M defined in (3.7). This method has the advantage of requiring only the solution of a linear problem per time step, but it requires the computation of the Jacobian of the nonlinear operator. We remark that the Jacobian is not needed in our ASR algorithm and it might even be practically uncomputable for some nonlinear problems, such as the monodomain and bidomain systems coupled with realistic ionic models; see Munteanu [21]. In our notations, the Linearly Implicit Euler method for the nonlinear system (3.1) B([u.sup.m]) = [??] at time step [t.sub.m] becomes:

solve the Jacobian system: [J.sup.m.sub.B] [s.sup.m] = [??] - B([u.sup.m]) by GMRES with the Additive Schwarz preconditioner M in (3.7), update the solution: [u.sup.m+1] = [u.sup.m] + [s.sup.m],

where [J.sup.m.sub.B] is the Jacobian of the nonlinear operator B at [u.sup.m]. Given our assumption (3.2) on the structure of B, this Jacobian matrix also can be written in terms of the nonlinear form b(u, v) and the mass matrix M as [J.sup.m.sub.B] = M + [tau][J.sup.m.sub.b], with [J.sup.m.sub.b] equal to the Jacobian of b at [u.sup.m].

Table 6.1 compares the two algorithms by reporting their iteration counts (iter) and MATLAB cpu times (cpu) on a PC (Acer Aspire 3680) in a scaled speed-up test, where the subdomain size H/h = 4 is kept fixed and the number of subdomains (hence nodes) is increased from 2 x 2 to 18 x 18. For both algorithms the right-hand side is chosen so that the exact solution is [u.sup.*] given above and we can determine the relative errors (err) reported in the last column of the table, that decrease proportionally to the mesh refinement (i.e., increasing subdomains) as expected. In agreement with the theory (see Remark 5.3), in the one-level case the number of iterations of both algorithms increases (much less for Linearly Implicit Euler, column 5), while in the two-level case the iteration counts remain bounded and both algorithms are scalable (with a better upper bound of 16 for Linearly Implicit Euler, column 6, than 36 for ASR, column 3). The cpu times behave accordingly, i.e., they increase strongly for the one-level algorithms and show a more moderate increase for the two-level algorithms. The most relevant comparison between the two-level algorithms shows that the ASR cpu times are initially slightly larger than the Linearly Implicit Euler cpu times, but as the problem size increases (for N [greater than or equal to] 14 x 14) the ASR times equal and then definitely improve over the Lineary Implicit Euler times (27.08 v. 37.42 sec. for N = 16 x 16 and 43.18 v. 76.17 sec. for N = 18 x 18). These results indicate that ASR can be asymptotically more efficient than Linearly Implicit Euler as the problem size and number of subdomains increase. We remark that this is only a partial indication because of the serial implementation of the two algorithms, where the subdomain problems of the Additive Schwarz preconditioners are solved sequentially; it would be much more significant to compare the parallel cpu times for the two algorithms on modern distributed computing architectures (which is beyond the scope of this paper).

ASR scalability with random RHS and [lambda] step-lenght strategy. Table 6.2 reports the results of a scaled speed-up test analogous to Table 6.1, but focuses only on the ASR algorithm with minimal overlap [delta] = h. In the left part of the table (columns 2 and 3), the parameter [lambda] is again fixed at 0.4 but the RHS is randomly distributed. In the right part of the table (column 4 and 5), [lambda] is chosen by the step-length strategy of [26] (columns 4 and 5) and the RHS is again the one associated to the exact solution [u.sup.*] given above. The results confirm that in the one-level case the number of ASR iterations (iter) increases, while in the two-level case this number remains bounded and the ASR algorithm is scalable. The steplength strategy for the selection of [lambda] yields better iteration counts (around 22 - 27 iterations) than the fixed [lambda] = 0.4 selection (around 36 iterations), but at the expense of a much larger cpu time (not shown). The results with a random right-hand side show the same scalability of the two-level ASR algorithm, only with slightly larger iteration counts (now with an upper bound of 43 iterations).

[FIGURE 6.1 OMITTED]

ASR standard speed-up. We study the ASR performance in a standard speed-up test where the global problem size is fixed (h = 1/48) and the number of subdomains is increased from 2 x 2 to 8 x 8, hence decreasing the ratio H/h. The same quantities (iter and err) of Table 6.2 are reported in Table 6.3. As predicted by the theory, only in the two-level case, the ASR iteration counts improve as the subdomain size H decreases, since the term [tau]/(Hh) dominates the one-level bound in Remark 5.3b).

ASR dependence on [lambda]. Figure 6.1 confirms the theoretical prediction of Theorem 4.7, showing the ASR iteration counts as a function of the parameter [lambda] for N = 2x2 subdomains, overlap [delta] = h, and two mesh sizes h = 1/8 (continuous line), h = 1/16 (dashed line). The explicit formula of Theorem 4.7 shows that the parabola P([lambda]) attains its minimum inside a right interval of 0 and tends to 1 at its endpoints; correspondingly, the ASR convergence rate attains a minimum inside an interval (0, [alpha]), [alpha] > 0 and degenerates at the interval endpoints.

ASR dependence on [delta]. Table 6.4 shows that the ASR iteration counts improve with increasing overlap size [delta], for both the one- and two-level ASR algorithms, in agreement with Lemma 5.1. In the two-level case, the improvement becomes irrelevant for overlap sizes larger than 3h.

[FIGURE 6.2 OMITTED]

ASR scalability dependence on [tau]. Figure 6.2 reports a different validation of the one-level bound by reducing the time-step size [tau] and performing a scaled speed-up test as in Table 6.2 (H/h fixed and small overlap [delta] = h). While we already know that for a given value of [tau] the one-level ASR algorithm is not scalable (Remark 5.3 and Table 6.2), we nevertheless expect a reduction of [tau] to give bounded iteration counts up to a critical number of subdomains [N.sub.[tau]] ("temporary" scalability) since the first term dominates the maximum in Remark 5.3a), while for N > [N.sub.[tau]] we expect increasing iteration counts since the second term dominates the maximum in Remark 5.3a). The results in Figure 6.2 show that this is indeed the case: for [tau] = 1e 3, [N.sub.[tau]] ~ 4 x 4, for [tau] = 5e - 4, [N.sub.[tau]] ~ 6 x 6 and for [tau] = 1e - 4, [N.sub.[tau]] ~ 12 x 12.

ASR performance for elliptic coefficients with jump discontinuities across subdomains. Finally, Figures 6.3 and 6.4 report the ASR results when the coefficients [[sigma].sub.i] of the linear elliptic operator are piecewise constant and present jump discontinuities across subdomain boundaries. We considered a decomposition of [OMEGA] into 7 x 7 subdomains with H/h = 4, d = h; we chose a larger tolerance tol = 1e - 4 in the stopping criterion in order to test the convergence (or lack thereof) of the unpreconditioned algorithm, up to a maximum number of iterations maxit = 3 x [10.sup.4]. We first considered a configuration where inside the 3 x 3 central subdomains i (see Figure 6.3, left) the elliptic coefficients [[sigma].sub.i] have varying values ranging from 1e 2 to 1e + 2, while they are equal to 1 in the other surrounding subdomains. The table in Figure 6.3, right, show that the two-level ASR method is unaffected by the size of the discontinuity, the one-level is almost unaffected but with iteration counts more than four times larger, and the unpreconditioned Richardson iteration essentially does not converge within maxit iterations. We also considered a second configuration where the coefficients [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] have random exponents [[alpha].sub.i] given in Figure 6.4, left, with a variation of six orders of magnitude. The two-level ASR iteration counts are the same as before (17), the one-level iteration counts are a bit better (40) and the unpreconditioned method again does not converge.

* Received December 19, 2007. Accepted for publication September 1, 2008. Published online on December 17, 2008. Recommended by T. Manteuffel. This work was supported by Istituto Nazionale di Alta Matematica Francesco Severi, Roma and by M.I.U.R. (PRIN 2004014411, 2005013982).

REFERENCES

[1] H.-B. AN, On convergence of the Additive Schwarz Preconditioned Inexact Newton Method, SIAM J. Numer. Anal., 43 (2005), pp. 1850-1871.

[2] L. BADEA, Convergence rate of Schwarz multilevel method for the constrained minimization of nonquadratic functionals, SIAM J. Numer. Anal., 44 (2006), pp 449-477.

[3] L. BADEA, X.-C. TAI, AND J. WANG, Convergence rate analysis of a multiplicative Schwarz method for variational inequalities, SIAM J. Numer. Anal., 41 (2003), pp 1052-1073.

[4] I. BOGLAEV,Monotone iterative algorithms for a nonlinear singularly perturbed parabolic problem, J. Comput. Appl. Math., 172 (2004), pp 313-335.

[5] D. BRAESS, Finite Elements. Theory, Fast Solvers, and Applications in Solid Mechanics, Cambridge University Press, Cambridge, 2001.

[6] J. H. BRAMBLE AND J. XU, Some estimates for a weighted [L.sup.2] projection, Math. Comp., 56 (1991), pp. 463-476.

[7] X.-C. CAI, Additive Schwarz algorithms for parabolic convection-diffusion equations, Numer. Math., 60 (1991), pp. 41-61.

[8] X-C. CAI, Multiplicative Schwarz methods for parabolic problems, SIAM J. Sci. Comput., 15 (1994), pp. 587-603.

[9] X-C. CAI AND M. DRYJA, Domain decomposition methods for monotone nonlinear elliptic problems, in Seventh International Conference on Domain Decomposition Methods in Scientific and Engineering Computing, D. E. Keyes and J. Xu, eds., Contemp. Math., Vol. 180, American Mathematical Society, Providence, RI, 1994, pp. 21-27.

[10] X-C. CAI, W. D. GROPP, D. E. KEYES, R. G. MELVIN, AND D. P. YOUNG, Parallel Newton-Krylov-Schwarz algorithms for the transonic full potential equation, SIAM. J. Sci. Comput., 19 (1998), pp. 246-265.

[11] X-C. CAI, W. D. GROPP, D. E. KEYES, AND M. D. TIDRIRI, Newton-Krylov-Schwarz methods in CFD, in Proceedings of the International Workshop on Numerical Methods for the Navier-Stokes Equations, Vieweg, Braunschweig, 1995, pp. 183-200.

[12] X-C. CAI AND D. E. KEYES, Nonlinearly preconditioned inexact Newton algorithms, SIAM. J. Sci. Comput., 24 (2002), pp. 183-200.

[13] P. COLLI FRANZONE AND L. F. PAVARINO.A parallel solver for reaction-diffusion systems in computational electrocardiology, Math. Models Methods Appl. Sci., 14 (2004), pp. 883-911.

[14] P. DEUFLHARD, Uniqueness theorems for stiff ODE initial value problems, in Numerical Analysis 1989, D. F. Griffiths and G. A. Watson, eds., Pitman Research Notes in Mathematics Series 228, Longman, 1990, pp. 74-88.

[15] M. DRYJA AND W. HACKBUSH, On the nonlinear domain decomposition method, BIT, 37 (1997), pp. 296-311.

[16] M. DRYJA AND O. B. WIDLUND, Domain decomposition algorithms with small overlap, SIAM J. Sci. Comput., 15 (1994), pp. 604-620.

[17] F-N. HWANG AND X-C. CAI, A parallel nonlinear additive Schwarz preconditioned inexact Newton algorithm for incompressible Navier-Stokes equations, J. Comput. Phys., 204 (2005), pp. 666-691.

[18] J. LANG, Adaptive Multilevel Solution of Nonlinear Parabolic PDE Systems. Theory, Algorithm, and Applications. Lect. Notes Comput. Sci. Eng., Vol. 16, Springer, Berlin, 2000.

[19] S-H. LUI, On linear monotone iteration and Schwarz methods for nonlinear elliptic PDEs, Numer. Math., 93 (2002), pp. 109-129.

[20] S-H. LUI, On monotone iteration and Schwarz methods for nonlinear parabolic PDEs, J. Comput. Appl. Math., 161 (2003), pp. 449-468.

[21] M. MUNTEANU, Overlapping additive Schwarz methods for nonlinear parabolic reaction-diffusion problems, Ph.D. Thesis, Dept. of Mathematics, University of Milano, 2008.

[22] M. MUNTEANU AND L. F. PAVARINO, Implicit parallel solvers in computational electrocardiology. in Applied Analysis and Differential Equations, O. Carja and I. I. Vrabie, eds., World Scientific, 2007, pp. 255-266.

[23] M. MUNTEANU AND L. F. PAVARINO, An Overlapping Additive Schwarz-Richardson Method for Monotone Nonlinear Parabolic Problems, in Domain Decomposition Methods in Science and Engineering XVII, U. Langer et al., eds., Lect. Notes Comput. Sci. Eng., Vol. 60, Springer, Berlin, 2008, pp. 599-606.

[24] M. MUNTEANU AND L. F. PAVARINO, Decoupled Schwarz algorithms for implicit discretization of nonlinear monodomain and bidomain systems, Math. Models Methods Appl. Sci., 19 (2009), to appear.

[25] M. MURILLO AND X-C. CAI, A fully implicit parallel algorithm for simulating the non-linear electrical activity of the heart, Numer. Linear Algebra Appl., 11 (2004), pp. 261-277.

[26] J. NOCEDAL AND S. J. WRIGHT, Numerical Optimization, Springer, New York, 1999.

[27] S. OVTCHINNIKOV AND X-C. CAI, One-level Newton-Krylov-Schwarz algorithm for unsteady non-linear radiation diffusion problem, Numer. Linear Algebra Appl., 10 (2004), pp. 867-881.

[28] L. F. PAVARINO AND S. SCACCHI, Multilevel additive Schwarz preconditioners for the bidomain reaction-diffusion system, SIAM J. Sci. Comput., 31 (2008), pp. 420-443.

[29] B. F. SMITH, P. E. BJORSTAD, AND W. D. GROPP, Domain Decomposition. Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press, Cambridge, 1996.

[30] J. SUNDNES, G. T. LINES, X. CAI, B. F. NIELSEN, K.-A. MARDAL, AND A. TVEITO, Computing the Electrical Activity of the Heart, Springer, Berlin, 2006.

[31] X-C. TAI AND M. ESPEDAL, Rate of convergence of some space decomposition methods for linear and nonlinear problems, SIAM J. Numer. Anal., 35 (1998), pp. 1558-1570.

[32] X-C. TAI AND M. ESPEDAL, Applications of a space decomposition method to linear and nonlinear elliptic problems, Numer. Methods Partial Differential Equations, 14 (1998), pp. 717-73.

[33] A. TOSELLI AND O. WIDLUND, Domain Decomposition Methods-Algorithms and Theory, Springer, Berlin, 2005.

[34] J. XU AND X-C. CAI, A preconditioned GMRES method for nonsymmetric or indefinite problems, Math. Comp., 59 (1992), pp. 311-319.

[35] A. ZENISEK, Nonlinear elliptic and evolution problems and their finite element approximations, Academic Press, London, 1990.

[36] X. ZHANG, Multilevel Schwarz methods, Numer. Math., 63 (1992), pp. 521-539.

M. MUNTEANU ([dagger]) AND L. F. PAVARINO ([dagger])

([dagger]) Department of Mathematics, Universita di Milano, Via Saldini 50, 20133 Milan, Italy ({Marilena.Munteanu,Luca.Pavarino}@mat.unimi.it).
TABLE 6.1

Comparison of ASR and Linearly Implicit Enter methods (GMRES with
AS preconditioner): scaled speed-up test with fixed subdomain size
H/h = 4, small overlap size 6 = h, and increasing number of subdomains
N (and nodes). iter = iteration counts, cpu = cpu times, err = relative
errors with exact solution.

 Lin. Impl. Euler:
 ASR with [lambda] = 0.4 GMRES with AS prec.

 one-level two-levels one-level

N iter cpu iter cpu iter cpu

2 x 2 40 0.07 43 0.07 10 0.09
4 x 4 70 0.57 36 0.29 17 0.15
6 x 6 123 2.88 35 0.87 20 0.59
8 x 8 197 11.20 36 2.15 23 1.76
10 x 10 293 36.80 36 4.61 26 4.48
12 x 12 410 99.12 36 9.07 29 11.31
14 x 14 549 236.93 36 16.25 31 29.12
16 x 16 709 511.79 36 27.08 34 77.29
18 x 18 891 1013.27 36 43.18 36 162.50

 Lin. Impl. Euler:
 GMRES with AS prec.

 one-level,
 rest = 20 two-levels

N iter cpu iter cpu err

2 x 2 10 0.10 11 0.07 6.76e-3
4 x 4 17 0.20 16 0.15 1.67e-3
6 x 6 20 0.84 17 0.49 7.44e-4
8 x 8 20+5 2.93 16 1.26 4.18e-4
10 x 10 20+7 7.78 16 3.02 2.67e-4
12 x 12 20+9 18.54 16 6.63 1.86e-4
14 x 14 20+14 51.33 16 15.69 1.36e-4
16 x 16 20+16 128.71 16 37.42 1.04e-4
18 x 18 20+18 188.71 16 76.17 8.26e-5

TABLE 6.2

ASR scaled speed-up test with fixed subdomain size H/h = 4, small
overlap size [delta] = h, and increasing number of subdomains N
(and nodes): ASR with fixed [lambda] = 0.4 and random RHS (second
and third columns); ASR with step-lenght strategy for [lambda] and
exact solution (fourth and fifth columns). iter = iteration counts,
err = relative errors with exact solution.

 ASR with [lambda] = 0.4 ASR with step-length strategy
 random RHS for [lambda] RHS exact solution

 one-level two-levels one-level

N iter iter iter err

2 x 2 40 42 25 6.76e-3
4 x 4 70 38 37 1.67e-3
6 x 6 122 39 69 7.44e-4
8 x 8 196 40 117 4.18e-4
10 x 10 291 42 157 2.67e-4
12 x 12 407 41 223 1.86e-4
14 x 14 544 42 -- --
16 x 16 703 43 -- --
18 x 18 882 43 -- --

 ASR with step-length strategy
 for [lambda] RHS exact solution

 two-levels

N iter err

2 x 2 24 6.76e-3
4 x 4 25 1.67e-3
6 x 6 24 7.44e-4
8 x 8 24 4.18e-4
10 x 10 27 2.67e-4
12 x 12 22 1.86e-4
14 x 14 25 1.36e-4
16 x 16 23 1.04e-4
18 x 18 24 8.26e-5

TABLE 6.3

ASR standard speed-up test with fixed mesh size h = 1/48, small overlap
size [delta] = h, and increasing number of subdomains N (of decreasing
size H/h). ASR with fixed [lambda] = 0.4 (second and third columns);
ASR with step-lenght strategy for [lambda] (fourth and fifth columns).
iter = iteration counts, err = relative errors with exact solution.

 [lambda] = 0.4

 one-level two-levels

N iter err iter err

2 x 2 155 1.74e-4 70 1.74e-4
4 x 4 192 1.74e-4 58 1.74e-4
6 x 6 245 1.74e-4 47 1.74e-4
8 x 8 301 1.74e-4 41 1.74e-4

 [lambda]: step-length strategy

 one-level two-levels

N iter err iter err

2 x 2 86 1.74e-4 43 1.74e-4
4 x 4 114 1.74e-4 32 1.74e-4
6 x 6 149 1.74e-4 27 1.74e-4
8 x 8 -- -- 23 1.74e-4

TABLE 6.4

Effect of increasing the overlap size 6 in one- and two-level ASR
methods for fixed mesh size h = 1/48, number of subdomains N = 2
x 2, [lambda] = 0.4 iter = iteration counts, err = relative errors
with exact solution.

 one-level two-levels
overlap
size [delta] iter err iter err

h 155 1.74e-4 70 1.74e-4
2h 82 1.74e-4 46 1.74e-4
3h 59 1.74e-4 37 1.74e-4
4h 49 1.74e-4 37 1.74e-4

FIG. 6.3. Iteration counts of one- and two-level ASR method with
[lambda] = 0.4 for a test problem with discontinuous coefficient
[[sigma].sub.i] in the linear elliptic operator; the domain is
decomposed into N = 7 x 7 subdomains (left panel, with values
of [[sigma].sub.i] indicated), H/h = 4, tol = 1e - 4

1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 [[sigma].sub.i] [[sigma].sub.i] [[sigma].sub.i] 1 1
1 1 [[sigma].sub.i] [[sigma].sub.i] [[sigma].sub.i] 1 1
1 1 [[sigma].sub.i] [[sigma].sub.i] [[sigma].sub.i] 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1

 one-level two-levels no prec
[[sigma].sub.i] iter iter iter

[10.sup.-2] 63 17 --
[10.sup.-1] 66 17 --
1 77 17 29818
10 76 17 --
[10.sup.2] 72 17 --

FIG. 6.4. Iteration counts of one- and two-level ASR method with
[lambda] = 0.4 for a test problem with random discontinuous
coefficient [[sigma].sub.i] in the linear elliptic operator; the
domain is decomposed into N = 7 x 7 subdomains (left panel), with
indicated the values of the exponents [[alpha].sub.i] in the
coefficients [[sigma].sub.i] = [MATHEMATICAL EXPRESSION NOT
REPRODUCIBLE IN ASCII], H/h = 4, tol = 1e - 4

 0 -3 1 0 -1 2 0
-2 2 0 1 -3 3 0
 1 0 -2 2 3 2 1
 2 -3 2 0 2 1 -3
 3 0 1 2 0 1 3
-3 1 0 3 -3 3 0
 0 -1 1 2 -2 3 -3

one level two levels
iter iter

40 17
COPYRIGHT 2008 Institute of Computational Mathematics
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2008 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Munteanu, M.; Pavarino, L.F.
Publication:Electronic Transactions on Numerical Analysis
Article Type:Report
Geographic Code:4EUIT
Date:Jan 1, 2008
Words:8459
Previous Article:Parameter-uniform fitted operator B-spline collocation method for self-adjoint singularly perturbed two-point boundary value problems.
Next Article:On the calculation of approximate Fekete points: the univariate case.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |