Local and parallel finite element algorithms based on two-grid discretizations

By Jinchao Xu and Aihui Zhou

Abstract

A number of new local and parallel discretization and adaptive finite element algorithms are proposed and analyzed in this paper for elliptic boundary value problems. These algorithms are motivated by the observation that, for a solution to some elliptic problems, low frequency components can be approximated well by a relatively coarse grid and high frequency components can be computed on a fine grid by some local and parallel procedure. The theoretical tools for analyzing these methods are some local a priori and a posteriori estimates that are also obtained in this paper for finite element solutions on general shape-regular grids. Some numerical experiments are also presented to support the theory.

1. Introduction

In this paper, we will propose some new parallel techniques for finite element computation. These techniques are based on our understanding of the local and global properties of a finite element solution to some elliptic problems. Simply speaking, the global behavior of a solution is mostly governed by low frequency components while the local behavior is mostly governed by high frequency components. The main idea of our new algorithms is to use a coarse grid to approximate the low frequencies and then to use a fine grid to correct the resulted residue (which contains mostly high frequencies) by some local/parallel procedures.

Let us now give a somewhat more detailed but informal (and hopefully informative) description of the main ideas and results in this paper. We consider the following very simple model problem posed on a convex polygonal domain :

The main philosophy behind this paper is that we should treat phenomena of different scales by different tools. In multigrid and domain decomposition methods, this kind of idea is used to devise iterative methods for solving a given discretization scheme (see e.g. Bank Reference 10, Bramble Reference 19, Chan and Mathew Reference 22, Hackbusch Reference 31, Xu Reference 49 and Yserentant Reference 53); while in our approach, we try to use this type of idea for designing discretization schemes. The two-grid method proposed by the first author Reference 48Reference 50Reference 51 (and later further investigated by many others such as Reference 3Reference 16Reference 24Reference 25Reference 33Reference 34Reference 42) is a result of such a consideration. The two-grid method is based on the observation that, for an equation like Equation 1.1, the symmetric positive definite leading term dominates the equation on high frequencies, while the low frequencies, as in a multigrid method, can be well approximated by a relatively coarse grid. Therefore, by first approximating the equation on a coarse grid, say , we can then correct the residue (in which high frequencies dominate) on a finer grid, say , by ignoring the lower order term and solving the resulting symmetric positive definite system.

For elliptic problems, the low frequencies are more global, while the high frequencies are more local. This fact is crucial in the multigrid methodology, in which high frequency errors are damped out by local relaxation techniques while low frequencies are handled by coarse grids. If we consider this fact more carefully, we can then imagine that if we first approximate the equation Equation 1.1 on a coarse grid , the residue which is dominated by high frequencies can then be resolved locally. This is precisely the central idea of the new algorithms in this paper, and is based on the local behavior of finite element approximations presented in Section 3.

One technical tool for motivating this idea is the local error estimate for finite element approximations. Let be a finite element approximation to Equation 1.1 on a quasi-uniform grid . Then the following kind of local error estimate holds (see Theorem 3.4):

where is the finite element space associated with and (here means that ).

At first glance, this type of estimate does not appear to be clearly related to what we said above, but we shall soon explain the connection. The above kind of estimate is available in the literature for quasi-uniform grids (see Nitsche and Schatz Reference 35, Schatz Reference 38, Schatz and Wahlbin Reference 39Reference 40 and Wahlbin Reference 46Reference 47), but we need them on locally refined grids with different mesh scales, which were also discussed in Reference 54 for local quasi-uniform grids. We are indeed able to extend these estimates to very general grids, which is one technical part of this paper—see Section 3.

Now we consider a very special grid that is obtained by refining a given coarse grid for the region , and obtain a locally refined grid with mesh size in and size away from (see Figure 1). Let us for example consider linear finite element discretizations on this grid. Then, by Equation 1.2 and some well-known finite element error estimates, we obtain (see Corollary 3.5)

This estimate means that we can obtain an asymptotically optimal error in the norm locally by taking .

With this basic result, it is then not difficult to devise a parallel algorithm on a fine grid by using a collection of overlapped subdomains. See Section 4.

In the above approach, all the “local” solvers need to be coupled with the global coarse grid in some way. We can actually improve the above procedure by using a residue-correction technique used in Xu Reference 48Reference 50Reference 51. One prototype algorithm is as follows (see Section 4):

(1)

Solve on a coarse grid: Find such that

(2)

Correct the residue (with SPD part only) on a fine grid: Find such that

In this algorithm, a coarse grid problem only needs to be solved once and it does not have to be coupled with the subsequence of parallel local solvers. For the above algorithm, we can still establish the following result (see Theorem 4.3):

This is a very satisfying result in many ways. As a consequence, for example, we can then design the following type of parallel algorithms: first solve the problem on a coarse grid, and then correct the residue in parallel on a collection of overlapped subdomains on a fine grid.

In practical finite element computations, it is desirable to carry out the finite element computations in an adaptive fashion, cf. Ainsworth and Oden Reference 2, Babuška, Duran and Rodriguez Reference 4, Babuška and Rheinboldt Reference 5, Babuška, Zienkiewick, Gago and Oliveira Reference 6, Bank and Weiser Reference 15, Johnson Reference 32 and Verfürth Reference 45. A typical procedure is first to start with a coarse grid and then use some a posteriori estimates as a guidance to properly refine the mesh to achieve the desired accuracy. In the existing literature, a posteriori error estimates are often obtained globally, but in practical applications, they are often used locally (see e.g. Reference 2Reference 4Reference 5Reference 14Reference 26Reference 27Reference 28Reference 36Reference 43Reference 44Reference 45 and references cited therein). In this paper, we shall also present some local a posteriori error estimates that would give a certain justification of the local application of the a posteriori estimates. For example, we shall prove the following type of local a posteriori estimate on a general grid (see Theorem 3.9):

where is the usual a posteriori estimator on the domain . Again we notice that the global term in the above estimate is a high order term.

