The Local Discontinuous Galerkin Method for the Fourth-Order Euler–Bernoulli Partial Differential Equation in One Space Dimension. Part I: Superconvergence Error Analysis

In this paper we develop and analyze a new superconvergent local discontinuous Galerkin (LDG) method for approximating solutions to the fourth-order Euler–Bernoulli beam equation in one space dimension. We prove the $L^2$ stability of the scheme and several optimal $L^2$ error estimates for the solution and for the three auxiliary variables that approximate derivatives of different orders. Our numerical experiments demonstrate optimal rates of convergence. We also prove superconvergence results towards particular projections of the exact solutions. More precisely, we prove that the LDG solution and its spatial derivatives (up to third order) are $\mathcal O (h^{k+3/2})$ super close to particular projections of the exact solutions for $k$ th-degree polynomial spaces while computational results show higher $\mathcal O (h^{k+2})$ convergence rate. Our proofs are valid for arbitrary regular meshes and for $P^k$ polynomials with $k\ge 1$ , and for periodic, Dirichlet, and mixed boundary conditions. These superconvergence results will be used to construct asymptotically exact a posteriori error estimates by solving a local steady problem on each element. This will be reported in Part II of this work, where we will prove that the a posteriori LDG error estimates for the solution and its derivatives converge to the true errors in the $L^2$ -norm under mesh refinement.     

A Posteriori Error Estimates for Weak Galerkin Finite Element Methods for Second Order Elliptic Problems

A residual type a posteriori error estimator is presented and analyzed for Weak Galerkin finite element methods for second order elliptic problems. The error estimator is proved to be efficient and reliable through two estimates, one from below and the other from above, in terms of an $H^1$ -equivalent norm for the exact error. Two numerical experiments are conducted to demonstrate the effectiveness of adaptive mesh refinement guided by this estimator.     

Error Estimates of the Finite Element Method for Interior Transmission Problems

The interior transmission problem (ITP) plays an important role in the investigation of the inverse scattering problem. In this paper we propose the finite element method for solving the ITP. Based on the $\mathbb T $ -coercivity, we derive both priori error estimate and a posteriori error estimate of the finite element approximation. Numerical experiments are also included to illustrate the accuracy of the finite element method.     

Constraint-Free Adaptive FEMs on Quadrilateral Nonconforming Meshes

Finite element methods (FEMs) on nonconforming meshes have been much studied in the literature. In all earlier works on such methods , some constraints must be imposed on the degrees of freedom on the edge/face with hanging nodes in order to maintain continuity, which make the numerical implementation more complicated. In this paper, we present two FEMs on quadrilateral nonconforming meshes which are constraint-free. Furthermore, we establish the corresponding residual-based a posteriori error reliability and efficiency estimation for general quadrilateral meshes. We also present extensive numerical testing results to systematically compare the performance among three adaptive quadrilateral FEMs: the constraint-free adaptive $\mathbb Q _1$ FEM on quadrilateral nonconforming meshes with hanging nodes developed herein, the adaptive $\mathbb Q _1$ FEM based on quadrilateral red-green refinement without any hanging node recently proposed in Zhao et al. (SIAM J Sci Comput 3(4):2099–2120, 2010), and the classical adaptive $\mathbb Q _1$ FEM on quadrilateral nonconforming meshes with constraints on hanging nodes. Some extensions are also included in this paper.     

Comparison Between Reduced Basis and Stochastic Collocation Methods for Elliptic Problems

