# Piecewise bilinear preconditioning of high-order finite element methods.

Abstract. Bounds on eigenvalues which are independent of both
degrees of high-order elements and mesh sizes are shown for the system
preconditioned by bilinear elements for high-order finite element discretizations applied to a model uniformly elliptic operator.

Key words. multigrid, high-order finite element methods, piecewise linear preconditioning

AMS subject classifications. 65F10, 65M30

1. Introduction. High-order finite element methods for discretizing a second-order uniformly elliptic partial differential equation lead to a linear equation [L.sub.[N.sup.2]] U = F which requires efficient iterative methods, such as Schwarz-based methods (see [5, 14, 17]), precon ditioning methods related to multilevel methods, multigrid methods (see [6, 7, 8]), etc. This is because such linear systems have large condition numbers which depend on the order of the elements used and the mesh spacing. In particular, an algebraic multigrid (AMG) method is useful in the case of irregular grids. However it was reported that a direct application of AMG to [L.sub.[N.sup.2]]U = F is not so efficient; see [8, 16]. The convergence factor degrades rapidly as the order of the elements is increased. For the case of Stokes and elasticity equations, the complexity from the high-order finite element discretizations for AMG is even worse than that of a simple elliptic partial differential equation.

In [6] and [8], a preconditioner constructed by using the Legendre-Gauss-Lobatto quadrature points in each cell as mesh points for a bilinear discretization. The finite element pre-conditioning can be approximately inverted by one AMG V -cycle. This approach has several advantages, including the possibility to avoid assembly of the high-order stiffness matrix. Numerical results show that this preconditioning is very effective, especially when accelerated by a conjugate gradient method. It also has the advantage of a straightforward matrix-free implementation for the fine grid high-order element matrix. In this paper, it is proven that the preconditioning yields a preconditioned system with condition number bounded independently of the mesh space and the polynomial order of the spectral elements.

In order to show that such a bilinear preconditioning is effective, we will consider a uniformly elliptic boundary value problem, like

(1.1) [L.sub.p]u := -[nabla] * p(x,y) [nabla]u + q(x,y)u in [OMEGA] = (-1,1)

with boundary conditions

(1.2) u = 0 on [[GAMMA].sub.D], n * [nabla]u = 0 on [[GAMMA].sub.N]

where [GAMMA] = [[GAMMA].sub.D] [union] [[GAMMA].sub.N] with a nonempty [[GAMMA].sub.D]. Further, we assume that p(x, y) is a strictly positive function and q(x, y) is a nonnegative smooth bounded function on [OMEGA]. The piecewise bilinear finite element preconditioner will be constructed by another uniformly elliptic boundary operator B, like

Bv := -[nabla] * [nabla]v + 2v in [OMEGA] = (-1,1) x (-1,1)

with the same boundary (1.2). This operator B yields a matrix [B.sub.[h.sup.2]] to reduce the condition number of a matrix [L.sub.[N.sup.2]] induced by high-order elements applied to (1.1)

For convenience, we assume throughout this paper that the Dirichlet part of the boundary [GAMMA] is

(1.3) [[GAMMA].sub.D] = {-1} x [-1,1] [union] [-1,1] x {-1}.

The main object of this article is to prove that the eigenvalues of [([B.sub.[h.sup.2]]).sup.-1] [L.sub.[N.sup.2]] are independent of the degrees of high-order elements and the mesh sizes. As a result the condition numbers of the preconditioned systems are fixed and small, so that the complexity is no longer a problem when the AMG algorithm is applied. This allow one to employ multigrid algorithms for solving problems like (1.1) with high-order element discretizations, which guarantees convergence of the strategy of preconditioning the high-order matrix with a bilinear or trilinear matrix based on Legendre-Gauss-Lobatto quadrature nodes well suited to a solution by multigird methods. For a single spectral element, this kind of preconditioning was analyzed for Legendre spectral collocation methods in [3, 12, 13, 15], for example.

The goal of this paper can be achieved by extending the results of [12] to high-order elements and by applying [H.sup.1], [L.sub.2] estimates in [18] of a local interpolation operator [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] to a global interpolation operator [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Further, we note that such an [H.sup.1] semi-norm estimate of the local interpolation operator defined on a space of piecewise linear functions can be extended to the space of [H.sup.1] by modifying the relevant results in [1]. We also note that the discussions here can be extended to singular value results for general elliptic operators which are not positive definite. For this, one should refer to [12].

This paper is organized as follows. In the next Section, we recall some known results on piecewise polynomial bases, interpolation operators, etc. In Section 3, we extend the results in [12] and [18] which lead to one and two dimensional preconditioning results for the constant coefficients case in Section 4. The variable coefficients case is dealt with in Section 5 using the tensor representation that appeared in [4]. In Section 6, we provide some numerical results which support the theories developed. Finally, we mention some conclusions in the last Section.

2. Preliminary. With the direction notation t = x or y, we assume that [M.sup.t] and [N.sup.t.sub.j] are natural numbers. Let [{[t.sub.k]}.sup.[M.sup.t].sub.k=0] to be the knots in the interval I = [-1,1] such that

-1 =: [t.sub.0] < [t.sub.1] < ... < [t.sub.[M.sup.t]-1] < [t.sub.[M.sup.t]] := 1.

Let [{[eta]k}.sup.[N.sup.t.sub.j].sub.k=0] and [{[w.sub.k]}.sup.[N.sup.t.sub.j].sub.k=0]] be the Legendre-Gauss-Lobatto (=: LGL) points in I arranged by