More important, based on a posteriori estimates like Equation 1.5 and a priori estimates like Equation 1.2, we are able to design an adaptive procedure that can be carried locally in a given subdomain and hence in parallel. We believe this type of parallel adaptive techniques will have great implications in practical parallel computations.

The rest of the paper is organized as follows. In Section 2, some preliminary materials are provided. In Section 3, a number of local a priori and a posteriori error estimates are obtained for finite element discretizations on general shape regular grids. Based upon these local error estimates, several new local/parallel algorithms are devised and analyzed in Section 4, and local and parallel adaptive processes are discussed in Section 5. In Section 6, some numerical experiments, which support our theory, are reported. Finally in Section 7, some further remarks are presented.

2. Preliminaries

In this section, we shall describe some basic notation and basic assumptions on the finite element spaces, and then study properties of the finite element approximation to a general linear second order elliptic boundary value problem.

Let be a bounded domain in . We shall use the standard notation for Sobolev spaces and their associated norms and seminorms, see e.g. Reference 1Reference 23. For , we denote and , where is in the sense of trace, and . (In some places of this paper, should be viewed as piecewise defined, if necessary.) The space , the dual of , will also be used.

For , we write to mean that , see Figure 2.

Throughout this paper, we shall use the letter C (with or without subscripts) to denote a generic positive constant which may stand for different values at its different occurrences. For convenience, following Reference 49, the symbols and will be used in this paper. Specifically, and mean that and for some constants and that are independent of the mesh parameters.

Note that any can be naturally extended to be a function in with zero outside of . We shall state this fact by the slightly abused notation .

2.1. Finite element spaces

For generality, we will not concentrate on any specific finite element space, rather we shall study a class of finite element spaces that satisfy certain assumptions. We now describe those assumptions.

Assume that is a mesh of with mesh-size function whose value is the diameter of the element containing . One basic assumption on the mesh is that it is not exceedingly over-refined locally, namely

A.0. There exists such that

where is the (largest) mesh size of .

This is apparently a very mild assumption, and most practical meshes should satisfy it. Sometimes, we will drop the subscript in , writing for the mesh size on a domain that is clear from the context.

Associated with a mesh , let be a finite dimensional subspace on and . Given , we define and to be the restriction of and to , and

For any mentioned in this paper, we assume that it aligns with when necessary.

We now state our basic assumptions on the finite element spaces.

A.1. Approximation. If , then as ,

A.1. Approximation. There exists such that for ,

A.2. Inverse Estimate. For any ,

A.3. Superapproximation. For , let with supp . Then for any , there is such that

A.4. Trace. For any ,

A.5. Fractional Norm. For any ,

Next we shall give an example of finite element spaces. The assumptions mentioned above are satisfied by most of the finite element spaces used in practice. We shall now briefly describe a special but popular finite element space for illustration. For simplicity, let us assume that is a polygonal domain. Let consist of shape-regular simplices and define to be a space of continuous functions on such that for restricted to each is a polynomial of total degree , namely

where is the space of polynomials of degree not greater than a positive integer . These are the Lagrange finite element spaces, and they satisfy all the above assumptions.

The approximation assumptions A.1 and A.1 are well-known for the Lagrange finite element spaces. A.2 and A.4 are well-known and they can be easily proven by a standard scaling argument. The superapproximation assumption has been discussed in many papers, cf. Reference 35Reference 39Reference 40Reference 46Reference 47. This superapproximation assumption can be easily verified for the Lagrange finite element spaces Equation 2.8, using a locally defined interpolation operator satisfying

where denotes the semi-norm involving only derivatives. Setting in Equation 2.9 and noting that derivatives of vanish, and using the inverse estimates, one obtains Assumption A.3.

The verification of A.5 can go as follows. For , let be the unique function satisfying

Then is discrete harmonic. The desired result then follows from the following well-known (cf. Reference 52) estimate for discrete harmonic functions:

2.2. A model problem

In this subsection, we shall study some basic properties of general second order elliptic boundary value problems and their finite element approximations. We consider the homogeneous boundary value problem

Here is a general linear second order elliptic operator:

satisfying , and is uniformly positive definite on .

The weak form of (Equation 2.10) is as follows: Find such that

where is the standard inner-product of and

with

Note that

and

Our basic assumption is that (Equation 2.11) is well-posed, namely (Equation 2.11) is uniquely solvable for any . (A simple sufficient condition for this assumption to be satisfied is that .) An application of the open-mapping theorem yields

It is easy to see that if satisfies the above assumption and the above estimates, so does its formal adjoint

A sufficient and necessary condition for the well-posedness of (Equation 2.11) is that

and

We have (cf. Reference 30) the following estimate for the regularity of the solution of (Equation 2.10) or (Equation 2.11):

for some depending on and the coefficients of .

For some , we need the following assumption.

R(G). For any , there exists a satisfying

and

It is well-known (cf. Reference 51) that if (depending on ) and Assumption A.1 holds, then

and

Throughout this paper, we will assume that (when ) and Assumption A.1 holds, so that the above two estimates hold. From the above two estimates, we can then define Galerkin-projections and by

and apparently

From (Equation 2.17), various a global priori error estimates can be obtained from the approximate properties of the finite element subspaces (cf. Reference 23). Particularly, by Assumption A.1, if , then

Now we introduce the following quantity:

where

Similarly, if Assumption R(G) holds, we can define well.

Lemma 2.1.

Assume that and Assumption A.1 holds. Then

and

Proof.

Let . For any , we have

Thus, (Equation 2.13) and (Equation 2.17) yield

which produce (Equation 2.19).

To prove (Equation 2.20), we use the Aubin-Nitsche duality argument. For each , let . Then

Note that

We get (Equation 2.20) from combining (Equation 2.22), the above inequalities, and

Lemma 2.2.

Assume that and Assumption A.1 holds. Then as . Moreover,

provided

Proof.