The stochastic collocation method (Babu?ka et al. in SIAM J Numer Anal 45(3):1005–1034, 2007; Nobile et al. in SIAM J Numer Anal 46(5):2411–2442, 2008a; SIAM J Numer Anal 46(5):2309–2345, 2008b; Xiu and Hesthaven in SIAM J Sci Comput 27(3):1118–1139, 2005) has recently been applied to stochastic problems that can be transformed into parametric systems. Meanwhile, the reduced basis method (Maday et al. in Comptes Rendus Mathematique 335(3):289–294, 2002; Patera and Rozza in Reduced basis approximation and a posteriori error estimation for parametrized partial differential equations Version 1.0. Copyright MIT, http://augustine.mit.edu, 2007; Rozza et al. in Arch Comput Methods Eng 15(3):229–275, 2008), primarily developed for solving parametric systems, has been recently used to deal with stochastic problems (Boyaval et al. in Comput Methods Appl Mech Eng 198(41–44):3187–3206, 2009; Arch Comput Methods Eng 17:435–454, 2010). In this work, we aim at comparing the performance of the two methods when applied to the solution of linear stochastic elliptic problems. Two important comparison criteria are considered: (1), convergence results of the approximation error; (2), computational costs for both offline construction and online evaluation. Numerical experiments are performed for problems from low dimensions $O(1)$ to moderate dimensions $O(10)$ and to high dimensions $O(100)$ . The main result stemming from our comparison is that the reduced basis method converges better in theory and faster in practice than the stochastic collocation method for smooth problems, and is more suitable for large scale and high dimensional stochastic problems when considering computational costs.     

A New Error Analysis of Crank–Nicolson Galerkin FEMs for a Generalized Nonlinear Schrödinger Equation

In this paper, we study linearized Crank–Nicolson Galerkin FEMs for a generalized nonlinear Schrödinger equation. We present the optimal \(L^2\) error estimate without any time-step restrictions, while previous works always require certain conditions on time stepsize. A key to our analysis is an error splitting, in terms of the corresponding time-discrete system, with which the error is split into two parts, the temporal error and the spatial error. Since the spatial error is \(\tau \) -independent, the numerical solution can be bounded in \(L^{\infty }\) -norm by an inverse inequality unconditionally. Then, the optimal \(L^2\) error estimate can be obtained by a routine method. To confirm our theoretical analysis, numerical results in both two and three dimensional spaces are presented.     

A C^0-Weak Galerkin Finite Element Method for the Biharmonic Equation

A $C^0$ -weak Galerkin (WG) method is introduced and analyzed in this article for solving the biharmonic equation in 2D and 3D. A discrete weak Laplacian is defined for $C^0$ functions, which is then used to design the weak Galerkin finite element scheme. This WG finite element formulation is symmetric, positive definite and parameter free. Optimal order error estimates are established for the weak Galerkin finite element solution in both a discrete $H^2$ norm and the standard $H^1$ and $L^2$ norms with appropriate regularity assumptions. Numerical results are presented to confirm the theory. As a technical tool, a refined Scott-Zhang interpolation operator is constructed to assist the corresponding error estimates. This refined interpolation preserves the volume mass of order $(k+1-d)$ and the surface mass of order $(k+2-d)$ for the $P_{k+2}$ finite element functions in $d$ -dimensional space.     

The Local Discontinuous Galerkin Method for the Fourth-Order Euler–Bernoulli Partial Differential Equation in One Space Dimension. Part II: A Posteriori Error Estimation

In this paper new a posteriori error estimates for the local discontinuous Galerkin (LDG) method for one-dimensional fourth-order Euler–Bernoulli partial differential equation are presented and analyzed. These error estimates are computationally simple and are obtained by solving a local steady problem with no boundary condition on each element. We use the optimal error estimates and the superconvergence results proved in Part I to show that the significant parts of the discretization errors for the LDG solution and its spatial derivatives (up to third order) are proportional to \((k+1)\) -degree Radau polynomials, when polynomials of total degree not exceeding \(k\) are used. These results allow us to prove that the \(k\) -degree LDG solution and its derivatives are \(\mathcal O (h^{k+3/2})\) superconvergent at the roots of \((k+1)\) -degree Radau polynomials. We use these results to construct asymptotically exact a posteriori error estimates. We further apply the results proved in Part I to prove that, for smooth solutions, these a posteriori LDG error estimates for the solution and its spatial derivatives at a fixed time \(t\) converge to the true errors at \(\mathcal O (h^{k+5/4})\) rate. We also prove that the global effectivity indices, for the solution and its derivatives up to third order, in the \(L^2\) -norm converge to unity at \(\mathcal O (h^{1/2})\) rate. Our proofs are valid for arbitrary regular meshes and for \(P^k\) polynomials with \(k\ge 1\) , and for periodic and other classical mixed boundary conditions. Our computational results indicate that the observed numerical convergence rates are higher than the theoretical rates. Finally, we present a local adaptive procedure that makes use of our local a posteriori error estimate.     

Optimal quadrature formulas in the sense of Sard in W_2^{(m,m-1)} space

This paper studies the problem of construction of optimal quadrature formulas in the sense of Sard in the $W_2^{(m,m-1)}(0,1)$ space. Using the Sobolev’s method we obtain new optimal quadrature formulas of such type for $N+1\ge m$ , where $N+1$ is the number of the nodes. Moreover, explicit formulas of the optimal coefficients are obtained. We investigate the order of convergence of the optimal formula for $m=1$ and prove an asymptotic optimality of such a formula in the Sobolev space $L_2^{(1)}(0,1)$ . It turns out that the error of the optimal quadrature formula in $W_2^{(1,0)}(0,1)$ is less than the error of the optimal quadrature formula given in the $L_2^{(1)}(0,1)$ space. The obtained optimal quadrature formula in the $W_2^{(m,m-1)}(0,1)$ space is exact for $\exp (-x)$ and $P_{m-2}(x)$ , where $P_{m-2}(x)$ is a polynomial of degree $m-2$ . Furthermore, some numerical results, which confirm the obtained theoretical results of this work, are given.     

Superconvergence of Any Order Finite Volume Schemes for 1D General Elliptic Equations

We present and analyze a finite volume scheme of arbitrary order for elliptic equations in the one-dimensional setting. In this scheme, the control volumes are constructed by using the Gauss points in subintervals of the underlying mesh. We provide a unified proof for the inf-sup condition, and show that our finite volume scheme has optimal convergence rate under the energy and $L^2$ norms of the approximate error. Furthermore, we prove that the derivative error is superconvergent at all Gauss points and in some special cases, the convergence rate can reach $h^{r+2}$ and even $h^{2r}$ , comparing with $h^{r+1}$ rate of the counterpart finite element method. Here $r$ is the polynomial degree of the trial space. All theoretical results are justified by numerical tests.     

Plaintext awareness in identity-based key encapsulation

The notion of plaintext awareness ( ${\mathsf{PA}}$ ) has many applications in public key cryptography: it offers unique, stand-alone security guarantees for public key encryption schemes, has been used as a sufficient condition for proving indistinguishability against adaptive chosen-ciphertext attacks ( ${\mathsf{IND}\hbox {-}{\mathsf{CCA}}}$ ), and can be used to construct privacy-preserving protocols such as deniable authentication. Unlike many other security notions, plaintext awareness is very fragile when it comes to differences between the random oracle and standard models; for example, many implications involving ${\mathsf{PA}}$ in the random oracle model are not valid in the standard model and vice versa. Similarly, strategies for proving ${\mathsf{PA}}$ of schemes in one model cannot be adapted to the other model. Existing research addresses ${\mathsf{PA}}$ in detail only in the public key setting. This paper gives the first formal exploration of plaintext awareness in the identity-based setting and, as initial work, proceeds in the random oracle model. The focus is laid mainly on identity-based key encapsulation mechanisms (IB-KEMs), for which the paper presents the first definitions of plaintext awareness, highlights the role of ${\mathsf{PA}}$ in proof strategies of ${\mathsf{IND}\hbox {-}{\mathsf{CCA}}}$ security, and explores relationships between ${\mathsf{PA}}$ and other security properties. On the practical side, our work offers the first, highly efficient, general approach for building IB-KEMs that are simultaneously plaintext-aware and ${\mathsf{IND}\hbox {-}{\mathsf{CCA}}}$ -secure. Our construction is inspired by the Fujisaki-Okamoto (FO) transform, but demands weaker and more natural properties of its building blocks. This result comes from a new look at the notion of $\gamma $ -uniformity that was inherent in the original FO transform. We show that for IB-KEMs (and PK-KEMs), this assumption can be replaced with a weaker computational notion, which is in fact implied by one-wayness. Finally, we give the first concrete IB-KEM scheme that is ${\mathsf{PA}}$ and ${\mathsf{IND}\hbox {-}{\mathsf{CCA}}}$ -secure by applying our construction to a popular IB-KEM and optimizing it for better performance.     

General DG-Methods for Highly Indefinite Helmholtz Problems

We develop a stability and convergence theory for a Discontinuous Galerkin formulation (DG) of a highly indefinite Helmholtz problem in $\mathbb R ^{d}$ , $d\in \{1,2,3\}$ . The theory covers conforming as well as non-conforming generalized finite element methods. In contrast to conventional Galerkin methods where a minimal resolution condition is necessary to guarantee the unique solvability, it is proved that the DG-method admits a unique solution under much weaker conditions. As an application we present the error analysis for the $hp$ -version of the finite element method explicitly in terms of the mesh width $h$ , polynomial degree $p$ and wavenumber $k$ . It is shown that the optimal convergence order estimate is obtained under the conditions that $kh/\sqrt{p}$ is sufficiently small and the polynomial degree $p$ is at least $O(\log k)$ . On regular meshes, the first condition is improved to the requirement that $kh/p$ be sufficiently small.     

The Compact Discontinuous Galerkin Method for Nearly Incompressible Linear Elasticity

A compact discontinuous Galerkin method (CDG) is devised for nearly incompressible linear elasticity, through replacing the global lifting operator for determining the numerical trace of stress tensor in a local discontinuous Galerkin method (cf. Chen et al., Math Probl Eng 20, 2010) by the local lifting operator and removing some jumping terms. It possesses the compact stencil, that means the degrees of freedom in one element are only connected to those in the immediate neighboring elements. Optimal error estimates in broken energy norm, $H^1$ -norm and $L^2$ -norm are derived for the method, which are uniform with respect to the Lamé constant $\lambda .$ Furthermore, we obtain a post-processed $H(\text{ div})$ -conforming displacement by projecting the displacement and corresponding trace of the CDG method into the Raviart–Thomas element space, and obtain optimal error estimates of this numerical solution in $H(\text{ div})$ -seminorm and $L^2$ -norm, which are uniform with respect to $\lambda .$ A series of numerical results are offered to illustrate the numerical performance of our method.     

The Nonconvergence of h-Refinement in Prolate Elements

Prolate elements are a “plug-compatible” modification of spectral elements in which Legendre polynomials are replaced by prolate spheroidal wave functions of order zero. Prolate functions contain a“bandwidth parameter” $c \ge 0 $ c ≥ 0 whose value is crucial to numerical performance; the prolate functions reduce to Legendre polynomials for $c\,=\,0$ c = 0 . We show that the optimal bandwidth parameter $c$ c not only depends on the number of prolate modes per element $N$ N , but also on the element widths $h$ h . We prove that prolate elements lack $h$ h -convergence for fixed $c$ c in the sense that the error does not go to zero as the element size $h$ h is made smaller and smaller. Furthermore, the theoretical predictions that Chebyshev and Legendre polynomials require $\pi $ π degrees of freedom per wavelength to resolve sinusoidal functions while prolate series need only 2 degrees of freedom per wavelength are asymptotic limits as $N \rightarrow \infty $ N → ∞ ; we investigate the rather different behavior when $N \sim O(4-10)$ N ～ O ( 4 ? 10 ) as appropriate for spectral elements and prolate elements. On the other hand, our investigations show that there are certain combinations of $N,\,h$ N , h and $c>0$ c > 0 where a prolate basis clearly outperforms the Legendre polynomial approximation.     

Long-Term Stability of Multi-Value Methods for Ordinary Differential Equations

Much effort is put into the construction of general linear methods with the aim of achieving an excellent long-time behavior for the integration of Hamiltonian systems. In this article, a backward error analysis is presented, which permits to get sharp estimates for the parasitic solution components and for the error in the Hamiltonian. For carefully constructed methods (symmetric and zero growth parameters) the error in the parasitic components typically grows like \(h^{p+4}\exp (h^2Lt)\) , where \(p\) is the order of the method, and \(L\) depends on the problem and on the coefficients of the method. This is confirmed by numerical experiments.     

A UTP semantics for Circus

Circus specifications define both data and behavioural aspects of systems using a combination of Z and CSP constructs. Previously, a denotational semantics has been given to Circus; however, a shallow embedding of Circus in Z, in which the mapping from Circus constructs to their semantic representation as a Z specification, with yet another language being used as a meta-language, was not useful for proving properties like the refinement laws that justify the distinguishing development technique associated with Circus. This work presents a final reference for the Circus denotational semantics based on Hoare and He’s Unifying Theories of Programming (UTP); as such, it allows the proof of meta-theorems about Circus including the refinement laws in which we are interested. Its correspondence with the CSP semantics is illustrated with some examples. We also discuss the library of lemmas and theorems used in the proofs of the refinement laws. Finally, we give an account of the mechanisation of the Circus semantics and of the mechanical proofs of the refinement laws.     

Solving Convection-Diffusion Problems on Curved Domains by Extensions from Subdomains

We present a technique for numerically solving convection-diffusion problems in domains $\varOmega $ with curved boundary. The technique consists in approximating the domain $\varOmega $ by polyhedral subdomains $\mathsf{{D}}_h$ where a finite element method is used to solve for the approximate solution. The approximation is then suitably extended to the remaining part of the domain $\varOmega $ . This approach allows for the use of only polyhedral elements; there is no need of fitting the boundary in order to obtain an accurate approximation of the solution. To achieve this, the boundary condition on the border of $\varOmega $ is transferred to the border of $\mathsf{D }_h$ by using simple line integrals. We apply this technique to the hybridizable discontinuous Galerkin method and provide extensive numerical experiments showing that, whenever the distance of $\mathsf{{D}}_h$ to $\partial \varOmega $ is of order of the meshsize $h$ , the convergence properties of the resulting method are the same as those for the case in which $\varOmega =\mathsf{{D}}_h$ . We also show numerical evidence indicating that the ratio of the $L^2(\varOmega )$ norm of the error in the scalar variable computed with $d>0$ to that of that computed with $d=0$ remains constant (and fairly close to one), whenever the distance $d$ is proportional to $\min \{h,Pe^{-1}\}/(k+1)^2$ , where $Pe$ is the so-called Péclet number.     

Combinatorial algorithms for distributed graph coloring

Numerous problems in Theoretical Computer Science can be solved very efficiently using powerful algebraic constructions. Computing shortest paths, constructing expanders, and proving the PCP Theorem, are just few examples of this phenomenon. The quest for combinatorial algorithms that do not use heavy algebraic machinery, but are roughly as efficient, has become a central field of study in this area. Combinatorial algorithms are often simpler than their algebraic counterparts. Moreover, in many cases, combinatorial algorithms and proofs provide additional understanding of studied problems. In this paper we initiate the study of combinatorial algorithms for Distributed Graph Coloring problems. In a distributed setting a communication network is modeled by a graph $G=(V,E)$ of maximum degree $\varDelta $ . The vertices of $G$ host the processors, and communication is performed over the edges of $G$ . The goal of distributed vertex coloring is to color $V$ with $(\varDelta + 1)$ colors such that any two neighbors are colored with distinct colors. Currently, efficient algorithms for vertex coloring that require $O(\varDelta + \log ^* n)$ time are based on the algebraic algorithm of Linial (SIAM J Comput 21(1):193–201, 1992) that employs set-systems. The best currently-known combinatorial set-system free algorithm, due to Goldberg et al. (SIAM J Discret Math 1(4):434–446, 1988), requires $O(\varDelta ^2+\log ^*n)$ time. We significantly improve over this by devising a combinatorial $(\varDelta + 1)$ -coloring algorithm that runs in $O(\varDelta + \log ^* n)$ time. This exactly matches the running time of the best-known algebraic algorithm. In addition, we devise a tradeoff for computing $O(\varDelta \cdot t)$ -coloring in $O(\varDelta /t + \log ^* n)$ time, for almost the entire range $1 < t < \varDelta $ . We also compute a Maximal Independent Set in $O(\varDelta + \log ^* n)$ time on general graphs, and in $O(\log n/ \log \log n)$ time on graphs of bounded arboricity. Prior to our work, these results could be only achieved using algebraic techniques. We believe that our algorithms are more suitable for real-life networks with limited resources, such as sensor networks.