-1 =: [[eta].sub.0] < [[[eta].sub.1] < ... < [[eta].sub.[N.sup.t.sub.j]-1] < [[eta].sub.[N.sup.t.sub.j] :=1

and its corresponding LGL weights respectively. Here [M.sup.t] denotes the number of subintervals of I = [-1,1] and [N.sup.t.sub.j] denotes the number of LGL points on a [j.sup.th] subinterval by a translation of I. By the translation from I to a [j.sup.th] subinterval [I.sup.t.sub.j] := [[t.sub.j-1], [t.sub.j]] we denote [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] as the [k.sup.th] - LGL points in each subinterval [I.sup.t.sub.j] for j = 1, 2, ..., [M.sup.t] and enumerate them as

(2.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and the corresponding LGL weights [{[[rho].sup.t.sub.j,k]}.sup.[N.sup.t.sub.j].sub.k=0] are given by

(2.2) [[rho].sup.t.sub.j,k] = [h.sup.t.sub.j]/2[w.sub.k], j = 1,2, ..., [M.sup.t].

With [[xi].sup.t.sub.[M.sup.t+1,0]] := [t.sub.[M.sup.t]], note than in (2.1) and (2.2)

(2.3) [[xi].sup.t.sub.j-1],[N.sup.t.sub.j] = [[xi].sup.t.sub.j,0], [[rho].sup.t.sub.j-1], [N.sup.t.sub.j] = [[rho].sup.t.sub.j,0], j = 2, ..., [M.sup.t] + 1.

Let [P.sub.k] be the space of all polynomials [p.sub.k] (t) defined on I whose degrees are less than or equal to k and let [P.sup.h.sub.[N.sup.t.sub.j]] be the subspace of C[-1,1] consisting of piecewise polynomials of degree less than or equal to [N.sup.t.sub.j] in [I.sup.t.sub.j]. The basis for [P.sup.h.sub.[N.sup.t.sub.j]] is given by a piecewise Labasis grange polynomial basis [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] with respect to g which satisfy

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where k = 1,2, ..., [N.sup.t.sub.j] - 1, q = 0, 1, ..., [N.sup.t.sub.j] and i, j = 1, ... [M.sup.t] and [delta] denotes the Kronecker delta function. Even though this Lagrangian basis is actually rather easy to work with providing preconditioning results, one may prefer another basis {[phi]v(t)}. The change of basis may be accomplished algebraically by use of the matrix G given by [G.sub.[micro]v] = [phi]v ([xi][micro]). Then if H is any matrix representation of an operator H : [P.sup.h.sub.[N.sup.t.sub.j]] [right arrow] [P.sup.h.[N.sub.t.sub.j]] given in terms of the representations via the {[phi][micro]} basis then the matrix representation H of H in the Lagrangian basis {[phi][micro]} is given by H = GH[G.sup.-1]. Hence it may be enough for us to use the above piecewise Lagrangian basis functions in this paper. For two dimensional high-order space, let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

whose basis functions are given by tensor products of one dimensional piecewise Lagrange polynomials. Let [V.sub.[N.sup.t.sub.j]] be the space of all piecewise Lagrange linear functions [psi]k (x) with respect to on I. Define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] as the space of all piecewise Lagrange linear functions [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] with respect to G. For two dimensional piecewise linear space, let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

hose basis functions are given by tensor products of one dimensional piecewise Lagrange linear functions.

Define two interpolation operators [L.sub.[N.sup.t.sub.j]] : C[-1,1] [right arrow] [P.sub.[N.sup.t.sub.j]] (I) such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and [L.sup.h[N.sup.t.sub.j]] : C [-1,1] [right arrow] [P.sup.h.[N.sup.t.sub.j]] (I) such that

Define a discrete inner product [<u, v>.sub.N] On C[-1,1] x C[-1,1] as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and its corresponding norm is given by

[[parallel]u[parallel].sub.N] = [<u,u>.sup.1/2.sub.N], for u [member of] C[-1,1].

Finally, the notation a ~ b for any two real quantities a and b means by that there are two positive constants which do not depend on mesh sizes and degrees of polynomials such that 0 < c [less than or equal to] a/b < C < [infinity]. Using this notation, the LGL numerical quadrature rule for a polynomial of degree 2[N.sup.t.sub.j] (see [1], for example) can be compared as

(2.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

The notation (U, V) stands for [SIGMA] [u.sub.i][u.sub.i] for any two vectors U = [([u.sub.1], ..., [u.sub.d]).sup.T] and V = [([v.sub.1], ... , [v.sub.d]).sup.T] where the superscript T denotes the transpose of a vector. The standard spaces [H.sup.1] and [L.sup.2] will be used.

3. Basic estimates. In this section, we will discuss some estimates of global interpolation operator [L.sup.h.sub[N.sup.t.sub.j]] in terms of [H.sup.1] and [L.sup.2] norms. For t [member of] [-1,1] and [S.sub.t] [member of] [[t.sub.j-1], [t.sub.j]] and a function u [member of] [H.sup.1], let

(3.1) vj(t) := u([S.sub.t]) = u ([h.sup.t.sub.j]/2 t + 1/2([t.sub.j-1] + tj)).

Then for k = 0, 1, ..., [N.sup.t.sub.j] we have

(3.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

which yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Also, we have

(3.3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where [[parallel] * [parallel].sub.1] denotes the standard Sobolev [H.sup.1] norm. From now on, we will use [|*|.sub.1] as the Sobolev [H.sup.1] seminorm and [parallel]*[parallel] as the usual [L.sup.2] norm. In order to discuss the piecewise linear finite elements preconditioner, it may be required to analyze the relations between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and [phi] in the sense of [H.sup.1]- and [L.sup.2]- norm. For this purpose, we recall the following lemma (see [1], [18, Lemma 7.2]) which can be also extended to higher dimensions; see in [18, Theorem 7.3]. We remark that the similar estimates with Chebyshev weight and Chebyshev-Gauss-Lobatto points are found in [1] and [11].

LEMMA 3.1. It follows that for all v [member of] [V.sub.[N.sup.t.sub.j]]

(3.5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Note that the result [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] in (3.5) can be verified for any function v [member of] [H.sup.1](I) by modifying Theorem 1.7, Corollary 1.9 in Chapter II and Corollary 1.16, Theorem 1.19 in Chapter III with usages of Theorem 1.15, Lemma 1.18 and Proposition 1.17 in Chapter III therein in [1] where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] is found. For reader's convenience, we include the statement here.

PROPOSITION 3.2. For all v [member of] [H.sup.1] (I), there is a positive constant C such that

[|[L.sub.[N.sup.t.sub.j]]v|.sub.1] [less than or equal to] [|v|.sub.1].

Now the extension of Lemma 3.1 to the global interpolation operator [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] can be done easily by combining (3.3), (3.4) with Lemma 3.1. Here we state it as theorem.

THEOREM 3.3. For all u [member of] [V.sup.h.sub[N.sup.t.sub.j]]

[|[I.sup.h.sub.[N.sup.t.sub.j]] u|.sub.1] ~[|u|.sub.1].

LEMMA 3.4. For f [member of] [P.sup.h.sub[N.sup.t.sub.j]] [-1,1], it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Proof. First note that j (t) is a polynomial of degree [N.sup.t.sub.j] on [[t.sub.j-1],[t.sub.j]]. Then applying (2.4) on the interval [[t.sub.j-1], [t.sub.j]] and using (2.3) yield

(3.6) MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

In the last equivalence in (3.6), the observations (2.3) were used.

THEOREM 3.5. For all u [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], we have

(3.7) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Proof. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], Lemma 3.4 yields [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Hence for the proof of (3.7) it is enough to show that for u [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

(3.8) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Using (3.1) and (3.2) for functions vj [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and u [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], we have

(3.9) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Since (see [12, Theorem 3.1])

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

it follows that, using (3.9),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Therefore, it is enough to show

(3.10) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Actually, because of (2.3) we can rewrite the left term of (3.10) as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Then one may see that (3.10) holds. These arguments complete the proof of (3.8) and consequently (3.7).

4. Case of constant coefficients: 1D and 2D. First, we discuss the one dimensional case. For convenience, let M := [M.sup.t] and [N.sub.j] := [N.sup.t.sub.j] for the one dimensional case only. Consider two uniformly positive definite elliptic operators defined in I = (-1,1) such that

(4.1) Lu = -([a.sub.1]u')' + [a.sub.2] u, in I, u(-1) = u'(1) = 0

and

(4.2) Bv = -([b.sub.1]v')' + [b.sub.2]u, in I, u(-1) = u'(1) = 0

where [a.sub.1], [b.sub.1] are positive constants and [a.sub.2], [b.sub.2] are nonnegative constants, leading to two bilinear forms on V x V, where V := {u [member of] [H.sup.1](I), u(-1) = u'(1) = 0},

[l.sub.1](u, v) = [[integral].sup.1.sub.-1] [a.sub.1]u'v' + [a.sub.2]uv dt and [b.sub.1] (u, v) = [[integral].sup.1.sub.-1] [b.sub.1]u'v' + [b.sub.2]uv dt.

For the high-order and piecewise linear approximations to (4.1) and (4.2), let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

whose suitable basis functions [{[[theta].sub.[micro]]}.sup.d.sub.[micro] =1] and [{[[psi].sub.v]}.sup.d.sub.v=1] , respectively, can be given, with

(4.3) d := dim ([P.sup.h,m).sub.Nj]) = dim([V.sup.h,m.sub.Nj]).

Then the stiffness matrix [L.sub.N] with high-order elements based on G of (4.1) is given by

[L.sub.N]([micro],v) = [l.sub.1] ([[theta].sub.[micro]], [[theta].sub.v]), [micro], v = 1, 2, ..., d,

and the stiffness matrix [B.sub.h] associated with piecewise linear elements based on G corresponding to (4.2) is given by

[B.sub.h] ([micro], v) = [b.sub.1] ([[psi].sub.[micro]], [[psi].sub.v], [micro], v = 1, 2, ..., d.

Denote [M.sub.N] and [M.sub.h] by mass matrices with respect to [{[[theta].sub.[micro]]}.sup.d.sub.[micro] = 1] and [{[psi].sub.[micro]]}.sup.d.sub.[micro] = 1], respectively. That is, [micro], v = 1, 2, ..., d,

[M.sub.N]([micro], v) = ([[phi].sub.[micro]], [[phi].sub.v]), [M.sub.h] ([micro], v) = ([[psi].sub.[micro]], [[psi].sub.v]).

Since all the stiffness and mass matrices are symmetric and positive definite, the preconditioned matrix below also has all positive real eigenvalues.

THEOREM 4.1. For every U = [([u.sub.1], [u.sub.2], ... [u.sub.d]).sup.T], we have

([B.sub.h] U,U) ~ ([L.sub.N]U,U), and ([M.sub.h] U,U) ~ ([M.sub.N], U,U).

Hence, the preconditioned matrix [B.sup.-1.sub.h] [L.sub.N] has all positive real eigenvalues [{[[lambda].sub.[micro]]}.sup.d.sub.[micro] = 1] independent of mesh sizes [h.sub.j] and degrees [N.sub.j] of polynomials. That is, there is absolute positive constants c and C such that

0 < c [less than or equal to] [[lambda].sub.[micro]] [less than or equal to] [infinity].

Proof. Let u(t) [member of] [V.sup.h,m.sub.Nj] be represented as u(t) = [[SIGMA].sup.d.sub.[micro] = 1] [u.sub.[micro]][[psi].sub.[micro]](t). Then its piecewise polynomial interpolation can be written as ([L.sup.h.sub.[N.sub.j]]u) (t) = [[SIGMA].sup.d.sub.[micro] = 1] [u.sub.[micro]][[theta].sub.[micro]] (t). The definitions of bilinear forms yield that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Then using Theorem 3.3 and 3.5 completes the proofs.

For actual computations, the bilinear form [l.sub.1] ([I.sup.h.sub.Nj] u, [I.sup.h.sub.Nj] v) and ([I.sup.h.sub.Nj] u, [I.sup.h.sub.Nj] u) will be calculated at LGL points. Define two matrices [L.sub.N] and [M.sub.N] as

[L.sub.N]([micro], v) = [l.sub.1,N]([[phi].sub.[micro]],[[phi].sub.v]), [M.sub.N]([micro],v) = [<[[phi].sub.[micro]],[[phi].sub.v]>.sub.N],

where

[l.sub.1,N](u,v) = [a.sub.1][<u',u'>.sub.N] + [a.sub.2][<u,v>.sub.N].

Note that [M.sub.N] is the diagonal matrix which consists of LGL weights, that is

[M.sub.N] = diag([[rho].sup.t.sub.j,k])

and employing (2.4) leads to

(4.4) ([L.sub.N]U, U) ~ ([L.sub.N]U,U), and ([M.sub.N]U, U) ~ ([M.sub.N]U, U)

and these matrices [L.sub.N] and [M.sub.N] are symmetric and positive definite.

COROLLARY 4.2. The preconditioned matrix [B.sup.-1.sub.h] [L.sub.N] has all positive real eigenvalues [{[[lambda].sub.[micro]]}.sup.d.sub.[micro = 1] independent of mesh sizes [h.sub.j] and degrees [N.sub.j] of polynomials. That is, there are absolute positive constants c and C such that

0 < c [less than or equal to] [[lambda].sub.[micro]] [less than or equal to] C < [infinity].

Proof. Let U = [([u.sub.1], [u.sub.2], ..., [u.sub.d]).sup.T] be any nonzero vector. Since

([L.sub.N] U,U)/([B.sub.h] U,U) = ([L.sub.N] U,U)/([L.sub.N]U,U) ([L.sub.N]U,U)/([B.sub.h]U,U)

using the min-max theorem, Theorem 4.1 and (4.4) we have the conclusion. This argument completes the proof because all involved matrices are symmetric and positive definite.

We now turn to the two dimensional case. For this, we consider the model elliptic operator L such that

Lu = -[[u.sub.xx] + [U.sub.yy]] + 2u, u = 0 on [[GAMMA].sub.D], n * [nabla]u = 0 on [[GAMMA].sub.N],

where [[GAMMA].sub.D] is the boundary described in (1.3), which leads to the bilinear form

(4.5) l(u,v) = ([nabla]u, [nabla]v) + 2(u,v), for u,v [member of] [H.sup.1.sub.D] ([OMEGA]),

where

[H.sup.1.sub.D]([OMEGA]) := {u [member of] [H.sup.1] ([OMEGA]) | u = 0 on [[GAMMA].sub.D]}.

Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Let us order the LGL points by horizontal lines and we list all LGL points [{[[XI].sub.P]}.sup.[d.sup.2].sub.P=1] as

[[XI].sub.P] = ([[xi].sub.[micro]],[[xi].sub.v]), where P = [micro] + d(v - 1), [micro] v = 1, 2, ..., d,

where d is defined in (4.3). Accordingly, we order the basis vectors [[PHI].sub.P] (x,y) [member of] [[P.sup.h,m].sub.N].sup.2] and [[PSI].sub.P] (x, y) [member of] [[[V.sup.h,m.sub.N].sup.2] in the same order. Let [L.sup.s.sub.[N.sup.2]] and [B.sup.s.sub.[h.sup.2]] be the stiffness matrices induced by (4.5) on the space [[[P.sup.h,m.sub.N]].sup.2] and [[[V.sup.h,m].sub.N]].sup.2], respectively. From now on, assume that

[a.sub.i] = [b.sub.i] = 1, i = 1,2

in the operators [L.sub.1] and [B.sub.1] in (4.1) and (4.2). Then using the one dimensional stiffness matrices [L.sub.N.sup.t.sub.j]], [B.sub.[h.sup.t.sub.j] and mass matrices [M.sub.[N.sup.t.sub.j], [M.sub.[h.sup.t.sub.j], we have

(4.6) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

(4.7) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

LEMMA 4.3. For every vector U = [([u.sub.1] ..., [u.sub.[d.sup.2]]).sup.T], we have

(4.8) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and

(4.9) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Proof. First note that all the matrices here are symmetric and positive definite. Hence it is enough to estimate (4.8) and (4.9) in terms of eigenvalues. Now because of Theorem 4.1 the conclusions (4.8) and (4.9) can be verified by following Lemma 5.4 in [12]. The details are as follows: Let [U.sup.1] = [([u.sub.1], [u.sub.2], ... [u.sub.d]).sup.T] and [V.sup.1] = [([v.sub.1], [v.sub.2], ..., [v.sub.d]).sup.T]. Theorem 4.1 implies that

(4.10) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Now consider eigenvalue problems

(4.11) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

From (4.10) we know that [kappa] and [lambda] are uniformly bounded in terms of mesh sizes [h.sup.x.sub.j], [h.sup.y.sub.j] and degrees [N.sup.x.sub.j], [N.sup.y.sub.j]. Note that each in (4.11) has a complete set of eigenvectors [U.sup.1.sub.[micro]] and [V.sup.1.sub.v], [micro], v = 1, ... , d. Therefore the vectors and eigenvalues

[Z.sub.[micro]v] = [U.sup.1.sub.[micro]] [cross product] [V.sup.-1.sub.v], [X.sub.[micro]v] = [V.sup.-1.sub.v] [cross product] [U.sup.1.sub.[micro]], [[LAMBDA].sub.[micro]v] = [[kappa].sub.[micro]][[lambda].sub.v]

are complete set of eigenvectors and eigenvalues of the eigenvalue problem

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Hence one can see the uniform bounds of eigenvalues [[LAMBDA].sub.[micro]v] because of the uniform bounds of [kappa] and [lambda] in terms of mesh sizes [h.sup.x.sub.j], [h.sup.y.sub.j] and degrees [N.sup.x.sub.j], [N.sup.y.sub.j].

PROPOSITION 4.4. For every U = [([u.sub.1], ..., [u.sub.[d.sup.2]]).sup.T], it follows that

([B.sup.s.sub.[h.sup.2]]U,U) ~ ([L.sup.s.sub.[N.sup.2]] U,U).

Hence the eigenvalues of [([B.sup.s.sub.[h.sup.2]]).sup.-1] [L.sup.s.sub.[N.sup.2]] are all positive and bounded. The bounds are independent of the mesh sizes [h.sup.x.sub.j], [h.sup.y.sub.j] and the degrees [N.sup.x.sub.j], [N.sup.y.sub.j] of polynomials.

Proof. It follows from Lemma 4.3 with (4.6) and (4.7).

For actual computations of (4.5), that is, for computations of [L.sup.s.sub.[N.sup.2]], we use LGL quadrature formula. For this, consider

[l.sub.N](u,v) = [<[nabla]u, [nabla]u>.sub.N] + [<u,v>.sub.N],

which can be written as, for u, v [member of] [[[P.sup.h,m.sub.N]].sup.2]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where the vectors U = [([u.sub.1], ..., [u.sub.[d.sup.2]]).sup.T] and V = [([v.sub.1], ..., [v.sub.[d.sup.2]]).sup.T] are vector representations of

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Now we will use the matrix [B.sup.s.sub.[h.sup.2]] in (4.7) as the preconditioner for

[L.sup.z.sub.[N.sup.2]]U = F

where

(4.12) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Then we can show that the eigenvalues of [([B.sup.s.sub.[h.sup.2]]).sup.-1] [L.sup.s.sub.[N.sup.2]] are bounded well in terms of mesh sizes [h.sup.x.sub.j], [h.sup.y.sub.j] and degrees [N.sup.x.sub.j], [N.sup.y.sub.j].

LEMMA 4.5. For every vector U = [([u.sub.1], ... [u.sub.[d.sup.2]]).sup.T], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Proof. Recall that A [cross product] B is symmetric and positive definite if the matrices A and B are symmetric, positive definite. Note that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Therefore, due to min-max theorem and Lemma 4.3, it is enough to show that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

are bounded independently of degrees [N.sup.x.sub.j], [N.sup.y.sub.j] and mesh sizes [h.sup.x.sub.j], [h.sup.y.sub.j]. Due to (4.4), this can be done by following the similar arguments of Lemma 4.3. These arguments complete the proof.

THEOREM 4.6. For every vector U = [([u.sub.1], ..., [u.sub.[d.sup.2]]).sup.T], it follows that

(4.13) ([B.sup.s.sub.[h.sup.2]] U,U) ~ ([L.sup.s.sub.[N.sup.2]U,U).

Hence the eigenvalues of [([B.sup.s.sub.[h.sup.2]]).sup.-1] [L.sup.s.sub.[N.sup.2]] are all positive and bounded. The bounds are independent of the mesh sizes [h.sup.x.sub.j], [h.sup.y.sub.j] and the degrees [N.sup.x.sub.j] [N.sup.y.sub.j].

Proof. It comes from (4.12) and (4.7) and Lemma 4.5

5. Case of variable coefficients: 2D. Consider the bilinear form corresponding to (1.1) and (1.2) as

(5.1) [l.sub.p](u,v) = (p(x,y) [nabla]u, [nabla]v + (q(x,y)u,v) for u,v [member of] [H.sup.1.sub.D] ([OMEGA]).

Let us denote [D.sub.[N.sup.t.sub.j]] by the differentiation matrix at LGL points (see [4] for example) and diagonal matrices P and Q by

P := diag([p.sub.[alpha]] := [p.sub[micro]v]), Q := diag([g.sub.[alpha]] := [q.sub.[micro]v]), [alpha] = [micro] + d(v - 1)

occurred from the expansions of the p(x, y) and q(x, y) in terms of 2D Lagrangian basis functions such that p(x, y) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and q(x, y) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], respectively. Then we will use the tensor representation for the approximations to (5.1) on the space [[[P.sup.h,m.sub.N]].sup.2] given by (see detailed discussions in [4])

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where [E.sub.[N.sup.t.sub.j]] is the identity matrix of order d

[W.sup.S.sub.N] := S([M.sub.[N.sup.y.sub.j]] [cross product] [M.sub.[N.sup.x.sub.j]], where S = P or Q.

Note that the matrix [W.sup.S.sub.N] is diagonal whose elements are positive because the matrices S(= P, Q) and ([M.sub.[N.sup.y.sub.j]] [cross product] [M.sub.[N.sup.x.sub.j]] are diagonal with positive elements. Further, if the matrix P is the identity and the matrix Q is 2E, then the matrix [L.sub.[N.sup.2]] is the same as [L.sup.S.sub.[N.sup.2]] in (4.12) with

[L.sub.[N.sup.t.sub.j]] = [D.sup.T.sub.[N.sup.t.sub.j]] [M.sub.[N.sup.t.sub.j]], t = x,y.

LEMMA 5.1. For any vector U = [([u.sub.1], ..., [u.sub.[d.sup.2]]).sup.T, it follows that

(5.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

(5.3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

(5.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where the matrix equivalence A ~ B should be understood as

(AU, U) ~ (BU, U).

Proof. Note that the variable coefficients p(x, y) and q(x, y) are positive bounded functions and the matrices [W.sup.S.sub.[N.sup.ys]], and ([M.sub.[N.sup.y.sub.j]] [cross product] [M.sub.[N.sup.x.sub.j]]) are diagonal with positive elements. Hence for any vector U it follows immediately that

(5.5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

This argument complete (5.4). Let V = ([E.sub.[N.sup.y.sub.j]] [cross product] [D.sub.[N.sup.x.sub.j]]. Since

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

we have the conclusion (5.2) with help of (5.5). The similar arguments complete (5.3). [] The main goal of this section is to show that the eigenvalues of the preconditioned matrix

[([B.sup.s.sub.[h.sup.2]]).sup.-1] [L.sub.[N.sup.2]]

are real and bounded as follows.

THEOREM 5.2. For any vector U = [([u.sub.1], ..., [u.sub.[d.sup.2]]).sup.T], we have

([B.sup.s.sub.[h.sup.2]]U,U) ~ (L.sub.[N.sup.2]] U,U).

In the sense of eigenvalues, it follows that all eigenvalues of the matrix [([B.sup.s.sub.[h.sup.2]]).sup.-1] [L.sub.[N.sub.2]] are real positive and bounded. The bounds are independent of the mesh sizes hjx, by and the degrees [N.sup.x.sub.j], [N.sup.y.sub.j] of piecewise polynomials.

Proof. Note that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Therefore, using Lemma 5.1 one may see that

([L.sub.[N.sup.2]]U,U) ~ ([L.sup.s.sub.[N.sup.2]]U,U).

From Theorem 4.6,

(L.sup.s.sub.[N.sup.2]]U,U) ~ ([B.sup.s.sub.[h.sup.2]]U,U).

These arguments complete the proof.

[FIGURE 6.1 OMITTED]

6. Computational results. Because there are numerical results reported already in [6] and [8], we discuss a few numerical experiments for one dimensional problems. Consider

(6.1) Lu = -(p(x)u')' + q(x)u, x [member of] (0,1)

with boundary conditions u(0) = u(1) = 0. Let us take the preconditioner operator B as

(6.2) Bu = -u" + [gamma]u, x [member of] (0,1)

with the same homogeneous Dirichlet boundary conditions where [gamma] will be chosen later. In the following numeric tests, the uniform mesh size h = [h.sup.x.sub.j] and uniform degree N = [N.sup.x.sub.j] for j = 1, ..., [M.sup.x] are used.

EXAMPLE 6.1. With a chosen p(x) = 1 + [x.sup.2] and q(x) = [e.sup.x] in (6.1), we discuss the optimal preconditioning operator (6.2) by considering several [gamma]. We will take [gamma] = k x 0.1 where [kappa] is an integer between -5 and 8. The Fig. 6.1 shows that the condition number of the preconditioned matrix [B.sup.-1.sub.h] [L.sub.N] becomes small relatively if we choose [gamma] near 0 among other [gamma]'s. These phenomena were pointed out in [9] if (6.1) is discretized by a finite difference scheme, that is to say, [gamma] may be chosen by considering the advection coefficient in (6.1). Hence one may choose [gamma] = 0 in this case.

EXAMPLE 6.2. Stimulated by the numerical results in Example 6.1, we will take [gamma] = 0 for the preconditioner operator B while p(x) = q(x) = 1 in (6.1) are taken. The condition numbers of the matrix [L.sub.N] are shown in Fig. 6.2 for various mesh sizes and degrees of polynomials. Then we enumerate condition numbers of the preconditioned matrix [B.sup.-1.sub.h] [L.sub.N] in Fig. 6.2 also, which shows that the condition numbers can be fixed for mesh sizes and degrees of polynomials. We point out that the condition numbers grow as [h.sup.-2] for a fixed degree of polynomial and O([N.sup.3]) for a fixed mesh size. These also can be proven in a standard finite element theory and in spectral methods; see [1]. These phenomena are depicted in Fig. 6.3.

7. Conclusion. As we have shown that the condition numbers of the preconditioned systems are well bounded, it is possible to use AMG algorithms without increasing complexity for solving elliptic boundary value problems with high-order discretizations based on LGL quadrature nodes. As an immediate application, one may apply the techniques here to a first-order system of least-squares for an elliptic problem whose systems are found in [2], combining the results here and in [12] (for example, one may refer to [10]). In order to avoid the non-nested property of irregular LGL nodes occurring in the multigrid method, one may use Chebyshev-Gauss-Lobatto nodes for discretizations which has a nested property in communications at each level. This case will be dealt in a forthcoming paper.

[FIGURE 6.2 OMITTED]

[FIGURE 6.3 OMITTED]

Acknowledgement. The author deeply thanks Professor Manteuffel for his kind guidance in preparing the present topic and also thanks to anonymous referees for pointing out some corrections.

* Received April 3, 2006. Accepted for publication January 1, 2007. Recommended by T. Manteuffel. This work was supported by KRF R02-2004-000-10109-0 (KOSEF 000006).

REFERENCES

[1] C. BERNARDI AND Y. MADAY, Approximation Spectrales de Problemes aux Limites Elliptiques, Springer, Paris, 1992.

[2] Z. CAI, T. MANTEUFEEL, AND S. MCCORMICK, First-order system least squares for second-order partial differential equations: Part II, SIAM J. Numer. Anal., 34 (1997), pp. 425-454.

[3] M. O. DEVILLE AND E. H. MEND, Finite element preconditioning for pseudospectral solutions of elliptic problems, SIAM J. Sci. Stat. Comput., 11 (1990), pp. 311-342.

[4] M. O. DEVILLE, P. F. FISCHER, AND E. H. MEND, High-order Methods for Incompressible Fluid Flow, Cambridge Monographs on Applied and Computational Mathematics, Cambridge Univ. Press, Cambridge, UK, 2002.

[5] M. DRYJA, B. SMITH, AND O. W IDLUND, Schwarz analysis of iterative substructuring algorithms for elliptic problems in three dimensions, SIAM J. Numer. Anal., 31 (1994), pp. 1662-1694.

[6] P. FISCHER, An overlapping Schwarz method for spectral element solution of the incompressible Navier-Stokes equations, J. Comput. Phys., 133 (1997), pp. 84-101.

[7] P. FISHER AND E. RONQUIST, Spectral element methods for large-scale parallel Navier-Stokes calculations, Comput. Method Appl. Math., 116 (1994), pp. 69-76.

[8] J. HEYS, T. MANTEUFFEL, S. MCCORMICK AND L. OLSON, Algebraic multigrid(AMG) for high-order finite elements, J. Comput. Phys., 204 (2005), pp. 520-532.

[9] T. MANTEUIFEL AND J. OTTO, Optimal equivalent preconditioners, SIAM J. Numer. Anal., 30 (1993), pp. 790-812.

[10] S. D. Kim, H.-C. LEE, AND B. C. SHIN, Pseudospectral least-squares method for the second-order elliptic boundary value problem, SIAM J. Numer. Anal., 41 (2003), pp. 1370-1387.

[11] S. D. KIM AND S. PARTER, Preconditioning Chebyshev spectral collocation method for elliptic partial differential equations, SIAM J. Numer. Anal., 33 (1996), pp. 2375-2400.

[12] S. PARTER AND E. ROTHMAN, Preconditioning Legendre spectral collocation approximations to elliptic problems, SIAM J. Numer. Anal., 32 (1995), pp. 333-385.

[13] S. PARTER, Preconditioning Legendre spectral collocation methods for elliptic problems L Finte element operators, SIAM J. Numer. Anal., 39 (2001), pp. 348-362.

[14] L. PAVARINO AND O. WIDLUND, A polylogorithmic bound for an iterative substructuring method for spectral element in three dimensions, SIAM J. Numer. Anal., 33 (1996), pp. 1303-1335.

[15] A. QUARTERONT AND E. ZAMPIERI, Finite element preconditioning for Legendre spectral collocation approximations to elliptic equations and systems, SIAM J. Numer. Anal., 29 (1992), pp. 917-936.

[16] J. RUDE, AMG for high-order discretiztions of second-order elliptic problems, in: Abstract of the Eleventh Copper Mountain Conference on Multigrid Methods (http://www.mgnet.org/ mgnet/Conference /CopperMtn03/'falks/ruge.pdf), 2003.

[17] A. ST-CYR, M. GANDER, AND S. THOMAS, On optimized Schwarz preconditioning for high-order spectral methods, Twelfth Copper Mountain Conference on Multigrid Methods, 2005.

[18] A. TOSELLI AND O. W IDLUND, Domain Decomposition Methods- Algorithms and Theory, Springer Series in Computational Mathematics, Springer, Berlin, Heidelberg, 2005.

[dagger] Department of Mathematics, Kyungpook National University, Daegu 702-701, Korea (skim@knu.ac.kr).

Key words. multigrid, high-order finite element methods, piecewise linear preconditioning

AMS subject classifications. 65F10, 65M30

1. Introduction. High-order finite element methods for discretizing a second-order uniformly elliptic partial differential equation lead to a linear equation [L.sub.[N.sup.2]] U = F which requires efficient iterative methods, such as Schwarz-based methods (see [5, 14, 17]), precon ditioning methods related to multilevel methods, multigrid methods (see [6, 7, 8]), etc. This is because such linear systems have large condition numbers which depend on the order of the elements used and the mesh spacing. In particular, an algebraic multigrid (AMG) method is useful in the case of irregular grids. However it was reported that a direct application of AMG to [L.sub.[N.sup.2]]U = F is not so efficient; see [8, 16]. The convergence factor degrades rapidly as the order of the elements is increased. For the case of Stokes and elasticity equations, the complexity from the high-order finite element discretizations for AMG is even worse than that of a simple elliptic partial differential equation.

In [6] and [8], a preconditioner constructed by using the Legendre-Gauss-Lobatto quadrature points in each cell as mesh points for a bilinear discretization. The finite element pre-conditioning can be approximately inverted by one AMG V -cycle. This approach has several advantages, including the possibility to avoid assembly of the high-order stiffness matrix. Numerical results show that this preconditioning is very effective, especially when accelerated by a conjugate gradient method. It also has the advantage of a straightforward matrix-free implementation for the fine grid high-order element matrix. In this paper, it is proven that the preconditioning yields a preconditioned system with condition number bounded independently of the mesh space and the polynomial order of the spectral elements.

In order to show that such a bilinear preconditioning is effective, we will consider a uniformly elliptic boundary value problem, like

(1.1) [L.sub.p]u := -[nabla] * p(x,y) [nabla]u + q(x,y)u in [OMEGA] = (-1,1)

with boundary conditions

(1.2) u = 0 on [[GAMMA].sub.D], n * [nabla]u = 0 on [[GAMMA].sub.N]

where [GAMMA] = [[GAMMA].sub.D] [union] [[GAMMA].sub.N] with a nonempty [[GAMMA].sub.D]. Further, we assume that p(x, y) is a strictly positive function and q(x, y) is a nonnegative smooth bounded function on [OMEGA]. The piecewise bilinear finite element preconditioner will be constructed by another uniformly elliptic boundary operator B, like

Bv := -[nabla] * [nabla]v + 2v in [OMEGA] = (-1,1) x (-1,1)

with the same boundary (1.2). This operator B yields a matrix [B.sub.[h.sup.2]] to reduce the condition number of a matrix [L.sub.[N.sup.2]] induced by high-order elements applied to (1.1)

For convenience, we assume throughout this paper that the Dirichlet part of the boundary [GAMMA] is

(1.3) [[GAMMA].sub.D] = {-1} x [-1,1] [union] [-1,1] x {-1}.

The main object of this article is to prove that the eigenvalues of [([B.sub.[h.sup.2]]).sup.-1] [L.sub.[N.sup.2]] are independent of the degrees of high-order elements and the mesh sizes. As a result the condition numbers of the preconditioned systems are fixed and small, so that the complexity is no longer a problem when the AMG algorithm is applied. This allow one to employ multigrid algorithms for solving problems like (1.1) with high-order element discretizations, which guarantees convergence of the strategy of preconditioning the high-order matrix with a bilinear or trilinear matrix based on Legendre-Gauss-Lobatto quadrature nodes well suited to a solution by multigird methods. For a single spectral element, this kind of preconditioning was analyzed for Legendre spectral collocation methods in [3, 12, 13, 15], for example.

The goal of this paper can be achieved by extending the results of [12] to high-order elements and by applying [H.sup.1], [L.sub.2] estimates in [18] of a local interpolation operator [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] to a global interpolation operator [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Further, we note that such an [H.sup.1] semi-norm estimate of the local interpolation operator defined on a space of piecewise linear functions can be extended to the space of [H.sup.1] by modifying the relevant results in [1]. We also note that the discussions here can be extended to singular value results for general elliptic operators which are not positive definite. For this, one should refer to [12].

This paper is organized as follows. In the next Section, we recall some known results on piecewise polynomial bases, interpolation operators, etc. In Section 3, we extend the results in [12] and [18] which lead to one and two dimensional preconditioning results for the constant coefficients case in Section 4. The variable coefficients case is dealt with in Section 5 using the tensor representation that appeared in [4]. In Section 6, we provide some numerical results which support the theories developed. Finally, we mention some conclusions in the last Section.

2. Preliminary. With the direction notation t = x or y, we assume that [M.sup.t] and [N.sup.t.sub.j] are natural numbers. Let [{[t.sub.k]}.sup.[M.sup.t].sub.k=0] to be the knots in the interval I = [-1,1] such that

-1 =: [t.sub.0] < [t.sub.1] < ... < [t.sub.[M.sup.t]-1] < [t.sub.[M.sup.t]] := 1.

Let [{[eta]k}.sup.[N.sup.t.sub.j].sub.k=0] and [{[w.sub.k]}.sup.[N.sup.t.sub.j].sub.k=0]] be the Legendre-Gauss-Lobatto (=: LGL) points in I arranged by

-1 =: [[eta].sub.0] < [[[eta].sub.1] < ... < [[eta].sub.[N.sup.t.sub.j]-1] < [[eta].sub.[N.sup.t.sub.j] :=1

and its corresponding LGL weights respectively. Here [M.sup.t] denotes the number of subintervals of I = [-1,1] and [N.sup.t.sub.j] denotes the number of LGL points on a [j.sup.th] subinterval by a translation of I. By the translation from I to a [j.sup.th] subinterval [I.sup.t.sub.j] := [[t.sub.j-1], [t.sub.j]] we denote [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] as the [k.sup.th] - LGL points in each subinterval [I.sup.t.sub.j] for j = 1, 2, ..., [M.sup.t] and enumerate them as

(2.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and the corresponding LGL weights [{[[rho].sup.t.sub.j,k]}.sup.[N.sup.t.sub.j].sub.k=0] are given by

(2.2) [[rho].sup.t.sub.j,k] = [h.sup.t.sub.j]/2[w.sub.k], j = 1,2, ..., [M.sup.t].

With [[xi].sup.t.sub.[M.sup.t+1,0]] := [t.sub.[M.sup.t]], note than in (2.1) and (2.2)

(2.3) [[xi].sup.t.sub.j-1],[N.sup.t.sub.j] = [[xi].sup.t.sub.j,0], [[rho].sup.t.sub.j-1], [N.sup.t.sub.j] = [[rho].sup.t.sub.j,0], j = 2, ..., [M.sup.t] + 1.

Let [P.sub.k] be the space of all polynomials [p.sub.k] (t) defined on I whose degrees are less than or equal to k and let [P.sup.h.sub.[N.sup.t.sub.j]] be the subspace of C[-1,1] consisting of piecewise polynomials of degree less than or equal to [N.sup.t.sub.j] in [I.sup.t.sub.j]. The basis for [P.sup.h.sub.[N.sup.t.sub.j]] is given by a piecewise Labasis grange polynomial basis [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] with respect to g which satisfy

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where k = 1,2, ..., [N.sup.t.sub.j] - 1, q = 0, 1, ..., [N.sup.t.sub.j] and i, j = 1, ... [M.sup.t] and [delta] denotes the Kronecker delta function. Even though this Lagrangian basis is actually rather easy to work with providing preconditioning results, one may prefer another basis {[phi]v(t)}. The change of basis may be accomplished algebraically by use of the matrix G given by [G.sub.[micro]v] = [phi]v ([xi][micro]). Then if H is any matrix representation of an operator H : [P.sup.h.sub.[N.sup.t.sub.j]] [right arrow] [P.sup.h.[N.sub.t.sub.j]] given in terms of the representations via the {[phi][micro]} basis then the matrix representation H of H in the Lagrangian basis {[phi][micro]} is given by H = GH[G.sup.-1]. Hence it may be enough for us to use the above piecewise Lagrangian basis functions in this paper. For two dimensional high-order space, let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

whose basis functions are given by tensor products of one dimensional piecewise Lagrange polynomials. Let [V.sub.[N.sup.t.sub.j]] be the space of all piecewise Lagrange linear functions [psi]k (x) with respect to on I. Define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] as the space of all piecewise Lagrange linear functions [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] with respect to G. For two dimensional piecewise linear space, let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

hose basis functions are given by tensor products of one dimensional piecewise Lagrange linear functions.

Define two interpolation operators [L.sub.[N.sup.t.sub.j]] : C[-1,1] [right arrow] [P.sub.[N.sup.t.sub.j]] (I) such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and [L.sup.h[N.sup.t.sub.j]] : C [-1,1] [right arrow] [P.sup.h.[N.sup.t.sub.j]] (I) such that

Define a discrete inner product [<u, v>.sub.N] On C[-1,1] x C[-1,1] as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and its corresponding norm is given by

[[parallel]u[parallel].sub.N] = [<u,u>.sup.1/2.sub.N], for u [member of] C[-1,1].

Finally, the notation a ~ b for any two real quantities a and b means by that there are two positive constants which do not depend on mesh sizes and degrees of polynomials such that 0 < c [less than or equal to] a/b < C < [infinity]. Using this notation, the LGL numerical quadrature rule for a polynomial of degree 2[N.sup.t.sub.j] (see [1], for example) can be compared as

(2.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

The notation (U, V) stands for [SIGMA] [u.sub.i][u.sub.i] for any two vectors U = [([u.sub.1], ..., [u.sub.d]).sup.T] and V = [([v.sub.1], ... , [v.sub.d]).sup.T] where the superscript T denotes the transpose of a vector. The standard spaces [H.sup.1] and [L.sup.2] will be used.

3. Basic estimates. In this section, we will discuss some estimates of global interpolation operator [L.sup.h.sub[N.sup.t.sub.j]] in terms of [H.sup.1] and [L.sup.2] norms. For t [member of] [-1,1] and [S.sub.t] [member of] [[t.sub.j-1], [t.sub.j]] and a function u [member of] [H.sup.1], let

(3.1) vj(t) := u([S.sub.t]) = u ([h.sup.t.sub.j]/2 t + 1/2([t.sub.j-1] + tj)).

Then for k = 0, 1, ..., [N.sup.t.sub.j] we have

(3.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

which yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Also, we have

(3.3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where [[parallel] * [parallel].sub.1] denotes the standard Sobolev [H.sup.1] norm. From now on, we will use [|*|.sub.1] as the Sobolev [H.sup.1] seminorm and [parallel]*[parallel] as the usual [L.sup.2] norm. In order to discuss the piecewise linear finite elements preconditioner, it may be required to analyze the relations between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and [phi] in the sense of [H.sup.1]- and [L.sup.2]- norm. For this purpose, we recall the following lemma (see [1], [18, Lemma 7.2]) which can be also extended to higher dimensions; see in [18, Theorem 7.3]. We remark that the similar estimates with Chebyshev weight and Chebyshev-Gauss-Lobatto points are found in [1] and [11].

LEMMA 3.1. It follows that for all v [member of] [V.sub.[N.sup.t.sub.j]]

(3.5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Note that the result [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] in (3.5) can be verified for any function v [member of] [H.sup.1](I) by modifying Theorem 1.7, Corollary 1.9 in Chapter II and Corollary 1.16, Theorem 1.19 in Chapter III with usages of Theorem 1.15, Lemma 1.18 and Proposition 1.17 in Chapter III therein in [1] where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] is found. For reader's convenience, we include the statement here.

PROPOSITION 3.2. For all v [member of] [H.sup.1] (I), there is a positive constant C such that

[|[L.sub.[N.sup.t.sub.j]]v|.sub.1] [less than or equal to] [|v|.sub.1].

Now the extension of Lemma 3.1 to the global interpolation operator [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] can be done easily by combining (3.3), (3.4) with Lemma 3.1. Here we state it as theorem.

THEOREM 3.3. For all u [member of] [V.sup.h.sub[N.sup.t.sub.j]]

[|[I.sup.h.sub.[N.sup.t.sub.j]] u|.sub.1] ~[|u|.sub.1].

LEMMA 3.4. For f [member of] [P.sup.h.sub[N.sup.t.sub.j]] [-1,1], it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Proof. First note that j (t) is a polynomial of degree [N.sup.t.sub.j] on [[t.sub.j-1],[t.sub.j]]. Then applying (2.4) on the interval [[t.sub.j-1], [t.sub.j]] and using (2.3) yield

(3.6) MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

In the last equivalence in (3.6), the observations (2.3) were used.

THEOREM 3.5. For all u [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], we have

(3.7) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Proof. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], Lemma 3.4 yields [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Hence for the proof of (3.7) it is enough to show that for u [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

(3.8) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Using (3.1) and (3.2) for functions vj [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and u [member of] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], we have

(3.9) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Since (see [12, Theorem 3.1])

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

it follows that, using (3.9),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Therefore, it is enough to show

(3.10) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Actually, because of (2.3) we can rewrite the left term of (3.10) as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Then one may see that (3.10) holds. These arguments complete the proof of (3.8) and consequently (3.7).

4. Case of constant coefficients: 1D and 2D. First, we discuss the one dimensional case. For convenience, let M := [M.sup.t] and [N.sub.j] := [N.sup.t.sub.j] for the one dimensional case only. Consider two uniformly positive definite elliptic operators defined in I = (-1,1) such that

(4.1) Lu = -([a.sub.1]u')' + [a.sub.2] u, in I, u(-1) = u'(1) = 0

and

(4.2) Bv = -([b.sub.1]v')' + [b.sub.2]u, in I, u(-1) = u'(1) = 0

where [a.sub.1], [b.sub.1] are positive constants and [a.sub.2], [b.sub.2] are nonnegative constants, leading to two bilinear forms on V x V, where V := {u [member of] [H.sup.1](I), u(-1) = u'(1) = 0},

[l.sub.1](u, v) = [[integral].sup.1.sub.-1] [a.sub.1]u'v' + [a.sub.2]uv dt and [b.sub.1] (u, v) = [[integral].sup.1.sub.-1] [b.sub.1]u'v' + [b.sub.2]uv dt.

For the high-order and piecewise linear approximations to (4.1) and (4.2), let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

whose suitable basis functions [{[[theta].sub.[micro]]}.sup.d.sub.[micro] =1] and [{[[psi].sub.v]}.sup.d.sub.v=1] , respectively, can be given, with

(4.3) d := dim ([P.sup.h,m).sub.Nj]) = dim([V.sup.h,m.sub.Nj]).

Then the stiffness matrix [L.sub.N] with high-order elements based on G of (4.1) is given by

[L.sub.N]([micro],v) = [l.sub.1] ([[theta].sub.[micro]], [[theta].sub.v]), [micro], v = 1, 2, ..., d,

and the stiffness matrix [B.sub.h] associated with piecewise linear elements based on G corresponding to (4.2) is given by

[B.sub.h] ([micro], v) = [b.sub.1] ([[psi].sub.[micro]], [[psi].sub.v], [micro], v = 1, 2, ..., d.

Denote [M.sub.N] and [M.sub.h] by mass matrices with respect to [{[[theta].sub.[micro]]}.sup.d.sub.[micro] = 1] and [{[psi].sub.[micro]]}.sup.d.sub.[micro] = 1], respectively. That is, [micro], v = 1, 2, ..., d,

[M.sub.N]([micro], v) = ([[phi].sub.[micro]], [[phi].sub.v]), [M.sub.h] ([micro], v) = ([[psi].sub.[micro]], [[psi].sub.v]).

Since all the stiffness and mass matrices are symmetric and positive definite, the preconditioned matrix below also has all positive real eigenvalues.

THEOREM 4.1. For every U = [([u.sub.1], [u.sub.2], ... [u.sub.d]).sup.T], we have

([B.sub.h] U,U) ~ ([L.sub.N]U,U), and ([M.sub.h] U,U) ~ ([M.sub.N], U,U).

Hence, the preconditioned matrix [B.sup.-1.sub.h] [L.sub.N] has all positive real eigenvalues [{[[lambda].sub.[micro]]}.sup.d.sub.[micro] = 1] independent of mesh sizes [h.sub.j] and degrees [N.sub.j] of polynomials. That is, there is absolute positive constants c and C such that

0 < c [less than or equal to] [[lambda].sub.[micro]] [less than or equal to] [infinity].

Proof. Let u(t) [member of] [V.sup.h,m.sub.Nj] be represented as u(t) = [[SIGMA].sup.d.sub.[micro] = 1] [u.sub.[micro]][[psi].sub.[micro]](t). Then its piecewise polynomial interpolation can be written as ([L.sup.h.sub.[N.sub.j]]u) (t) = [[SIGMA].sup.d.sub.[micro] = 1] [u.sub.[micro]][[theta].sub.[micro]] (t). The definitions of bilinear forms yield that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Then using Theorem 3.3 and 3.5 completes the proofs.

For actual computations, the bilinear form [l.sub.1] ([I.sup.h.sub.Nj] u, [I.sup.h.sub.Nj] v) and ([I.sup.h.sub.Nj] u, [I.sup.h.sub.Nj] u) will be calculated at LGL points. Define two matrices [L.sub.N] and [M.sub.N] as

[L.sub.N]([micro], v) = [l.sub.1,N]([[phi].sub.[micro]],[[phi].sub.v]), [M.sub.N]([micro],v) = [<[[phi].sub.[micro]],[[phi].sub.v]>.sub.N],

where

[l.sub.1,N](u,v) = [a.sub.1][<u',u'>.sub.N] + [a.sub.2][<u,v>.sub.N].

Note that [M.sub.N] is the diagonal matrix which consists of LGL weights, that is

[M.sub.N] = diag([[rho].sup.t.sub.j,k])

and employing (2.4) leads to

(4.4) ([L.sub.N]U, U) ~ ([L.sub.N]U,U), and ([M.sub.N]U, U) ~ ([M.sub.N]U, U)

and these matrices [L.sub.N] and [M.sub.N] are symmetric and positive definite.

COROLLARY 4.2. The preconditioned matrix [B.sup.-1.sub.h] [L.sub.N] has all positive real eigenvalues [{[[lambda].sub.[micro]]}.sup.d.sub.[micro = 1] independent of mesh sizes [h.sub.j] and degrees [N.sub.j] of polynomials. That is, there are absolute positive constants c and C such that

0 < c [less than or equal to] [[lambda].sub.[micro]] [less than or equal to] C < [infinity].

Proof. Let U = [([u.sub.1], [u.sub.2], ..., [u.sub.d]).sup.T] be any nonzero vector. Since

([L.sub.N] U,U)/([B.sub.h] U,U) = ([L.sub.N] U,U)/([L.sub.N]U,U) ([L.sub.N]U,U)/([B.sub.h]U,U)

using the min-max theorem, Theorem 4.1 and (4.4) we have the conclusion. This argument completes the proof because all involved matrices are symmetric and positive definite.

We now turn to the two dimensional case. For this, we consider the model elliptic operator L such that

Lu = -[[u.sub.xx] + [U.sub.yy]] + 2u, u = 0 on [[GAMMA].sub.D], n * [nabla]u = 0 on [[GAMMA].sub.N],

where [[GAMMA].sub.D] is the boundary described in (1.3), which leads to the bilinear form

(4.5) l(u,v) = ([nabla]u, [nabla]v) + 2(u,v), for u,v [member of] [H.sup.1.sub.D] ([OMEGA]),

where

[H.sup.1.sub.D]([OMEGA]) := {u [member of] [H.sup.1] ([OMEGA]) | u = 0 on [[GAMMA].sub.D]}.

Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Let us order the LGL points by horizontal lines and we list all LGL points [{[[XI].sub.P]}.sup.[d.sup.2].sub.P=1] as

[[XI].sub.P] = ([[xi].sub.[micro]],[[xi].sub.v]), where P = [micro] + d(v - 1), [micro] v = 1, 2, ..., d,

where d is defined in (4.3). Accordingly, we order the basis vectors [[PHI].sub.P] (x,y) [member of] [[P.sup.h,m].sub.N].sup.2] and [[PSI].sub.P] (x, y) [member of] [[[V.sup.h,m.sub.N].sup.2] in the same order. Let [L.sup.s.sub.[N.sup.2]] and [B.sup.s.sub.[h.sup.2]] be the stiffness matrices induced by (4.5) on the space [[[P.sup.h,m.sub.N]].sup.2] and [[[V.sup.h,m].sub.N]].sup.2], respectively. From now on, assume that

[a.sub.i] = [b.sub.i] = 1, i = 1,2

in the operators [L.sub.1] and [B.sub.1] in (4.1) and (4.2). Then using the one dimensional stiffness matrices [L.sub.N.sup.t.sub.j]], [B.sub.[h.sup.t.sub.j] and mass matrices [M.sub.[N.sup.t.sub.j], [M.sub.[h.sup.t.sub.j], we have

(4.6) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

(4.7) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

LEMMA 4.3. For every vector U = [([u.sub.1] ..., [u.sub.[d.sup.2]]).sup.T], we have

(4.8) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and

(4.9) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Proof. First note that all the matrices here are symmetric and positive definite. Hence it is enough to estimate (4.8) and (4.9) in terms of eigenvalues. Now because of Theorem 4.1 the conclusions (4.8) and (4.9) can be verified by following Lemma 5.4 in [12]. The details are as follows: Let [U.sup.1] = [([u.sub.1], [u.sub.2], ... [u.sub.d]).sup.T] and [V.sup.1] = [([v.sub.1], [v.sub.2], ..., [v.sub.d]).sup.T]. Theorem 4.1 implies that

(4.10) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Now consider eigenvalue problems

(4.11) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

From (4.10) we know that [kappa] and [lambda] are uniformly bounded in terms of mesh sizes [h.sup.x.sub.j], [h.sup.y.sub.j] and degrees [N.sup.x.sub.j], [N.sup.y.sub.j]. Note that each in (4.11) has a complete set of eigenvectors [U.sup.1.sub.[micro]] and [V.sup.1.sub.v], [micro], v = 1, ... , d. Therefore the vectors and eigenvalues

[Z.sub.[micro]v] = [U.sup.1.sub.[micro]] [cross product] [V.sup.-1.sub.v], [X.sub.[micro]v] = [V.sup.-1.sub.v] [cross product] [U.sup.1.sub.[micro]], [[LAMBDA].sub.[micro]v] = [[kappa].sub.[micro]][[lambda].sub.v]

are complete set of eigenvectors and eigenvalues of the eigenvalue problem

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Hence one can see the uniform bounds of eigenvalues [[LAMBDA].sub.[micro]v] because of the uniform bounds of [kappa] and [lambda] in terms of mesh sizes [h.sup.x.sub.j], [h.sup.y.sub.j] and degrees [N.sup.x.sub.j], [N.sup.y.sub.j].

PROPOSITION 4.4. For every U = [([u.sub.1], ..., [u.sub.[d.sup.2]]).sup.T], it follows that

([B.sup.s.sub.[h.sup.2]]U,U) ~ ([L.sup.s.sub.[N.sup.2]] U,U).

Hence the eigenvalues of [([B.sup.s.sub.[h.sup.2]]).sup.-1] [L.sup.s.sub.[N.sup.2]] are all positive and bounded. The bounds are independent of the mesh sizes [h.sup.x.sub.j], [h.sup.y.sub.j] and the degrees [N.sup.x.sub.j], [N.sup.y.sub.j] of polynomials.

Proof. It follows from Lemma 4.3 with (4.6) and (4.7).

For actual computations of (4.5), that is, for computations of [L.sup.s.sub.[N.sup.2]], we use LGL quadrature formula. For this, consider

[l.sub.N](u,v) = [<[nabla]u, [nabla]u>.sub.N] + [<u,v>.sub.N],

which can be written as, for u, v [member of] [[[P.sup.h,m.sub.N]].sup.2]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where the vectors U = [([u.sub.1], ..., [u.sub.[d.sup.2]]).sup.T] and V = [([v.sub.1], ..., [v.sub.[d.sup.2]]).sup.T] are vector representations of

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Now we will use the matrix [B.sup.s.sub.[h.sup.2]] in (4.7) as the preconditioner for

[L.sup.z.sub.[N.sup.2]]U = F

where

(4.12) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Then we can show that the eigenvalues of [([B.sup.s.sub.[h.sup.2]]).sup.-1] [L.sup.s.sub.[N.sup.2]] are bounded well in terms of mesh sizes [h.sup.x.sub.j], [h.sup.y.sub.j] and degrees [N.sup.x.sub.j], [N.sup.y.sub.j].

LEMMA 4.5. For every vector U = [([u.sub.1], ... [u.sub.[d.sup.2]]).sup.T], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Proof. Recall that A [cross product] B is symmetric and positive definite if the matrices A and B are symmetric, positive definite. Note that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Therefore, due to min-max theorem and Lemma 4.3, it is enough to show that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

are bounded independently of degrees [N.sup.x.sub.j], [N.sup.y.sub.j] and mesh sizes [h.sup.x.sub.j], [h.sup.y.sub.j]. Due to (4.4), this can be done by following the similar arguments of Lemma 4.3. These arguments complete the proof.

THEOREM 4.6. For every vector U = [([u.sub.1], ..., [u.sub.[d.sup.2]]).sup.T], it follows that

(4.13) ([B.sup.s.sub.[h.sup.2]] U,U) ~ ([L.sup.s.sub.[N.sup.2]U,U).

Hence the eigenvalues of [([B.sup.s.sub.[h.sup.2]]).sup.-1] [L.sup.s.sub.[N.sup.2]] are all positive and bounded. The bounds are independent of the mesh sizes [h.sup.x.sub.j], [h.sup.y.sub.j] and the degrees [N.sup.x.sub.j] [N.sup.y.sub.j].

Proof. It comes from (4.12) and (4.7) and Lemma 4.5

5. Case of variable coefficients: 2D. Consider the bilinear form corresponding to (1.1) and (1.2) as

(5.1) [l.sub.p](u,v) = (p(x,y) [nabla]u, [nabla]v + (q(x,y)u,v) for u,v [member of] [H.sup.1.sub.D] ([OMEGA]).

Let us denote [D.sub.[N.sup.t.sub.j]] by the differentiation matrix at LGL points (see [4] for example) and diagonal matrices P and Q by

P := diag([p.sub.[alpha]] := [p.sub[micro]v]), Q := diag([g.sub.[alpha]] := [q.sub.[micro]v]), [alpha] = [micro] + d(v - 1)

occurred from the expansions of the p(x, y) and q(x, y) in terms of 2D Lagrangian basis functions such that p(x, y) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and q(x, y) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], respectively. Then we will use the tensor representation for the approximations to (5.1) on the space [[[P.sup.h,m.sub.N]].sup.2] given by (see detailed discussions in [4])

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where [E.sub.[N.sup.t.sub.j]] is the identity matrix of order d

[W.sup.S.sub.N] := S([M.sub.[N.sup.y.sub.j]] [cross product] [M.sub.[N.sup.x.sub.j]], where S = P or Q.

Note that the matrix [W.sup.S.sub.N] is diagonal whose elements are positive because the matrices S(= P, Q) and ([M.sub.[N.sup.y.sub.j]] [cross product] [M.sub.[N.sup.x.sub.j]] are diagonal with positive elements. Further, if the matrix P is the identity and the matrix Q is 2E, then the matrix [L.sub.[N.sup.2]] is the same as [L.sup.S.sub.[N.sup.2]] in (4.12) with

[L.sub.[N.sup.t.sub.j]] = [D.sup.T.sub.[N.sup.t.sub.j]] [M.sub.[N.sup.t.sub.j]], t = x,y.

LEMMA 5.1. For any vector U = [([u.sub.1], ..., [u.sub.[d.sup.2]]).sup.T, it follows that

(5.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

(5.3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

(5.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where the matrix equivalence A ~ B should be understood as

(AU, U) ~ (BU, U).

Proof. Note that the variable coefficients p(x, y) and q(x, y) are positive bounded functions and the matrices [W.sup.S.sub.[N.sup.ys]], and ([M.sub.[N.sup.y.sub.j]] [cross product] [M.sub.[N.sup.x.sub.j]]) are diagonal with positive elements. Hence for any vector U it follows immediately that

(5.5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

This argument complete (5.4). Let V = ([E.sub.[N.sup.y.sub.j]] [cross product] [D.sub.[N.sup.x.sub.j]]. Since

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

we have the conclusion (5.2) with help of (5.5). The similar arguments complete (5.3). [] The main goal of this section is to show that the eigenvalues of the preconditioned matrix

[([B.sup.s.sub.[h.sup.2]]).sup.-1] [L.sub.[N.sup.2]]

are real and bounded as follows.

THEOREM 5.2. For any vector U = [([u.sub.1], ..., [u.sub.[d.sup.2]]).sup.T], we have

([B.sup.s.sub.[h.sup.2]]U,U) ~ (L.sub.[N.sup.2]] U,U).

In the sense of eigenvalues, it follows that all eigenvalues of the matrix [([B.sup.s.sub.[h.sup.2]]).sup.-1] [L.sub.[N.sub.2]] are real positive and bounded. The bounds are independent of the mesh sizes hjx, by and the degrees [N.sup.x.sub.j], [N.sup.y.sub.j] of piecewise polynomials.

Proof. Note that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Therefore, using Lemma 5.1 one may see that

([L.sub.[N.sup.2]]U,U) ~ ([L.sup.s.sub.[N.sup.2]]U,U).

From Theorem 4.6,

(L.sup.s.sub.[N.sup.2]]U,U) ~ ([B.sup.s.sub.[h.sup.2]]U,U).

These arguments complete the proof.

[FIGURE 6.1 OMITTED]

6. Computational results. Because there are numerical results reported already in [6] and [8], we discuss a few numerical experiments for one dimensional problems. Consider

(6.1) Lu = -(p(x)u')' + q(x)u, x [member of] (0,1)

with boundary conditions u(0) = u(1) = 0. Let us take the preconditioner operator B as

(6.2) Bu = -u" + [gamma]u, x [member of] (0,1)

with the same homogeneous Dirichlet boundary conditions where [gamma] will be chosen later. In the following numeric tests, the uniform mesh size h = [h.sup.x.sub.j] and uniform degree N = [N.sup.x.sub.j] for j = 1, ..., [M.sup.x] are used.

EXAMPLE 6.1. With a chosen p(x) = 1 + [x.sup.2] and q(x) = [e.sup.x] in (6.1), we discuss the optimal preconditioning operator (6.2) by considering several [gamma]. We will take [gamma] = k x 0.1 where [kappa] is an integer between -5 and 8. The Fig. 6.1 shows that the condition number of the preconditioned matrix [B.sup.-1.sub.h] [L.sub.N] becomes small relatively if we choose [gamma] near 0 among other [gamma]'s. These phenomena were pointed out in [9] if (6.1) is discretized by a finite difference scheme, that is to say, [gamma] may be chosen by considering the advection coefficient in (6.1). Hence one may choose [gamma] = 0 in this case.

EXAMPLE 6.2. Stimulated by the numerical results in Example 6.1, we will take [gamma] = 0 for the preconditioner operator B while p(x) = q(x) = 1 in (6.1) are taken. The condition numbers of the matrix [L.sub.N] are shown in Fig. 6.2 for various mesh sizes and degrees of polynomials. Then we enumerate condition numbers of the preconditioned matrix [B.sup.-1.sub.h] [L.sub.N] in Fig. 6.2 also, which shows that the condition numbers can be fixed for mesh sizes and degrees of polynomials. We point out that the condition numbers grow as [h.sup.-2] for a fixed degree of polynomial and O([N.sup.3]) for a fixed mesh size. These also can be proven in a standard finite element theory and in spectral methods; see [1]. These phenomena are depicted in Fig. 6.3.

7. Conclusion. As we have shown that the condition numbers of the preconditioned systems are well bounded, it is possible to use AMG algorithms without increasing complexity for solving elliptic boundary value problems with high-order discretizations based on LGL quadrature nodes. As an immediate application, one may apply the techniques here to a first-order system of least-squares for an elliptic problem whose systems are found in [2], combining the results here and in [12] (for example, one may refer to [10]). In order to avoid the non-nested property of irregular LGL nodes occurring in the multigrid method, one may use Chebyshev-Gauss-Lobatto nodes for discretizations which has a nested property in communications at each level. This case will be dealt in a forthcoming paper.

[FIGURE 6.2 OMITTED]

[FIGURE 6.3 OMITTED]

Acknowledgement. The author deeply thanks Professor Manteuffel for his kind guidance in preparing the present topic and also thanks to anonymous referees for pointing out some corrections.

* Received April 3, 2006. Accepted for publication January 1, 2007. Recommended by T. Manteuffel. This work was supported by KRF R02-2004-000-10109-0 (KOSEF 000006).

REFERENCES

[1] C. BERNARDI AND Y. MADAY, Approximation Spectrales de Problemes aux Limites Elliptiques, Springer, Paris, 1992.

[2] Z. CAI, T. MANTEUFEEL, AND S. MCCORMICK, First-order system least squares for second-order partial differential equations: Part II, SIAM J. Numer. Anal., 34 (1997), pp. 425-454.

[3] M. O. DEVILLE AND E. H. MEND, Finite element preconditioning for pseudospectral solutions of elliptic problems, SIAM J. Sci. Stat. Comput., 11 (1990), pp. 311-342.

[4] M. O. DEVILLE, P. F. FISCHER, AND E. H. MEND, High-order Methods for Incompressible Fluid Flow, Cambridge Monographs on Applied and Computational Mathematics, Cambridge Univ. Press, Cambridge, UK, 2002.

[5] M. DRYJA, B. SMITH, AND O. W IDLUND, Schwarz analysis of iterative substructuring algorithms for elliptic problems in three dimensions, SIAM J. Numer. Anal., 31 (1994), pp. 1662-1694.

[6] P. FISCHER, An overlapping Schwarz method for spectral element solution of the incompressible Navier-Stokes equations, J. Comput. Phys., 133 (1997), pp. 84-101.

[7] P. FISHER AND E. RONQUIST, Spectral element methods for large-scale parallel Navier-Stokes calculations, Comput. Method Appl. Math., 116 (1994), pp. 69-76.

[8] J. HEYS, T. MANTEUFFEL, S. MCCORMICK AND L. OLSON, Algebraic multigrid(AMG) for high-order finite elements, J. Comput. Phys., 204 (2005), pp. 520-532.

[9] T. MANTEUIFEL AND J. OTTO, Optimal equivalent preconditioners, SIAM J. Numer. Anal., 30 (1993), pp. 790-812.

[10] S. D. Kim, H.-C. LEE, AND B. C. SHIN, Pseudospectral least-squares method for the second-order elliptic boundary value problem, SIAM J. Numer. Anal., 41 (2003), pp. 1370-1387.

[11] S. D. KIM AND S. PARTER, Preconditioning Chebyshev spectral collocation method for elliptic partial differential equations, SIAM J. Numer. Anal., 33 (1996), pp. 2375-2400.

[12] S. PARTER AND E. ROTHMAN, Preconditioning Legendre spectral collocation approximations to elliptic problems, SIAM J. Numer. Anal., 32 (1995), pp. 333-385.

[13] S. PARTER, Preconditioning Legendre spectral collocation methods for elliptic problems L Finte element operators, SIAM J. Numer. Anal., 39 (2001), pp. 348-362.

[14] L. PAVARINO AND O. WIDLUND, A polylogorithmic bound for an iterative substructuring method for spectral element in three dimensions, SIAM J. Numer. Anal., 33 (1996), pp. 1303-1335.

[15] A. QUARTERONT AND E. ZAMPIERI, Finite element preconditioning for Legendre spectral collocation approximations to elliptic equations and systems, SIAM J. Numer. Anal., 29 (1992), pp. 917-936.

[16] J. RUDE, AMG for high-order discretiztions of second-order elliptic problems, in: Abstract of the Eleventh Copper Mountain Conference on Multigrid Methods (http://www.mgnet.org/ mgnet/Conference /CopperMtn03/'falks/ruge.pdf), 2003.

[17] A. ST-CYR, M. GANDER, AND S. THOMAS, On optimized Schwarz preconditioning for high-order spectral methods, Twelfth Copper Mountain Conference on Multigrid Methods, 2005.

[18] A. TOSELLI AND O. W IDLUND, Domain Decomposition Methods- Algorithms and Theory, Springer Series in Computational Mathematics, Springer, Berlin, Heidelberg, 2005.

[dagger] Department of Mathematics, Kyungpook National University, Daegu 702-701, Korea (skim@knu.ac.kr).

Printer friendly Cite/link Email Feedback | |

Author: | Kim, Sang Dong |
---|---|

Publication: | Electronic Transactions on Numerical Analysis |

Date: | Jan 1, 2007 |

Words: | 6440 |

Previous Article: | Block triangular preconditioners for M-matrices and Markov chains. |

Next Article: | Solving linear systems with a Levinson-like solver. |