It is easy to see that is compact. Hence, is a compact and continuous mapping. Since

we get

which implies as .

(Equation 2.23) is immediately obtained from (Equation 2.21), (Equation 2.15) and (Equation 2.24).

Remark 2.3.

We would like to point out that the first part of Lemma 2.2 generalizes Reference 33.

3. Local a priori and a posteriori error estimates

In this section, we shall present a number of local a priori and a posteriori error estimates for finite element discretizations on general shape regular grids. Novelties of our estimates lie in, for example, the weak assumption on the underlying grids as well as the generality of model continuous problems. Although these general estimates are theoretically interesting in their own right, our main motivation is to use them to devise and analyze some new local/parallel methods to be presented in the following sections.

3.1. Local a priori error estimates

The results presented here generalize local a priori error estimates known in the literature Reference 35Reference 39Reference 40Reference 46Reference 47Reference 54 to more general second order differential equations and more general finite element meshes.

First, we need the following technical result.

Lemma 3.1.

Let , and let be such that supp . Then

Proof.

From the identity

we get

Note that

and

so we have

An application of a kick-back argument then leads to (Equation 3.1).

We shall now present a local a priori estimate for finite element approximation that will play a crucial role in our analysis. This type of estimates can be found in Reference 35Reference 39Reference 40Reference 46Reference 47; a new feature here is the generality of the underlying finite element grid for which this estimate is proven valid.

Lemma 3.2.

Suppose that and . If Assumptions A.0, A.2 and A.3 hold and satisfies

then

where

Proof.

Let be an integer such that , and let satisfy

Choose satisfying and such that on and supp . Then, from Assumption A.3, there exists such that

which implies

and

Since , (Equation 3.2) implies

Hence, combining (Equation 3.1), (Equation 3.5), (Equation 3.6) and (Equation 3.7), we have

or

The argument may be repeated for on the right to yield

Combining (Equation 3.8) and (Equation 3.9), we get from Assumptions A.0 and A.2

This completes the proof.

The local stability of the Galerkin-projection is stated as follows.

Theorem 3.3.

Let and . If Assumptions A.0, A.1, A.2 and A.3 hold, then

Proof.

Let be the Galerkin projection, i.e., for

Choose satisfying and such that on and supp . Then for ,

Thus, Lemma 3.2 yields

Therefore, estimates similar to (Equation 2.17) lead to

Thus, we obtain (Equation 3.11). This completes the proof.

Theorem 3.4.

Let and . If Assumptions A.0, A.1, A.2 and A.3 hold, then

or

Proof.

Note that for any , we get from Theorem 3.3,

which leads to (Equation 3.15). And (Equation 3.16) is derived from (Equation 3.15) and Lemma 2.1. This completes the proof.

Corollary 3.5.

Let , and . If Assumptions A.0, A.1, A.2 and A.3 hold, then

Remark 3.6.

The results above show that many refined finite element meshes can be locally employed.

Remark 3.7.

Similar results hold for .

3.2. Local a posteriori error estimates

In this section, we shall present local a posteriori error estimate in energy-norm. First, we need the following technical result.

Lemma 3.8.

Let , and let be such that supp . Then

Proof.

From the identity

we immediately obtain (Equation 3.18).

To state the a posteriori estimates, we need some more notation. Let be the set of all the interior faces of the mesh , and For each , let be a unit vector normal to , and define for

Namely, is the jump across in the normal component of . We now introduce by

One sees that and are computable in terms of the finite element solution .

Theorem 3.9.

Let and . If Assumptions A.1, A.3 and A.4 hold, then

or

Proof.

Choose satisfying and such that on and supp . Thus, from Lemma 3.8, we have

where .

Note that for any ,

and for any , there exists such that . Thus Assumption A.4 implies that

Thus, we get, for any ,

which together with Assumptions A.1 and A.3 yields

Therefore, (Equation 2.13) and (Equation 3.22) lead to

which implies (Equation 3.20).

Remark 3.10.

In (Equation 3.20) or (Equation 3.21), the last term is of higher order and hence negligible. If, for example, (Equation 2.15) holds with , one has the following a posterior error estimates, see e.g. Reference 26Reference 28:

under additional assumptions. Moreover,

are globally equivalent to the errors and , respectively, cf. e.g. Reference 4Reference 26Reference 27Reference 28Reference 36Reference 44Reference 45 and reference cited therein. Similar arguments show that is essentially controlled by This means that we essentially have

Remark 3.11.

The argument here easily extends to other boundary conditions, provided the problems are well-posed.

4. New local and parallel algorithms

In this section we shall present some new local and parallel finite element algorithms. These algorithms are motivated by the local error estimates studied in the previous section. We shall first discuss the local algorithms. The generalization of the local algorithms to parallel algorithms is straightforward.

For clarity, let be a polygonal domain and be a finite element subspace of degree associated with a grid . Let be the solution of the standard finite element scheme for solving (Equation 2.11):

Either locally or globally, with proper regularity assumption, we have the following error estimate:

With this type of error estimates in mind, in the rest of this section, we will only compare the approximate solutions from our new algorithms with instead of the exact solution .

4.1. Local algorithms

The local algorithms we shall now present can be used to obtain approximate solution on a given subdomain, mostly by local computation. The main idea is that the more global component of a finite element solution may be obtained by a relatively coarser grid, and the rest of the computation can then be localized.

Roughly speaking, our new algorithms will be based on sometimes one coarse grid of size and one fine grid of size , and sometimes on a grid that is fine in a subdomain and coarse on the rest of the domain. The fine grid may be only defined locally. In our analysis, we shall use an auxiliary fine grid, say , that is globally defined. One basic assumption for this auxiliary fine grid is that it should coincide with the local fine grid in the subdomain of interest.

