Abstract
In this paper, a fully non-conforming least-squares spectral element method for fourth order elliptic problems on smooth domains is presented. The proposed method works for a general fourth order elliptic operator with non-homogeneous data in two dimensions and gives exponentially accurate solutions. We derive differentiability estimates and prove our main stability estimate theorem using a non-conforming spectral element method. We then formulate a numerical scheme using a block diagonal preconditioner. Error estimates are also proven for the proposed method. We provide the computational complexity of our method and present results of numerical simulations that have been performed to validate the theory.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
The h–p version of the finite element method (FEM) for elliptic problems was proposed in the mid-80’s by Babuška et al. [3, 4] for solving problems in structural mechanics. The h–p version simultaneously refines the mesh and increases the polynomial degree achieve optimal convergence. The h–p version of spectral element method (SEM) as compared to FEM employ polynomials of higher degree in order to recover the so called spectral/exponential convergence. It is well established that SEM deliver exponential convergence for elliptic problems with smooth solutions and have been successfully implemented to many practical problems [24, 30]. In this paper we describe an efficient and exponentially accurate least-squares spectral element method for fourth order elliptic problems on smooth domains. Such problems include examples of the classical plate bending problem in the theory of elasticity. This type of boundary value problems arise in structural mechanics, materials science and fluid flow.
Several methods have been proposed and analyzed both theoretically and computationally for fourth order elliptic problems in [7, 9, 13, 28, 34–36, 39–42, 44] (and references cited therein) and have been shown to be very effective. In [9], Ben-Artzi et al. presented a fast direct solver for the Dirichlet biharmonic problem in a rectangle based on the capacitance matrix method of [13, 14]. The resulting linear system is solvable in \(O(N^2 \log N)\), where N is the number of grid points in each direction. Bernardi et al. [7] presented some spectral approximations of two-dimensional fourth-order problems. Preconditioning of thin solids in structural mechanical problems was analyzed in [28] using \(p-\)version FEM. It is shown that the method performs well for modelling many real world problems such as skin of an aircraft, laminated fibre plate, microstructure of composite materials etc. These preconditioners are constructed using classical additive Schwarz method which is essentially a generalization of the block Jacobi method to allow for overlapping of the blocks.
In [34], Shen proposed an efficient spectral-Galerkin method for the second and fourth order equations using Legendre polynomials. The two books by Shen and coworkers [35, 36] deal with many important practical aspects of computations using spectral methods and present the recent research in the subject. Zhang et al. [41] developed nearly optimal solvers for the linear algebraic systems for fourth order problems on arbitrary polygonal domains that are partitioned by unstructured grids in the framework of finite element methods. They proved that such a system can be solved in \(O(N\log N)\) operations on an unstructured grid of size N. We refer to the work by Meleshko [29] for a comprehensive history and summary of results available for the biharmonic problem in two dimensions. Recently, Yu et al. [39, 40] proposed spectral element method for mixed inhomogeneous boundary value problems of fourth order and also discussed spectral method for fourth-order problems on quadrilaterals.
The least-squares methods are well suited for the numerical solution of partial differential equations. However, the convergence of the least-squares approach in solving biharmonic problems depends on the convergence of fourth order derivatives which is an essential disadvantage in comparison with the conventional Galerkin or weak formulation approach, where only the convergence of the second order derivatives is required for solving biharmonic problems. Secondly, the resulting coefficient matrices are essentially more ill-conditioned as compared to the Galerkin methods. This can be easily circumvented by properly selected preconditioners. On the other hand, the least-squares methods give rise to symmetric, positive definite matrices and does not require numerical integration. Moreover, least-squares approach can be used for solving problems on complicated geometries.
The least squares spectral element method (LSQ-SEM) is a very promising numerical method developed by Proot et al. [32], and Potanza et al. [31] which combine the least squares formulation with the spectral element approximation. LSQ-SEM combines the generality of finite element methods, the accuracy of the spectral methods and the theoretical and computational advantages of the algorithmic design and implementation into a general mathematical framework. LSQ-SEM has been successfully applied to many interesting problems (see [18–21, 25, 31, 32, 37, 38, 43]). However, their implementation to the fourth order problems has been limited so far.
In [18–20, 37, 38], an exponentially accurate h–p spectral element method was proposed for two dimensional elliptic problems on non-smooth domains using parallel computers. The key ingredients were use of auxiliary mappings and geometrical mesh near corners, proposed originally by Babuška et al. [3, 4]. The analysis of LSQ-SEM for Stokes and Navier-Stokes is given in [31, 32]. Recently, an exponentially accurate nonconforming LSQ-SEM for elliptic problems on unbounded domain is presented in [25]. LSQ-SEM solution of the gas-liquid multi-fluid model coupled with the population balance equation is discussed in [43]. A discrete weighted least-squares method for the Poisson and biharmonic problems on circular and annular domains was presented by Zitnan [44] having smooth solutions. The resulting matrices were preconditioned using algebraic polynomials, suitably chosen collocation (matching) points and weight factors. However, the method is not suitable for problems on irregular domains. For a complete survey of spectral element methods and their applications to elliptic boundary value problems we refer to the monograph by Karniadakis et al. [24] which summarizes the recent developments in the subject.
We choose as our solution the spectral element function which minimizes the sum of a squared norm of the residuals in the partial differential equations and the squared norm of the residuals in the boundary conditions in fractional order Sobolev spaces and enforce continuity by adding a term which measures the jump in the function and its derivatives at inter-element boundaries in fractional Sobolev norms, to the functional being minimized. The method we shall describe is a least-squares collocation method and to obtain our approximate solution we solve the normal equations using preconditioned conjugate gradient method (PCGM). The residuals in the normal equations can be obtained without computing and storing mass and stiffness matrices [37, 38]. A preconditioner is defined for the method which is a block diagonal matrix, where each diagonal block corresponds to an element. It is shown in [23] that there exists a new preconditioner which is a diagonal matrix on each element.
We remark here that after obtaining our approximate solution at the Gauss-Lobatto-Legendre points consisting of non-conforming spectral element functions we can make a correction to it so that the corrected solution is conforming and is an exponentially accurate approximation to the true solution in the \(H^2\) norm over the whole domain. These corrections are similar to those for second order elliptic problems described in [33, 38]. However, our computational results do not include these corrections. We also emphasize that for simplicity we consider only curvilinear domains although our results have a more general character. The method works for non self-adjoint problems too. Computational results for a non self-adjoint problem with variable coefficients are provided. Throughout this paper, \(\Omega \) will denote a curvilinear domain in \(\mathbb {R}^{2}\) and \((x_{1},x_{2})\) will denote the standard Cartesian coordinates. We shall also denote the Cartesian coordinates by (x, y).
The organization of this paper is as follows. In Sect. 2, we introduce the problem under consideration. In Sect. 3, we drive differentiability estimates, define the spectral element functions and prove the stability estimate which is the main result of this paper. Numerical scheme and error estimates are provided in Sects. 4 and 5 respectively. Sections 6 is dedicated to computational results for various test problems on with analytic solutions. Concluding remarks and some outlines for future work are provided in Sect. 7.
2 Preliminaries
Let \(\Omega \) denote a curvilinear domain in \(\mathbb {R}^2\) with smooth boundary. We shall denote the boundary of \(\Omega \) by \(\partial \Omega \). Consider the fourth order elliptic problem with non-homogeneous Dirichlet boundary conditions
Here, \(\nu \) denotes the outward unit normal vector to the boundary \(\partial \Omega \). The data f is analytic on \(\bar{\Omega }\) and \(\Phi \), \(\Psi \) are analytic on \(\partial \Omega \). The problem (2.1) describes the vibration of a homogeneous non-clamped isotropic plate with constant thickness. The thickness is assumed to be much smaller that the other two dimensions of the plate.
We need to review a set of function spaces. Let \(w(x_1,x_2)\) be a smooth function. By \(H^m(\Omega )\), we denote the usual Sobolev space of integer order \(m\ge 0\) furnished with the norm
where \(\alpha =(\alpha _1,\alpha _2), |\alpha |=\alpha _1+\alpha _2, \partial ^{\alpha }w=\partial ^{\alpha _1}_{x_1}\partial ^{\alpha _2}_{x_2}w=w_{x_{1}^{{\alpha }_{1}} x_{2}^{{\alpha }_{2}}}\) is the distributional (weak) derivative of w. As usual \(H^{0}(\Omega )=L^{2}(\Omega )\), and
A seminorm on \(H^m(\Omega )\) is given by
Further, let
denote the fractional Sobolev norm of order s, where \(0< s < 1\). Here, I denotes an interval contained in \(\mathbb {R}\).
We now cite a special case of important regularity result Theorem (7.2.2.3) of Grisvard [22].
Theorem 2.1
(Smooth regularity) Let \(w\in H^{2}(\Omega )\) be a solution of
with \(f\in H^{k}(\Omega )\), \(\Phi \in H^{k+7/2}(\partial \Omega )\) and \(\Psi \in H^{k+5/2}(\partial \Omega )\), \(k\ge -1\). Then \(w\in H^{k+4}(\Omega )\).
Using this it follows that if \(f\in L^{2}(\Omega ), \Phi \in H^{\frac{7}{2}}(\partial \Omega )\) and \(\Psi \in H^{\frac{5}{2}}(\partial \Omega )\), then the solution w of (2.1) belongs to \(H^{4}(\Omega )\).
Theorem 2.2
(Analytic regularity) For a curvilinear domain \(\Omega \) with analytic boundary \(\partial \Omega \), if the given data \(f,\Phi \) and \(\Psi \) are analytic then this implies analyticity of w and the following differentiability estimate
holds for all integers \(m\ge 1\). Here, C and d denote positive constants.
Proof
Since the solution w(x) is analytic in an open neighbourhood of \(\bar{\Omega }\). Hence, (2.2) follows. \(\square \)
3 Stability Estimates
First we divide the domain \(\Omega \) into a set of N quadrilaterals \(\Omega _1,\Omega _2,\ldots ,\Omega _N\) with smooth sides as shown in Fig. 1. Thus, the boundary \(\partial \Omega \) of \(\Omega \) is divided into analytic arcs \(\bar{\gamma }_{l}, 1\le l\le N\) i.e. \(\partial \Omega =\displaystyle {\bigcup _{l\in \mathcal {I}}}\bar{\gamma }_{l}\), where \(\mathcal {I}=\{1,2,\ldots ,N\}\). We shall assume that the data f is analytic on \(\bar{\Omega }\) and \(\Phi ,\Psi \) are analytic on every closed arc \(\bar{\gamma }_{l}\) and continuous on \(\partial \Omega \). Each of the quadrilaterals \(\{\Omega _{l}\}_{l=1,2,\ldots ,N}\) is mapped onto the master square \(S=(-1,1)\times (-1,1)\) by a set of analytic maps \(\{M_{l}^{-1}\}_{l=1,2,\ldots ,N}\), where \(M_{l}\) is from S to \(\Omega _{l}\). The map \(M_{l}\) is of the form
with \(X^{l}\) and \(Y^{l}\) being analytic functions on S. Thus, \(M_{l}=(X^{l},Y^{l})\). Let W denote an upper bound on the degree of the approximating polynomial. We shall assume that N is proportional to W. A set of non-conforming spectral element functions which are a sum of tensor products of polynomials in their respective coordinates are defined on the elements in \(\Omega \). Let \(\Omega _l\) be one of the elements into which \(\Omega \) is divided. We now define the spectral element function \(u_l\) on \(\Omega _l\) by
Let \(\{\mathcal F_u\}\) denote the spectral element representation of the function u and \({\mathcal S}^{N,W}(\Omega )\) denote the space of spectral element functions \(\mathcal F_u\) over the whole domain \(\Omega \). To state our main stability theorem we shall define two quadratic forms \(\mathcal V^{N,W}\left( \{\mathcal F_u\}\right) \) and \(\mathcal U^{N,W}\left( \{\mathcal F_u\}\right) \).
Let \(\left. {[u]}\right| _{\gamma _{l,i}}\) denote the jump in u across the side \(\gamma _{l,i}\). Let the side \(\gamma _{l,i}=\gamma _{m,j}\), where \(\gamma _{m,j}\) is one of the sides of the element \(\Omega _m\). We assume that the side \(\gamma _{l,i}\) corresponds to \(\xi =1\) and \(\gamma _{m,j}\) corresponds to \(\xi =-1\). Then, \(\left. {[u]}\right| _{\gamma _{l,i}}\) is a function of \(\eta \) only. Let \(J_{l}(\xi ,\eta )\) is the Jacobian of the mapping \(M_{l}\) from S to \(\Omega _{l}\) and let \(\mathscr {L}_l u_{l}(\xi , \eta ) =\mathcal {L}u_l(M_l(\xi ,\eta ))\sqrt{J_{l}}\). Now we have to approximate
Hence,
Let \((\mathscr {L}_{l})^{a}\) denotes a differential operator which is an approximation to \(\mathscr {L}_{l}\) in which the coefficients of \(\mathscr {L}_{l}\) are replaced by polynomial approximation. Then it is easy to prove that for W large enough
Here, C is a constant and \(\varepsilon _{W}\rightarrow 0\) as \(W\rightarrow \infty \). In fact the rate of the convergence of \(\varepsilon _{W}\rightarrow 0\) decays exponentially in W (the rest of the proof is given in Sect. 5). We now define the quadratic form
The fractional Sobolev norms used above are as defined in [22].
Since \(\gamma _{l,i}\), corresponding to \(\xi =1\), is the image of the interval \(I=(-1,1)\), in \(\eta \) coordinates
for \(0< \sigma < 1\). Moreover,
Next, we define the quadratic form
We now state our main stability estimate theorem.
Theorem 3.1
Consider the fourth order elliptic boundary value problem (2.1). Then
At the same time there exists a constant K (using trace theorems) such that
Proof
By Lemma 3.2, there exists \(\{\mathcal F_v\}\) such that \(w=u+v\in H^{4}(\Omega )\). Using Minkowski’s inequality, we can write the following estimate
Hence, by regularity result stated in Theorem 2.1, the estimate
holds.
Inserting the results from Lemma 3.1 and 3.2 in Eq. (3.8), the desired result follows. \(\square \)
3.1 Technical Results
Lemma 3.1
Let \(\{\mathcal F_u\}\in {\mathcal S}^{N,W}(\Omega )\). Then there exists \(\{\mathcal F_v\}\) such that \(v_{l}\in H^{4}(S)\), for \(l=1,2,\ldots ,N\) and \(u+v\in H^{4}(\Omega )\). Moreover, the estimate
holds. Here, \(\epsilon _{W}\) is exponentially small in W.
Proof
Proof of Lemma 3.1 is very similar to the proof of Lemma 7.1 of [18] and we omit the details. \(\square \)
Lemma 3.2
Let \(w=u+v\in H^{4}(\Omega )\). Here, \(\{\mathcal F_u\}\in {\mathcal S}^{N,W}(\Omega )\) and \(\{\{{v}_{l}(\xi ,\eta )\}_{l}\}\) is as defined in Lemma 3.1. Then the estimate
holds. Here, \(\epsilon _{W}\) is exponentially small in W.
Proof
By the Lemma 3.1, there exists \(\{\mathcal F_v\}\) such that \(v_{l}\in H^{4}(S)\), for \(l=1,2,\ldots ,N\) and \(u+v\in H^{4}(\Omega )\). Using Minkowski’s inequality, the following estimate
holds.
Applying trace theorem, we obtain
Using the result from Lemma 3.1 in Eq. (3.10), we get the final result. \(\square \)
4 Numerical Scheme
Let \(f_{l}=f(X^l(\xi ,\eta ), Y^l(\xi ,\eta ))\), for \(1\le l\le N\). Let \(\tilde{f}_l(\xi ,\eta )\) denote the polynomial of degree \(2W-1\) in \(\xi \) and \(\eta \) which is the orthogonal projection of \(f_{l}(\xi ,\eta )\) into the space of polynomials of degree \(2W-1\) with respect to the usual inner product on \(H^4(S)\). Let \(\gamma _{l,i}=\gamma _{i}\cap \partial \Omega _{l}\) be the image of \(\xi =-1\) under the mapping \(M_{l}:S\rightarrow \Omega _{l}\). Let \(\Phi (X^l(-1,\eta ),Y^l(-1,\eta )) =\Phi _{l}(\eta )\) and let \(\tilde{\Phi }_{l}(\eta )\) denote the orthogonal projection of \(\Phi _{l} (\eta )\) into the space of polynomials of degree \(2W-1\) in \(\eta \) with respect to the usual inner product in \(H^{4}(-1,1)\). Let \(\Psi (X^l(-1,\eta ),Y^l(-1,\eta ))=\Psi _l(\eta )\) and let \(\tilde{\Psi }_{l}(\eta )\) denote the orthogonal projection of \(\Psi _{l}(\eta )\) into the space of polynomials of degree \(2W-1\) in \(\eta \) with respect to the usual inner product in \(H^4(-1,1)\). Let \(J_l\) denote the Jacobian of the mapping \(M_l\) as before. Define
We now define the least-squares functional
Our numerical scheme may now be formulated as
Theorem 4.1
Find \(\mathcal F_s\in {\mathcal S}^{N,W}(\Omega )\) which minimizes the functional \(\mathcal R^{N,W}(\{\mathcal F_u\})\) over all \(\mathcal F_u\in {\mathcal S}^{N,W}(\Omega )\).
This functional \(\mathcal {R}^{N,W}\left( \{\mathcal F_u\}\right) \) is closely related to quadratic form in the stability estimate in Theorem 3.1. Using quadratures we can exactly evaluate the functional \(\mathcal {R}^{N,W}\left( \{\mathcal F_u\}\right) \). Thus, we find a solution which minimizes the sum of \(L^2\) norm of residuals in the partial differential equation and fractional Sobolev norm of the residuals in the boundary conditions and enforce continuity by a adding a term which measures the sum of the squares of the jumps in the function and its derivatives at the inner-element boundaries in appropriates Sobolev norm.
Now
for all V, where U is a vector assembled from the values of \(\{(u_{l}(\xi ,\eta ))\}\).
Similarly V is a vector assembled and G is assembled from the data. Here S and T denote matrices. Thus we have to solve \(SU-TG=0\).
The method is essentially a least-squares method and the normal equations can be solved using the preconditioned conjugate gradient method (PCGM). To be able to do so we must be able to compute the residuals in the Normal equation inexpensively. Let the normal equations be
Thus at each iteration of the PCGM we have to compute the action of a matrix on a vector. The feasibility of such a process depends on the ability to compute \(A^TAU\) efficiently and inexpensively for any vector U. As in [18–20] it can be shown that \(A^TAU\) can be computed inexpensively without computing the mass and stiffness matrices.
However, in addition to this it is imperative that we should be able to construct an effective preconditioner for the matrix \(A^TA\) so that the condition number of the preconditioned system is as small as possible. If this can be done then it will be possible to compute \((A^TA)^{-1}G\) efficiently using the PCGM for any vector G.
4.1 Parallelization and Preconditioning
This quadratic form \(\mathcal {V}^{N, W}(\{\mathcal F_v\})\) is equivalent to the functional \(\mathcal {R}^{N,W} (\{\mathcal F_v\})\) with zero data. Define a quadratic form \(\mathscr {U}^{N,W}(\{\mathcal F_v\})\), where
Here, \(\mathscr {U}^{N,W}(\{\mathcal F_v\})\) is the preconditioner for \(\mathcal {V}^{N,W}(\{\mathcal F_v\})\). Now, we find the estimate of condition number of the preconditioner \(\mathscr {U}^{N,W}(\{\mathcal F_v\})\).
Using Theorem 3.1, the following result holds
where K is a constant. From (4.3), we observe that the condition number of the preconditioned system is \(O({(\log W)^{4}})\). Now \(\check{v}_{l}\) is defined in terms of Legendre polynomials in \(\xi \) and \(\eta \). The form of \(\check{v}_{l}\) is
The coefficients \(a_{i,j}\) are arranged lexicographically in i and j. The detail of the computation of preconditioner is given in [17, 23]. Each element is mapped to a single processor for ease of parallelism. During the PCGM process, communication between neighbouring processors is confined to the interchange of information consisting of the value of function and its derivatives at inter-element boundaries. In addition we need to compute two global scalars to update the approximate solution and the search direction. Hence inter-processor communication is quite small.
5 Error Estimates
In this section we obtain the error estimates for the proposed method. If u is smooth then the proposed method gives spectral accuracy in W, however if u is analytic then the method gives exponential accuracy in W. The optimal rate of convergence with respect to \(W_{dof}\), the number of degrees of freedom is also provided.
Let \(\{\mathcal F_{z}\}\) minimize \(\mathcal R^{N,W}(\{\mathcal F_u\})\) over all \(\{\mathcal F_{u}\}\in {\mathcal S}^{N,W}(\Omega )\). We write one more representation for \(\{\mathcal F_{z}\}\) as \(\{\mathcal F_{z}\}=\left\{ \left\{ z_l(\xi ,\eta )\right\} _{l=1}^{N}\right\} \).
Consider a typical quadrilateral \(\Omega _{l}\) into which \(\Omega \) is divided. Let
where the general form of the mapping \(M_{l}=(X^{l}(\xi ,\eta ),Y^{l}(\xi ,\eta ))\) from S to \(\bar{\Omega }_{l}\) has been defined in [4]. Then the following has been proved in Lemma 5.1 of [4].
Theorem 5.1
(Lemma 5.1 of [4]) If \(U_l\) is analytic on \(\bar{S}\) then for some constant C and d independent of l and \(|\alpha |=m\), \(m=1,2,\ldots \), we have
Our main theorem on error estimates is now stated.
Theorem 5.2
Let \(\{\mathcal F_{z}\}\) minimize \(\mathcal R^{N,W}(\{\mathcal F_u\})\) over all \(\{\mathcal F_{u}\}\in {\mathcal S}^{N,W}(\Omega )\). Then there exist a constant \(C_s\) such that
Here, \(\mathcal E^{N,W}\left( \{\mathcal F_{(z-U)}\}\right) \) is as defined in (3.3) and \((\mathbf I )=\displaystyle {\sum _{l=1}^{N}}||U_l||_{s,S}^2\).
Proof
Here, \(U_{l}(\xi ,\eta )=u(M_l(\xi ,\eta ))\). Then using the results on approximation theory as in Section 5 of [4] it follows that there exists a polynomial \(\phi _{l}(\xi ,\eta )\) of degree W in each variable separately such that
for \(0\le m\le 4\) and all \(W> s\), where \(C_{s}= C e^{2s}\). Hence
Let \(\tilde{f}_{l}\) be the polynomial of degree \((2W-1)\) in each variable separately which is the orthogonal projection of \(f_{l}\) in \(H^{4}(S)\) into the space of polynomials of degree \((2W-1)\). Then
Next, we examine the error committed in the boundary data. Let \(\Phi _{l}(\eta )=\Phi (X^{l}(-1,\eta ), Y^{l}(-1,\eta ))\) for \(-1\le \eta \le 1\). Let \(\tilde{\Phi }_{l}(\eta )\) be the polynomial of degree \((2W-1)\) in each variable separately which is the orthogonal projection of \(\Phi _{l}(\eta )\) in \(H^{4}(-1,1)\) into the space of polynomials of degree \((2W-1)\). Then we have
for \(t< 2W-1\).
Let \(\Psi _{l}(\eta )=\Psi (X^{l}(-1,\eta ), Y^{l}(-1,\eta ))\) for \(0\le \eta \le 1\). Let \(\tilde{\Psi }_{l}(\eta )\) be the polynomial of degree \((2W-1)\) in each variable separately which is the orthogonal projection of \(\Psi _{l}(\eta )\) in \(H^{4}(-1,1)\) into the space of polynomials of degree \((2W-1)\). Then we have
for \(t< 2W-1\).
Now consider the set of functions \(\{\phi _l(\xi ,\eta )\}\). We wish to show \(\mathcal {R}^{N,W}(\{\phi _l(\xi ,\eta )\})\) as defined in (3.3) is exponentially small in W. It remains then to estimate the terms
Let \(\mathscr {L}_{l}\) denote the differential operator with analytic coefficients such that
where
We can show as in [4] that there exists constants C and d such that
for all \((\xi ,\eta )\in S, |\alpha |\le m\). Similarly, we can estimate all other coefficients of \(\mathscr {L}_{l}\). Now,
Here, \((\mathcal {A}_{l})^{a}\) is the orthogonal projection of \(\mathcal {A}_{l}\) in \(H^4(S)\) into the space of polynomials of degree \(W-1\). The other coefficients of \((\mathscr {L}_{l})^{a}\) are obtained in a similar way. Therefore,
Same relation holds for all other coefficients. Now
Hence,
Finally, we show how to estimate the jump term (at inter-element boundary)
for any \(\gamma _{l,i}\subseteq \bar{\Omega }{\setminus }\partial \Omega \).
The other boundary terms can be handled in a similar fashion. Clearly, \(\gamma _{l,i}\) is a side which is common to \(\Omega _{m}\) and \(\Omega _{n}\) for some m and n. Let us assume that \(\gamma _{l,i}\) is the image of the side \(\xi =1\) of the square S under the mapping \(M_{m}\) and \(\xi =-1\) of the square S under the mapping \(M_{n}\). Then
Now,
Also,
Moreover,
Now \((\xi _{m})_{x},(\eta _{m})_{x},(\xi _{m})_{y}\) and \((\eta _{m})_{y}\) are analytic functions of \(\xi \) and \(\eta \) and satisfy
for \((\xi ,\eta )\in S\) and \(|\alpha |\le m\). Similar estimates hold for the functions \((\eta _{m})_{x}\), \((\xi _{m})_{y}\) and \((\eta _{m})_{y}\). So we can show
Combining all these estimates, we conclude that
Similarly, we can show that
and
Finally, we estimate the term \(||[(\phi )^{a}_{xxx}]||^{2}_{1/2,\gamma _{l,i}}\). We have
where
for \(j=m,n\). We have
and
Moreover,
and
Now, \((\xi _m)^{3}_{x}\), \((\xi _m)^{2}_{x} (\eta _m)_{x}\), \((\xi _m)_{x} (\eta _m)^{2}_{x}\), \((\eta _m)^{3}_{x}\), \((\xi _m)_{x}(\xi _m)_{xx}\), \((\eta _m)_{x}(\xi _m)_{xx}\), \((\xi _m)_{x}(\eta _m)_{xx}\), \((\eta _m)_{x}(\eta _m)_{xx}\), \((\xi _m)_{xxx}\) and \((\eta _m)_{xxx}\) are analytic functions of \(\xi \) and \(\eta \) on S and satisfy
for \((\xi ,\eta )\in S\) and \(|\alpha |\le m\). All other terms can be estimated similarly. So we can show that
Putting all these estimate together we conclude that
Similarly,
Hence, we can conclude that
Let \(\{\mathcal F_{z}\}\) minimizes \(\mathcal {R}^{N,W}(\{\mathcal F_{u}\})\) over all \(\{\mathcal F_{u}\}\in \mathcal {S}^{N,W}\). Then we have
Therefore, we conclude that
Hence, using stability theorem 3.1, we obtain
It is easy to show that
Combining the results (5.8) and (5.9), we obtain
which is the desired result. \(\square \)
Theorem 5.3
Let \(\{\mathcal F_{z}\}\) minimize \(\mathcal R^{N,W}(\{\mathcal F_u\})\) over all \(\{\mathcal F_{u}\}\in {\mathcal S}^{N,W}(\Omega )\). If u is analytic then there exist constants C and b (independent of N) such that
Here, \(\mathcal E^{N,W}\left( \{\mathcal F_{(z-U)}\}\right) \) is as defined in (3.3).
Proof
Combining Theorem 5.1 and 5.2, we obtain
for \(W>s\).
Applying Stirling’s formula
in Eq. (5.12) and choosing \(s=\gamma W\) with \(0<\gamma <1\), implies
Select \(\gamma \) so that \((d\gamma )<1\). Then there exists a constant \(b>0\) such that the following result holds:
\(\square \)
Remark 5.1
After having obtained the non-conforming spectral element solution we can make a correction to it so that the corrected solution is conforming and the error in the \(H^2\) norm is exponentially small in W. These corrections are similar to those for second order problems as explained in [33, 37].
Let us now estimate the error in terms of number of degrees of freedom. There are O(1) number of elements in \(\Omega \) and each element has \(O(W^{2})\) degrees of freedom.
Theorem 5.4
Let \(\{\mathcal F_{z}\}\) minimize \(\mathcal R^{N,W}(\{\mathcal F_u\})\) over all \(\{\mathcal F_{u}\}\in {\mathcal S}^{N,W}(\Omega )\). Then there exist constants C and b (independent of N and W) such that
Here, \(\mathcal U^{N,W}\left( \{\mathcal F_{(z-U)}\}\right) \) is as defined in (5) and \(W_{dof}=dim({\mathcal S}^{N,W}(\Omega ))=\#\) degrees of freedom.
6 Numerical Results
Let \(u_{approx.}\) be the spectral element solution obtained from the minimization problem and \(u_{exact}\) be the exact solution. Then the relative error is defined as
The numerical results presented in this Section have been obtained with a FORTRAN90 code. All our computations are carried out using a 372-node HPC cluster which is based on Intel Xeon Quadcore processors with a total of 2944 cores having a peak performance of 34.5 TF. In all examples of this section we have mapped each element onto a single processor. The library used for inter processor communication is Message Passing Interface (MPI). To show the exponential rate of convergence the relative error is plotted on a \(\log -\)scale.
We perform the PCGM until a stopping criterion on the relative norm of the residual vector for the normal equations becoming less than \(\epsilon \), a specified number, is satisfied. Since we would need to perform \(O\left( \frac{\sqrt{\kappa }}{2}|\log \left( \frac{2}{\epsilon }\right) |\right) \) iterations of the PCGM to satisfy the stopping criterion, we would need to perform \(O(W(\ln W)^2)\) iterations of the PCGM to obtain the approximate solution to an accuracy of \(O(e^{-bW})\). Here, \(\kappa \) denotes condition number of the preconditioner. Each iteration requires \(O(W^3)\) operation-time on a parallel computer with O(N) processors. Thus, the method requires \(O(W^{4}(\ln W)^2)\) operation-time on a parallel computer with O(N) processors to compute the solution to an accuracy of \(O(e^{-bW})\).
Let \(\Omega =S\) be the master square with boundary \(\partial \Omega \). In all our examples we have used three different meshes with uniform mesh size \(h=2.0,1.0\) and 0.5 in each direction (corresponds to \(N=1,4\) and 16 respectively).
Remark 6.1
In general singularities arise at the corners for 2D square domain. However, we choose our data selectively so that the solution is not singular at the corners.
Example 6.1
(Biharmonic problem with Dirichlet boundary conditions): Consider the biharmonic problem with Dirichlet BCs on \(\Omega =(-1,1)^2\),
We choose f, g and h such that the exact solution is
Results are presented in the Table 1 and the corresponding plots are shown in Fig. 3. A uniform mesh of size \(h=1\) is used which corresponds to the Mesh 2 (Fig. 2). In Fig. 3a, the relative error is plotted against W. Fig. 3c contains iterations vs. W and shows growth of iterations almost \(O(W(\log (W))^2)\) with increase in polynomial order. This is in agreement with our condition number estimates obtained in [23]. It is clear that the error decays exponentially and satisfies (5.1). Relative error as a function of iterations is shown in Fig. 3b. It validate the result which require \(O(W(\log W)^2)\) iterations to achieve the accuracy of \(O(e^{-bW})\) (Fig. 4).
Example 6.2
(Homogeneous boundary conditions): In order to demonstrate the efficiency of the method and to compare our scheme with those existing in the literature, we now consider the biharmonic problem:
and test the performance of our method. Consider the case when the exact solution is
In this case we have homogeneous boundary conditions. This example was reported in [9]. Table 2 summarizes the results. Comparing Tables 2 and 3, it can be observed that:
-
1.
Ben-Artzi et al. achieved \(10^{-10}\) accuracy with grid point \(n=256\) while our proposed method LSQ-SEM obtain \(10^{-13}\) accuracy with total grid point \(n=5\).
-
2.
The proposed method takes only \(1.3 \times 10^{-2}\) second to achieve \(3.2\times 10^{-15}\) accuracy.
-
3.
As expected we received zero error up to the machine accuracy, however, with much fewer degree of freedom as compared to 3, this is in agreement with the fact that our method is exact for polynomials.
-
4.
Plots among various parameters are plotted in Fig. 5. It is clear from the plots that the method give accuracy up to machine precision for polynomial solutions and is very effective in comparison to other methods.
-
5.
The graphs of exact solution and approximate solution for \(W=10\) are given in Fig. 6.
Example 6.3
(Non-homogeneous boundary conditions): We consider an additional example by choosing our exact solution as
This solves the equation
with non-zero boundary conditions where the forcing term \(f(x,y)=0\). Performance of the method on Mesh 2 (Fig. 2) is presented in Table 4.
Plots of relative error and iterations against polynomial orders and other parameters are depicted in Fig. 7. The relative error decays rapidly to \(\approx 10^{-7}\) when \(W=8\). The error profile is nearly a straight line for \(W=2,\ldots ,10\). This shows exponential convergence (Fig. 8).
Example 6.4
(Non-separable biharmonic problem): In Table 5 we report results of numerical simulations of our solver on Mesh 3 of Fig. 2 for a non-separable biharmonic problem in \(\Omega =(0,1)^2\) (see also [1, 9]) with exact solution
Comparing the Tables 5 and 6, we can easily see that
-
1.
Altas et al. [1] obtained \(10^{-10}\) accuracy for mesh size \(32\times 32\) while LSQ-SEM achieve \(10^{-11}\) accuracy with mesh 3 for \(W=8\).
-
2.
The proposed method takes only 0.4387 second to achieve \(10^{-11}\) accuracy.
-
3.
Plots for various parameters are presented in Fig. 9. Percentage relative error against polynomial degrees and iterations is plotted in Figs. 9a, b respectively on a \(\log \)-scale.
-
4.
The graphs of exact solution and approximate solution for \(W=10\) are given in Fig. 10.
-
5.
It is evident from the graphs the approximate solutions converge exponentially to the exact solution.
Remark 6.2
It is clear from these examples that the method is efficient in dealing problems with homogeneous as well as non-homogeneous boundary conditions.
Example 6.5
(Periodic boundary conditions): In our next example we take \(\Omega =(-1,1)^2\) and solve (2.1). We choose f, g and h such that the exact solution is
This example was considered in [1, 9, 12]. The source term is \(\Delta ^2 w(x,y)\) and the boundary conditions are zeros on the four sides of the square. Table 7 depicts the numerical results.
Here, we are comparing our result in Table 7 from Tables 8 and 9. The observations are as follows:
-
1.
Shen [34] and Bialecki et al. [11] achieved the accuracy \(10^{-12}\) for \(W=32\) while LSQ-SEM obtain \(10^{-13}\) accuracy for \(W=12\).
-
2.
In Fig. 11a, relative error is plotted against polynomial order W on a \(\log -\)scale. The curve is almost a straight line and it confirms the theoretical estimates obtained.
-
3.
In Fig. 11b, the error is drawn as a function of iterations on a \(\log \) scale. It satisfy the criteria to achieve the \(O(e^{-b W})\) accuracy with \(O(W(\log (W))^2)\) iteration.
-
4.
In Fig. 11c, iteration is plotted against polynomial order W on a \(\log -\)scale. The growth of the iterations is almost \(O(W(\log (W))^2)\).
-
5.
The graphs of exact solution and approximate solution for \(W=10\) are given in Fig. 12.
7 Conclusions
In this article we have presented a fully non-conforming least-squares spectral element method for fourth order elliptic problems on smooth domains. It is shown that the condition number of the preconditioned system is \(O((\ln W)^{4})\). It is also clear from giving test problems that the error in the computed solution decays exponentially in W, the number of elements in the mesh. The computational complexity of the method is \(O(W^{4}(\ln W)^2)\) operations on a parallel computer with O(N) processors.
Numerical results for a number of test problems on rectangular domains with analytic solutions confirm the estimates obtained for the error and computational complexity. The algorithm is quite simple and easy to implement on parallel computers since the bottlenecks of our algorithm are matrix-vector multiplications. The method works for variable coefficient problems too and can be extended to three dimensional problems with less efforts. We plan to develop numerical schemes for fourth order problems with various types of singularities on polygonal and polyhedral domains in future work.
References
Altas, I., Dym, J., Gupta, M.M., Manohar, R.: Mutigrid solution of automatically generated high-order discretizations for the biharmonic equation. SIAM J. Sci. Comput. 19, 1575–1585 (1998)
Babuška, I., Guo, B.: Approximation properties of the \(h-p\) version of the finite element method. Comput. Methods Appl. Mech. Eng. 133, 319–346 (1996)
Babuška, I., Guo, B.: Regularity of the solutions of elliptic problems with piecewise analytic data, part I: boundary value problems for linear elliptic equation of second order. SIAM J. Math. Anal. 19(1), 172–203 (1988)
Babuška, I., Guo, B.: The \(h-p\) version of the finite element method on domains with curved boundaries. SIAM J. Numer. Anal. 25, 837–861 (1988)
Babuška, I., Guo, B.: The \(h\)-\(p\) version of the finite element method, part I: the basic approximation results. Comput. Mech. 1, 21–41 (1986)
Babuška, I., Guo, B.: The \(h-p\) version of the finite element method, part II: general results and applications. Comput. Mech. 1, 203–220 (1986)
Bernardi, C., Coppoletta, G., Maday, Y.: Some spectral approximations of two-dimensional fourth-order problems. Math. Comput. 59(199), 63–76 (1992)
Bernardi, C., Maday, Y.: Spectral methods. Handb. Numer. Anal. 5, 209–485 (1997)
Ben-Artzi, M., Croisille, J.P., Fishelov, D.: A fast direct solver for the biharmonic problem in a rectangular grid. SIAM J. Sci. Comput. 31(1), 303–333 (2008)
Bialecki, B., Karageorghis, A.: A Legendre spectral Galerkin method for the biharmonic Dirichlet problem. SIAM J. Sci. Comput. 22(5), 1549–1569 (2001)
Bialecki, B.: A Legendre spectral collocation method for the biharmonic Dirichlet problem. ESAIM: Math. Model. Numer. Anal. 34(3), 637–662 (2000)
Bialecki, B.: A fast solver for the orthogonal spline collocation solution of the biharmonic Dirichlet problem on rectangles. J. Comput. Phys. 191, 601–621 (2003)
Bjørstad, P.: Fast numerical solution of the biharmonic Dirichlet problem on rectangles. SIAM J. Numer. Anal. 20(1), 59–71 (1983)
Buzzbee, B.L., Dorr, F.W.: The direct solution of the biharmonic equation on rectangular regions and the Poisson equation on irregular regions. SIAM J. Numer. Anal. 11(4), 753–763 (1974)
Canuto, C., Hussaini, M.Y., Quarteroni, A., Zang, T.A.: Spectral Methods in Fluid Dynamics. Springer, Berlin (1988)
Ciarlet, P.G.: The finite element method for elliptic problems, classics in applied mathematics. SIAM. 40 (2002). doi:10.1137/1.9780898719208
Dutt, P., Biswas, P., Raju, G.N.: Preconditioners for spectral element methods for elliptic and parabolic problems. J. Comput. Appl. Math. 215(1), 152–166 (2008)
Dutt, P.K., Kumar, N.K., Upadhyay, C.S.: Non-conforming \(h-p\) spectral element methods for elliptic problems. Proc. Indian Acad. Sci. (Math. Sci.) 117(1), 109–145 (2007)
Dutt, P., Tomar, S.: Stability estimates for \(h-p\) spectral element methods for general elliptic problems on curvilinear domains. Proc. Indian Acad. Sci. (Math. Sci.) 113(4), 395–429 (2003)
Dutt, P., Tomar, S., Kumar, B.V.R.: Stability estimates for \(h-p\) spectral element methods for elliptic problems. Proc. Indian Acad. Sci. (Math Sci.) 112(4), 601–639 (2002)
Gerritsma, M., Maerschalck, D.B.: Least-squares spectral element methods in computational fluid dynamics. Advanced Computational Methods in Science and Engineering Lecture Notes in Computational Science and Engineering, vol. 71, pp. 179–227 (2010)
Grisvard, P.: Elliptic problems in nonsmooth domains, classics in applied mathematics. SIAM, 69 (2011). doi:10.1137/1.9781611972030
Husain, A., Khan, A.: Least-squares spectral element preconditioners for fourth order elliptic problems. arXiv:1608.08416
Karniadakis, G., Sherwin, J.: Spectral/h-p Element Methods for CFD. Oxford University Press, Oxford (1999)
Khan, A., Upadhyay, C.S.: Exponentially accurate nonconforming least-squares spectral element method for elliptic problems on unbounded domain. Comput. Methods Appl. Mech. Eng. 305, 607–633 (2016)
Kumar, N.K., Nagaraju, G.: Least-squares \(hp\)/spectral element method for elliptic problems. Appl. Numer. Math. 60(1–2), 38–54 (2010)
Kumar, N.K., Dutt, P.K., Upadhyay, C.S.: Nonconforming spectral/\(h-p\) element methods for elliptic systems. J. Numer. Math. 17(2), 119–142 (2009)
Mandel, J.: Iterative methods for \(p-\)version finite elements: preconditioning thin solids. Comput. Methods Appl. Mech. Eng. 133, 247–257 (1996)
Meleshko, V.V.: Selected topics in the history of the two-dimensional biharmonic problem. Appl. Mech. Rev. 56(1), 3385 (2003)
Pathria, D., Karniadakis, G.E.: Spectral element methods for elliptic problems in non-smooth domains. J. Comput. Phys. 122, 83–95 (1995)
Pontaza, J.P., Reddy, J.N.: Spectral/hp least-squares finite element formulation for the incompressible Navier-Stokes equation. J. Comput. Phys. 190(2), 523–549 (2003)
Proot, M.M.J., Gerritsma, M.I.: A least-squares spectral element formulation for Stokes problem. J. Comput. Phys. 17(1–4), 285–296 (2002)
Schwab, C.: \(p\) and \(h-p\) Finite Element Methods. Clarendon Press, Oxford (1998)
Shen, J.: Efficient spectral-Galerkin method I. Direct solvers for the second and fourth order equations using Legendre polynomials. SIAM J. Sci. Comput. 15(6), 1489–1505 (1994)
Shen, J., Tang, T.: Spectral and High-order Methods with Applications. Science Press, Beijing (2006)
Shen, J., Tang, T., Wang, L.L.: Spectral Methods: Algorithms, Analysis and Applications. Springer, Berlin (2011)
Tomar, S.K.: \(h-p\) Spectral element methods for elliptic problems over non-smooth domains using parallel computers. Computing 78, 117–143 (2006)
Tomar, S.K., Dutt, P., Kumar, B.V.R.: An efficient and exponentially accurate parallel \(h-p\) spectral element method for elliptic problems on polygonal domains—the Dirichilet case. Lecture Notes in Computer Science 2552, High Performance Computing. Springer, Berlin (2002)
Yu, X.H., Guo, B.Y.: Spectral element method for mixed inhomogeneous boundary value problems of fourth order. J. Sci. Comput. 61(3), 673–701 (2014)
Yu, X.H., Guo, B.Y.: Spectral method for fourth-order problems on quadrilaterals. J. Sci. Comput. 66(2), 1–27 (2015)
Zhang, S., Xu, J.: Optimal solvers for fourth-order PDEs discretized on unstructured grids. SIAM J. Numer. Anal. 52(1), 282–307 (2014)
Zhao, J.: Multigrid methods for fourth order problems. Ph.D. Thesis, University of South Carolina. www.math.sc.edu/~fem/zhaodiss.pdf (2004)
Zhu, Z.: The least-squares spectral element method solution of the gas-liquid multi-fluid model coupled with the population balance equation. Ph.D. Thesis, NTNU Norway. www.diva-portal.org/smash/get/diva2:297012/FULLTEXT03.pdf (2009)
Žitňan, P.: Discrete weighted least-squares method for the Poisson and biharmonic problems on domains with smooth boundary. Appl. Math. Comput. 217(22), 8973–8982 (2011)
Author information
Authors and Affiliations
Corresponding author
Additional information
The first author is thankful to the LNM Institute of Information Technology (LNMIIT), Jaipur for supporting his visits to carry out this work and also thankful to IIT Kanpur for providing the parallel computers facilities to compute the numerical results. Research is also supported by Mathematics Center Heidelberg (MATCH), Ruprecht-Karls-Universität Heidelberg, 69120 Heidelberg, Germany.
This work was carried out during the second author’s stay at the LNM Institute of Information Technology (LNMIIT), Jaipur as assistant professor.
Rights and permissions
About this article
Cite this article
Khan, A., Husain, A. Exponentially Accurate Spectral Element Method for Fourth Order Elliptic Problems. J Sci Comput 71, 303–328 (2017). https://doi.org/10.1007/s10915-016-0300-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10915-016-0300-z