Let be a shape-regular coarse grid, of size , so that the highly locally refined mesh can be obtained, where is a slightly larger subdomain containing a subdomain (namely ), see Figure 3. More precisely, we let denote a locally refined shape-regular mesh that may be viewed as being obtained by refining locally around the subdomain in such a way that . We are interested in obtaining the approximation solution in the given subdomain with an accuracy comparable to that from . We shall propose two different gridding strategies for obtaining finite element approximations on the subdomain (see Figure 4). We denote the corresponding finite element space by , which consists of piecewise polynomial of degree less than or equal to in this section.

4.1.1. First approach

The first strategy is simply to solve a standard finite element solution in .

Algorithm A0.Find such that

Strictly speaking, this algorithm is still a global algorithm as a global problem is solved. But it is designed to obtain a local approximation in the subdomain and it makes use of a mesh that is much coarser away from .

Theorem 4.1.

Assume that is obtained by Algorithm A0. Then

Proof.

By the definition of Algorithm A0 and our assumption on the auxiliary grid that coincides with on , we have

By Lemma 3.2, we get

and then finish the proof.

We would like to remark here that similar locally refined grids have been used for different purposes in the literature, cf. Bramble Reference 19, Bramble, Ewing, Parashkevov and Pasciak Reference 20, and Bramble, Ewing, Pasciak and Schatz Reference 21.

4.1.2. Second approach

Our second strategy is in a way an improvement of the first strategy. In this strategy, we first solve a global problem only on the given coarse grid , and we then correct the residue locally on the fine mesh . Let be the finite element space of degree defined on .

A prototype of our new local algorithms is as follows.

Algorithm B0. 1. Find a global coarse grid solution :

2. Find a local fine grid correction :

3. Update: .

Theorem 4.2.

Assume that is obtained by Algorithm B0, and Assumption holds. Then

Proof.

By the definition of Algorithm B0,

By Lemma 3.2, we get

To estimate , we use the Aubin-Nitsche duality argument. Given any , there exists such that

Let and satisfy

Then

It follows that

which implies

The desired result then follows.

Following the basic idea in Xu Reference 48Reference 50Reference 51, for non-SPD problems Algorithm B0 may be modified in such a way that the local fine grid correction in Algorithm B0 is only carried out for the symmetric positive definite leading part of the equation.

Algorithm C0. 1. Find a global coarse grid solution :

2. Find a local fine grid correction :

3. Update: .

Theorem 4.3.

Assume that is obtained by Algorithm C0. Then

Proof.

By the definition of Algorithm C0,

Thus, by Lemma 3.2, we obtain

The rest of the proof is similar to that of Theorem 4.2, and we leave the details to the interested readers.

4.2. New parallel algorithms based on local algorithms

The parallel algorithms we shall present here are naturally obtained from the local algorithms that we studied above. Given an initial coarse triangulation , let us first divide into a number of disjoint subdomains (see Figure 5), then enlarge each to obtain that align with . The basic idea of our parallel algorithm is very simple: we just apply the local algorithms in parallel in all ’s.

4.2.1. Basic parallel algorithms

Let us first discuss the parallel version of Algorithm A0. For each , we use some adaptive process to obtain a shape-regular mesh and the corresponding finite element solution denoted by . We note that each looks like the mesh depicted in Figure 1, and it has a substantially finer mesh inside . We note that all are different triangulations for and they can be very arbitrary; but for simplicity of exposition, we assume each has the same size in (more precisely, ) and has the size away from . Let be the corresponding finite element spaces.

Algorithm A1. 1. Find in parallel:

2. Set , in .

Define a piecewise norm

By Theorem 4.1, we have

Consequently,

We now discuss the parallel versions of Algorithms B0 and C0. Although there are many possibilities for the generalization, for clarity of exposition, it appears to be most convenient to discuss these using two globally defined grids: an initial coarse grid and a refined (from ) grid that satisfies .

Algorithm B1. 1. Find a global coarse grid solution :

2. Find local fine grid corrections in parallel:

3. Set

By Theorem 4.2, for this algorithm, we apparently have the following result.

Theorem 4.4.

Assume that is the solution obtained by Algorithm B1 and Assumptions hold for . Then

and

Proof.

Note that

The desired result follows.

Algorithm C1. 1. Find a global coarse grid solution :

2. Find local fine grid corrections in parallel:

3. Update: , in

For this algorithm, we have

Theorem 4.5.

Assume that is the solution obtained by Algorithm C1. Then

and

4.2.2. Further modifications

We note that the approximations obtained by Algorithms A1, B1 and C1 are piecewise defined and they are in general discontinuous. We also point out that does not in general have higher order than . In this subsection, we shall propose some further modifications for these algorithms to achieve the following two goals:

(1)

smooth to obtain a global approximation;

(2)

improve the error .

The first goal will be achieved by using some more local fine grid problems; the second will be achieved by carrying out a further global coarse grid correction. We note that the second goal is realized after the first goal has been achieved.

We now proceed to present a modified algorithm that addresses both of the aforementioned two issues. To do this, we pick another sequence of subdomains and (see Figure 6).

Algorithm C2. 1. Find a global coarse grid solution :

2. Find local fine grid corrections in parallel:

3. Set , in and on is defined by and satisfying

4. Find a further coarse grid correction :

5. Update:

In the above algorithm, Step 3 is for obtaining a global solution and Step 4 is for improving the error.

For the analysis of the above algorithm, we need an additional assumption on the finite element space.

Theorem 4.6.

Assume that is the solution obtained by Algorithm C2 and Assumption A.5. Then

and

Proof.

From the definition, we have

Let

then

Thus, for any

and

From Assumption A.5, we have

Using

or

we get

Thus

namely,

which together with Theorem 4.5 and

finishes the proof.

5. Local and parallel adaptive process

The local error estimates and local/parallel algorithms presented in previous sections make it possible to design many new local and parallel adaptive algorithms for finite element computations. In this section, we shall give some examples.

5.1. On the traditional adaptive process

Before we present our new local and parallel adaptive method, we would like to recall some traditional finite element adaptive process based on a posteriori error estimates. We would like to illustrate that our local a posteriori error estimates give a certain theoretical justification of some traditional finite element adaptive techniques.

The basic idea of an adaptive algorithm is to use a given computed finite element solution to detect the behavior of the exact solution so that the underlying finite element meshes can get properly refined or de-refined in certain regions of the domain according to the behavior of the solution. The behavior of the solution is detected by using certain a posteriori error estimates like the ones presented in §3.2. In the existing literature, these a posteriori error estimates are often given and analyzed in a global form. For example, in view of Equation 3.19, one can often use the following kind of global a posteriori error estimate:

The constant only depends on the shape of the grids, and it may be properly estimated, or, for simplicity, one may take . In practice, we wish to find a mesh (with least possible number of nodes) such that the corresponding finite element approximation satisfies

for a given a tolerance error .

Using, for example, Equation 5.1, it suffices to refine the mesh in such a way that

If the above estimate is satisfied for the given mesh, then we have achieved our goal. Otherwise, we need to further refine the mesh locally. In order to use the global error estimate for local mesh refinement, one often uses the principle of equi-distribution for the error. Let be the total number of elements. For each element, we then check if the following is satisfied:

Here is the averaged error on obtained by the aforementioned equi-distribution principle.

One natural question to ask is why a global a posteriori error estimate like Equation 5.1 can be used locally as in Equation 5.3. We would like to argue that our local estimates would give a theoretical justification of the aforementioned local application of a posteriori error estimates. One argument we can make is that the a posteriori error estimate itself is essentially local, according to Theorem 3.9. Another related argument can be based on the locality of a priori error estimates for according to Theorem 3.4.

5.2. A local adaptive process

The locality of both a priori and a posteriori error estimates can be used to devise some local/parallel adaptive algorithms. As an example, we shall now propose a local adaptive algorithm that can be used to obtain an approximate solution that has a desired accuracy in a given subdomain locally.

Let be a given subdomain and a given tolerance. Suppose we want to obtain an approximate solution satisfying

According to the local error estimates in previous sections, this error tolerance can be achieved by only local mesh refinement around the domain . Let be a subdomain that is slightly larger than . By Theorem 3.9, we have the estimate

If our initial grid is reasonably fine, the higher order global error term is negligible. This means we may only need to refine the mesh in the subdomain so that

This adaptive process corresponds precisely to the local algorithm described in §4.1.1, where a priori error estimates are discussed.

In view of the local algorithm described in §4.1.2, apparently, a corresponding local adaptive process can also be obtained. We omit the details here.

5.3. A parallel adaptive process

As before, a simultaneous application of a local algorithm on a number of subdomains naturally leads to a parallel algorithm. In this subsection, we shall give some details for a parallel adaptive algorithm corresponding to the local adaptive algorithm described in the previous subsection.

Our goal is to design a parallel procedure to find a finite element approximation (which may be piecewise defined) satisfying (see Equation 4.1)

for a given tolerance error .

Based on a reasonable good initial mesh, denoted by , and its corresponding solution, denoted by , an adaptive process is to make use of some a posteriori estimates based on information from and to adaptively come up with better and better meshes until a desired error tolerance is reached. Traditionally, after a stage of refinement/de-refinement, the a posteriori estimates are evaluated on the whole domain. Thanks to the local estimate Equation 3.21, we propose that a posteriori estimates can be evaluated concurrently on a number of proper subdomains and a parallel adaptive process can then be brought about.

As in §4.2, given an initial coarse triangulation , we divide into a number of disjoint subdomains , then enlarge each to obtain ’s that align with .

We aim to reach Equation 5.5 by refining the mesh . Note that is of higher order compared with ; for convenience of exposition, we may assume that our initial mesh is fine enough so that is much smaller than . (This assumption is not crucial in practice, as can get updated by finer meshes in an adaptive process.) Thanks to the estimate Equation 3.21, we have (with )

We use a standard principle of equi-distribution for the error control, in which we equalize the contribution from each subdomain. More precisely, the finite element approximation computed on the targeted mesh in terms of computational work satisfies

Therefore we can just carry out the mesh refinement locally on until the following estimates are satisfied:

We note that the refinement process on each is independent of those from other subdomains. Associated with each , we get a locally refined mesh as in Figure 1 and then find the corresponding finite element solution, denoted by , on such a mesh. After all these are done, we then take final solutions that are defined piecewise on each restricted from .

The above exposition contains the main ideas of a parallel adaptive process, but for its application, there are many practical issues that need to be addressed. We refer to Bank and Holst Reference 12 for a similar approach and implementation details.

6. Some numerical experiments

In this paper, we have presented many new estimates and new algorithms. It is perhaps a little too much of an undertaking to carry out and report numerical experiments for all these results in this single work. For illustration, we choose to report some simple numerical experiments only for Algorithms B1, C1 and C2.

We consider the simple unit square domain and a uniform triangulation (see Figure 7) and piecewise linear finite element spaces:

Divide into four subdomains (see Figure 8):

Set

and

Now we apply Algorithm B1, Algorithm C1 and Algorithm C2 with coarse mesh size to solve two partial differential equations of second order, respectively. For the exact solver of all the nonsymmetric and/or indefinite systems of coarse spaces, the Gaussian elimination is used. On the other hand, a standard V-cycle multigrid algorithm is used to solve all the SPD systems on fine spaces.

We first consider the following simple Poisson equation:

where

We shall apply Algorithm B1 and Algorithm C2 to solve this problem, using fine meshes of sizes and corresponding coarse meshes of size .

Let be the standard finite element solution, let be obtained by Algorithm B1, and let be obtained by Algorithm C2. Then, by Theorems 4.4 and 4.6, we obtain

The results shown in Table 1 support the above estimate. Actually, for Algorithm C2, this numerical example shows a better order of convergence than our theory predicted.

We next consider a simple example of convection-diffusion problems:

where .

As for the convection-diffusion equation above, we again apply Algorithm C1 and Algorithm C2 to solve this problem. The corresponding computational results are shown in Table 2, and again support our theory.

7. Some further remarks

In this last section, we shall make a few technical comments and a concluding remark.

7.1. On the dependence of subdomains

We would like to point out that most of the error estimates presented in this paper depend on the distance between the boundaries of the underlying subdomains (cf. Schatz and Wahlbin Reference 39Reference 40, and Wahlbin Reference 46Reference 47). To avoid notational complication, we chose not to explicitly spell out this kind of dependence.

7.2. Estimates in terms of different norms

Most of the local estimates in this paper can be generalized to other norms such as the and norms. As an illustration, let us discuss briefly the possible maximum norm estimates in two dimensions.

For any , let be the Green function with respect to the singular point :

We assume that

A.6. Green function.

where . Moreover, if , then

(The above assumption is reasonable; we refer, for example, to Reference 17Reference 37 for details.)

A.1 Approximation. If , then as ,

A.4. Trace.

The following theorem can be proved.

Theorem 7.1.

If Assumptions A.1, A.4 and A.6 hold, then

7.3. Improved estimates in some special cases

In our local error estimates, the global errors are all measured in norms. As in the existing literature on local a priori error estimates (cf. Schatz and Wahlbin Reference 39Reference 40, and Wahlbin Reference 46Reference 47), it is possible to replace the global norm by some negative Sobolev norms. For example, the following estimate may be obtained:

for a finite element space of degree . As a result, the following estimate similar to Equation 1.3 may be obtained:

For simplicity and generality, we did not get into details in this paper when the above improved estimates may be obtained. We will report this kind of results in our future work.

7.4. Conclusion

In this paper, we have used a simple second oder elliptic model problem and a class of finite element discretization methods to demonstrate how to use a coarse grid to capture the global component of the approximate solution and then parallelize the major computation in a much finer grid. We believe this is a general and powerful parallel-computing technique that can be used for a variety of partial differential equations with different types of discretization methods.

Acknowledgments

The authors wish to thank H. Kim and L. Zikatanov for their assistance with numerical experiments and helpful discussions. This paper was completed while the first author was visiting ETH Zurich in Switzerland during the summer of 1998, and the author wishes to thank Professors C. Schwab and R. Jeltsch for their hospitality.

Figures

Figure 1.

A local refinement mesh

Graphic without alt text
Figure 2.

Subdomains

Graphic without alt text
Figure 3.

Local Refinement

Graphic without alt text
Figure 4.

Localization

Graphic without alt text
Figure 5.

Domain decomposition:

Graphic without alt text
Figure 6.

Domain decomposition: and

Graphic without alt text
Figure 7.

A Triangulation

Graphic without alt text
Figure 8.

Domain Decomposition

Graphic without alt text
Table 1.

Algorithm B1 and Algorithm C2 for the Poisson problem

0.7722(-1)0.4224(-3)
0.1948(-1)3.960.2933(-4)14.4
0.4885(-2)3.990.1952(-5)15.0
Table 2.

Algorithm C1 and Algorithm C2 for the Non-SPD problem

0.1063(+0)0.1089(-2)
0.2827(-1)3.760.1307(-3)8.33
0.7217(-2)3.920.1606(-4)8.14

Mathematical Fragments

Equation (1.1)
Equation (1.2)
Equation (1.3)
Equation (1.5)
Equation (2.8)
Equation (2.9)
Equation (2.10)
Equation (2.11)
Equation (2.13)
Equation (2.15)
Equation (2.17)
Lemma 2.1.

Assume that and Assumption A.1 holds. Then

and

Equation (2.21)
Equation (2.22)
Lemma 2.2.

Assume that and Assumption A.1 holds. Then as . Moreover,

provided

Lemma 3.1.

Let , and let be such that supp . Then

Lemma 3.2.

Suppose that and . If Assumptions A.0, A.2 and A.3 hold and satisfies

then

where

Equation (3.5)
Equation (3.6)
Equation (3.7)
Equation (3.8)
Equation (3.9)
Theorem 3.3.

Let and . If Assumptions A.0, A.1, A.2 and A.3 hold, then

Theorem 3.4.

Let and . If Assumptions A.0, A.1, A.2 and A.3 hold, then

or

Corollary 3.5.

Let , and . If Assumptions A.0, A.1, A.2 and A.3 hold, then

Lemma 3.8.

Let , and let be such that supp . Then

Equation (3.19)
Theorem 3.9.

Let and . If Assumptions A.1, A.3 and A.4 hold, then

or

Equation (3.22)
Theorem 4.1.

Assume that is obtained by Algorithm A0. Then

Theorem 4.2.

Assume that is obtained by Algorithm B0, and Assumption holds. Then

Theorem 4.3.

Assume that is obtained by Algorithm C0. Then

Equation (4.1)
Theorem 4.4.

Assume that is the solution obtained by Algorithm B1 and Assumptions hold for . Then

and

Theorem 4.5.

Assume that is the solution obtained by Algorithm C1. Then

and

Theorem 4.6.

Assume that is the solution obtained by Algorithm C2 and Assumption A.5. Then

and

Equation (5.1)
Equation (5.3)
Equation (5.5)

References

Reference [1]
Adams R.A.(1975): Sobolev Spaces, Academic Press, New York. MR 56:9247
Reference [2]
Ainsworth, M. and Oden, J.T.(1993): A unified approach to a posteriori error estimation using element residual methods, Numer. Math., 65, 23-50. MR 95a:65185
Reference [3]
Axelsson, O. and Layton, W.(1996): A two-level discretization of nonlinear boundary value problems, SIAM J. Numer. Anal., 33, 2359-2374. MR 98c:65181
Reference [4]
Babuska, I., Duran, R. and Rodriguez, R.(1992): Analysis of the efficiency of an posteriori error estimator for linear triangular finite elements, SIAM J. Numer. Anal., 29, 947-946. MR 93d:65096
Reference [5]
Babuska, I. and Rheinboldt, C.(1978): Error estimates for adaptive finite element computations, SIAM J. Numer. Anal., 15, 736-754. MR 58:3400
Reference [6]
Babuska, I., Zienkiewicz, O.C., Gago, J. and Oliveira, E.R. de A. (eds.)(1986): Accuracy Estimates and Adaptive Refinements in Finite Element Computations, Wiley, New York. MR 87j:65004
[7]
Babuska, I., Strouboulis, T. and Gangaraj, S.K.(1997): A posteriori estimation of the error in the recovered derivatives of the finite element solution, Comput. Methods Appl. Mech. Engrg., 150, 369-396. CMP 98:06
[8]
Babuska, I., Strouboulis, T., Gangaraj, S.K. and Upadhyay, C.S.(1997): Pollution error in the version of the finite element method and the local quality of the recovered derivatives, Comput. Methods Appl. Mech. Engrg., 140, 1-37. MR 97i:73092
[9]
Babuska, I., Strouboulis, T. and Upadhyay, C.S.(1994): A model study of the quality of a posteriori error estimators for linear elliptic problems. Error estimation in the interior of patchwise uniform grids of triangles, Comput. Methods Appl.Mech. Engrg., 114, 307-378. MR 95d:65093
Reference [10]
Bank, R.E.(1996): Hierarchical bases and the finite element method, Acta Numerica, 5, 1-43. CMP 98:14
[11]
Bank, R.E.(1998): A simple analysis of some a posteriori error estimates, Appl. Numer. Math., 26, 153-164. CMP 98:08
Reference [12]
Bank, R.E. and Holst, M.(1998): A new paradigm for parallel adaptive meshing algorithms (manuscript).
[13]
Bank, R.E. and Smith, R.K.(1993): A posteriori error estimates based on hierarchical bases, SIAM J. Numer. Anal., 30, 921-935. MR 95f:65212
Reference [14]
Bank, R.E. and Smith, R.K.(1997): Mesh smoothing using a posteriori error estimates, SIAM J. Numer. Anal., 34, 979-997. MR 98M:65162
Reference [15]
Bank, R.E. and Weiser, A.(1985): Some a posteriori error estimates for elliptic partial differential equations, Math. Comp., 44, 283-301. MR 86g:65207
Reference [16]
Bedivan, D.M.(1995): A two-grid method for solving elliptic problems with inhomogeneous boundary conditions, Comput. Math. Appl., 29, 59-66. MR 95k:65103
Reference [17]
Blum, H., Lin, Q. and Rannacher, R.(1986): Asymptotic error expansion and Richardson extrapolation for linear finite elements, Numer. Math., 49, 11-38. MR 87m:65172
[18]
Bornemann, F.A., Erdmann, B. and Kornhuber, R.(1996): A posteriori error estimates for elliptic problems in two and three space dimensions, SIAM J. Numer. Anal., 33, 1188-1204. MR 98a:65161
Reference [19]
Bramble, J.H.(1993): Multigrid Methods, Pitman Research Notes in Mathematics, 294, London Co-published in the USA with Wiley, New York. MR 95b:65002
Reference [20]
Bramble, J.H., Ewing, R.E., Parashkevov, R.R. and Pasciak, J.E.(1992): Domain decomposition methods for problems with partial refinement, SIAM J. Sci. Stat. Comp., 13, 397-410. MR 92i:65179
Reference [21]
Bramble, J.H., Ewing, R.E., Pasciak, J.E. and Schatz, A.H.(1988): A preconditioning technique for the efficient solution of problems with local grid refinement, Comp. Meth. Appl. Mech. Eng., 67, 149-159.
Reference [22]
Chan, T. and Mathew, T.(1994): Domain decomposition algorithms, Acta Numerica, 3, 61-143. MR 95f:65214
Reference [23]
Ciarlet, P.G. and Lions J.L.(1991): Handbook of Numerical Analysis, Vol.II, Finite Element Methods (Part I), North-Holland. MR 92f:65001
Reference [24]
Dawson, C.N. and Wheeler, M.F.(1994): Two-grid methods for mixed finite element approximations of nonlinear parabolic equations, Contemp. Math., 180, 191-203. MR 95j:65117
Reference [25]
Dawson, C.N., Wheeler, M.F. and Woodward, C.S.(1998): A two-grid finite difference scheme for nonlinear parabolic equations, SIAM J. Numer. Anal., 35, 435-452. MR 99b:65097
Reference [26]
Eriksson, K., Estep, D., Hansbo, P. and Johnson, C.(1995): Introduction to adaptive methods for differential equations, Acta Numerica, 105-158. MR 96k:65057
Reference [27]
Eriksson, K., Estep, D., Hansbo, P. and Johnson, C.(1996): Computational Differential Equations, Cambridge University Press. MR 97m:65006
Reference [28]
Eriksson, K. and Johnson, C.(1991): Adaptive finite element methods for parabolic problems I: a linear model problem, SIAM J. Numer. Anal., 28, 43-77. MR 91m:65274
[29]
Eriksson, K. and Johnson, C.(1995): Adaptive finite element methods for parabolic problems IV: Nonlinear problems, SIAM J. Numer. Anal., 32, 1729-1749. MR 96i:65081
Reference [30]
Grisvard, P.(1985): Elliptic Problems in Nonsmooth Domains, Pitman, Boston, MA. MR 86m:35044
Reference [31]
Hackbusch, W.(1985): Multigrid Methods and Applications, Springer, New York. MR 87e:65082
Reference [32]
Johnson, C.(1990): Adaptive finite element methods for diffusion and convection problems, Comp. Methods Appl. Mech. Engrg., 82, 301-322. MR 91k:65134
Reference [33]
Layton, W. and Lenferink, W.(1995): Two-level Picard and modified Picard methods for the Navier-Stokes equations, Appl. Math. Comp., 69, 263-274. MR 95m:65191
Reference [34]
Marion, M. and Xu, J.(1995): Error estimates on a new nonlinear Galerkin method based on two-grid finite elements, SIAM J. Numer. Anal., 32, 1170-1184. MR 96f:65136
Reference [35]
Nitsche, J. and Schatz, A.H.(1974): Interior estimates for Ritz-Galerkin methods, Math. Comp., 28, 937-955. MR 51:9525
Reference [36]
Nochetto, R. H.(1995): Pointwise a posteriori error estimates for elliptic problems on highly graded meshes, Math. Comp., 64, 1-22. MR 95c:65172
Reference [37]
Rannacher, R. and Scott, R.(1982): Some optimal error estimates for piecewise linear finite element approximations, Math. Comp., 38, 437-445. MR 83e:65180
Reference [38]
Schatz, A.H.(1998): Pointwise error estimates and asymptotic error expansion inequalities for the finite element method on irregular grids: Part I. Global estimates, Math. Comp., 67, 877-899. MR 98j:65082
Reference [39]
Schatz, A.H. and Wahlbin, L.B.(1977): Interior maximum-norm estimates for finite element methods, Math. Comp., 31, 414-442. MR 55:4748
Reference [40]
Schatz, A.H. and Wahlbin, L.B.(1995): Interior maximum-norm estimates for finite element methods, Part II, Math. Comp., 64, 907-928. MR 95j:65143
[41]
Schatz, A.H. and Wang, J.(1996): Some new error estimates for Ritz-Galerkin methods with minimal regularity assumptions, Math. Comp., 65, 19-27. MR 96d:65190
Reference [42]
Utnes, T.(1997): Two-grid finite element formulations of the incompressible Navier-Stokes equations, Comm. Numer. Methods Engrg., 34, 675-684. MR 98d:76110
Reference [43]
Verfürth, R.(1994): A posteriori error estimates for nonlinear problems. Finite element discretizations of elliptic equations, Math. Comp., 62, 445-475. MR 94j:65136
Reference [44]
Verfürth, R.(1995): A posteriori error estimates for nonlinear problems. Finite element discretizations of parabolic equations, Bericht Nr. 180, Fakultät für Mathematik, Ruhr-Universität Bochum.
Reference [45]
Verfürth, R.(1996): A Review of A-Posteriori Error Estimation and Adaptive Mesh Refinement, Wiley-Teubner.
Reference [46]
Wahlbin, L.B.(1991): Local behavior in finite element methods, in Reference 23, pp. 355-522. MR 92f:65001
Reference [47]
Wahlbin, L.B.(1995): Superconvergence in Galerkin Finite Element Methods, Vol. 1605, Lecture Notes in Math., Springer. MR 98j:65083
Reference [48]
Xu, J.(1992): A new class of iterative methods for nonselfadjoint or indefinite problems, SIAM J. Numer. Anal., 29, 303-319. MR 92k:65063
Reference [49]
Xu, J.(1992): Iterative methods by space decomposition and subspace correction, SIAM Review, 34, 4, 581-613. MR 93k:65029
Reference [50]
Xu, J.(1994): A novel two-grid method for semilinear equations, SIAM J. Sci. Comput., 15, 231-237. MR 94m:65178
Reference [51]
Xu, J.(1996): Two-grid discretization techniques for linear and nonlinear PDEs, SIAM J. Numer. Anal., 33, 1759-1777. MR 97i:65169
Reference [52]
Xu, J. and Zou, J.(1998): Some non-overlapping domain decomposition methods, SIAM Review 40, 4, 857-914.
Reference [53]
Yserentant, H.(1993): Old and new proofs for multigrid algorithms, Acta Numerica, 2, 285-326. MR 94i:65128
Reference [54]
Zhou, A., Liem, C.L., Shih, T.M. and Lü, T.(1998): Error analysis on bi-parameter finite elements, Comput. Methods Appl. Mech. Engrg., 158, 329-339. CMP 98:14

Article Information

MSC 1991
Primary: 65N15 (Error bounds), 65N30 (Finite elements, Rayleigh-Ritz and Galerkin methods, finite methods), 65N55 (Multigrid methods; domain decomposition), 65F10 (Iterative methods for linear systems)
Keywords
  • Adaptive
  • finite elements
  • local a priori and a posteriori error estimates
  • nonsymmetric
  • parallel algorithm
  • two-grid method
Author Information
Jinchao Xu
Center for Computational Mathematics and Applications, Department of Mathematics, Pennsylvania State University, University Park, Pennsylvania 16802
xu@math.psu.edu
MathSciNet
Aihui Zhou
Institute of Systems Science, Academia Sinica, Beijing 100080, China
azhou@bamboo.iss.ac.cn
Additional Notes

This work was partially supported by NSF DMS-9706949, NSF ACI-9800244 and NASA NAG2-1236 through Penn State and Center for Computational Mathematics and Applications, The Pennsylvania State University.

Journal Information
Mathematics of Computation, Volume 69, Issue 231, ISSN 1088-6842, published by the American Mathematical Society, Providence, Rhode Island.
Publication History
This article was received on and published on .
Copyright Information
Copyright 2000 American Mathematical Society
Article References
  • Permalink
  • Permalink (PDF)
  • DOI 10.1090/S0025-5718-99-01149-7
  • MathSciNet Review: 1654026
  • Show rawAMSref \bib{1654026}{article}{ author={Xu, Jinchao}, author={Zhou, Aihui}, title={Local and parallel finite element algorithms based on two-grid discretizations}, journal={Math. Comp.}, volume={69}, number={231}, date={2000-07}, pages={881-909}, issn={0025-5718}, review={1654026}, doi={10.1090/S0025-5718-99-01149-7}, }

Settings

Change font size
Resize article panel
Enable equation enrichment

Note. To explore an equation, focus it (e.g., by clicking on it) and use the arrow keys to navigate its structure. Screenreader users should be advised that enabling speech synthesis will lead to duplicate aural rendering.

For more information please visit the AMS MathViewer documentation.