Optimal Error Estimates of Two Mixed Finite Element Methods for Parabolic Integro-Differential Equations with Nonsmooth Initial Data

In the first part of this article, a new mixed method is proposed and analyzed for parabolic integro-differential equations (PIDE) with nonsmooth initial data. Compared to the standard mixed method for PIDE, the present method does not bank on a reformulation using a resolvent operator. Based on energy arguments combined with a repeated use of an integral operator and without using parabolic type duality technique, optimal $L^2$ L 2 -error estimates are derived for semidiscrete approximations, when the initial condition is in $L^2$ L 2 . Due to the presence of the integral term, it is, further, observed that a negative norm estimate plays a crucial role in our error analysis. Moreover, the proposed analysis follows the spirit of the proof techniques used in deriving optimal error estimates for finite element approximations to PIDE with smooth data and therefore, it unifies both the theories, i.e., one for smooth data and other for nonsmooth data. Finally, we extend the proposed analysis to the standard mixed method for PIDE with rough initial data and provide an optimal error estimate in $L^2,$ L 2 , which improves upon the results available in the literature.     

Optimal Error Analysis of Galerkin FEMs for Nonlinear Joule Heating Equations

We study in this paper two linearized backward Euler schemes with Galerkin finite element approximations for the time-dependent nonlinear Joule heating equations. By introducing a time-discrete (elliptic) system as proposed in Li and Sun (Int J Numer Anal Model 10:622–633, 2013; SIAM J Numer Anal (to appear)), we split the error function as the temporal error function plus the spatial error function, and then we present unconditionally optimal error estimates of $r$ th order Galerkin FEMs ( $1 \le r \le 3$ ). Numerical results in two and three dimensional spaces are provided to confirm our theoretical analysis and show the unconditional stability (convergence) of the schemes.     

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.     

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.     

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.     

HDG Methods for Naghdi Arches

In this paper, we introduce and analyze a class of hybridizable discontinuous Galerkin methods for Naghdi arches. The main feature of these methods is that they can be implemented in an efficient way through a hybridization procedure which reduces the globally coupled unknowns to approximations to the transverse and tangential displacement and bending moment at the element boundaries. The error analysis of the methods is based on the use of a projection especially designed to fit the structure of the numerical traces of the method. This property allows to prove in a very concise manner that the projection of the errors is bounded in terms of the distance between the exact solution and its projection. The study of the influence of the stabilization function on the approximation is then reduced to the study of how they affect the approximation properties of the projection in a single element. Consequently, we prove that when polynomials of degree $k$ are used, the methods converge with the optimal order of $k+1$ for all the unknowns and that they are free from shear and membrane locking. Finally, we show that all the numerical traces converge with order $2k+1$ . Numerical experiments validating these results are shown.     

A Spectral Element Framework for Option Pricing Under General Exponential Lévy Processes

We derive a spectral element framework to compute the price of vanilla derivatives when the dynamic of the underlying follows a general exponential Lévy process. The representation of the solution with Legendre polynomials allows one to naturally approximate the convolution integral with high order quadratures. The method is spectrally accurate in space for the solution and the greeks, and third order accurate in time. The spectral element framework does not require an approximation of the Lévy measure nor the lower truncation of the convolution integral as commonly seen in finite difference approximations. We show that the spectral element method is ten times faster than Fast Fourier Transform methods for the same accuracy at strike, and two hundred times faster if one reconstructs the greeks from the solution obtained by FFT. We use the SEM approximation to derive the $\Delta $ Δ and $\Gamma $ Γ in a variance gamma model, for which there is no closed form solution.     

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.     

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.     

Resource augmentation for uniprocessor and multiprocessor partitioned scheduling of sporadic real-time tasks

Although the earliest-deadline-first (EDF) policy is known to be optimal for preemptive real-time task scheduling in uniprocessor systems, the schedulability analysis problem has recently been shown to be $\mathit{co}\mathcal{NP}$ -hard. Therefore, approximation algorithms, and in particular, approximations based on resource augmentation have attracted a lot of attention for both uniprocessor and multiprocessor systems. Resource augmentation based approximations assume a certain speedup of the processor(s). Using the notion of approximate demand bound function (dbf), in this paper we show that for uniprocessor systems the resource augmentation factor is at most $\frac{2e-1}{e} \approx1.6322$ , where e is the Euler number. We approximate the dbf using a linear approximation when the analysis interval length of interest is larger than the relative deadline of the task. For identical multiprocessor systems with M processors and constrained-deadline task sets, we show that the deadline-monotonic partitioning (that has been proposed by Baruah and Fisher) with the approximate dbf leads to an approximation factor of $\frac{3e-1}{e}-\frac{1}{M} \approx 2.6322-\frac{1}{M}$ with respect to resource augmentation. We also show that the corresponding factor is $3-\frac{1}{M}$ for arbitrary-deadline task sets. The best known results so far were $3-\frac{1}{M}$ for constrained-deadline tasks and $4-\frac {2}{M}$ for arbitrary-deadline ones. Our tighter analysis exploits the structure of the approximate dbf directly and uses the processor utilization violations (which were ignored in all previous analysis) for analyzing resource augmentation factors. We also provide concrete input instances to show that the lower bound on the resource augmentation factor for uniprocessor systems—using the above approximate dbf—is 1.5, and the corresponding bound is 2.5 for identical multiprocessor systems with an arbitrary order of fitting and a large number of processors. Further, we also provide a polynomial-time approximation scheme (PTAS) to derive near-optimal solutions under the assumption that the ratio of the maximum relative deadline to the minimum relative deadline of tasks is a constant, which is a more relaxed assumption compared to the assumptions required for deriving such a PTAS in the past.     

Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits

The class of polynomials computable by polynomial size log-depth arithmetic circuits (VNC ¹) is known to be computable by constant width polynomial degree circuits (VsSC ⁰), but whether the converse containment holds is an open problem. As a partial answer to this question, we give a construction which shows that syntactically multilinear circuits of constant width and polynomial degree can be depth-reduced, which in our notation shows that sm-VsSC ⁰ ${\subseteq}$ ? sm-VNC ¹. We further strengthen this inclusion, by giving a separate construction that provides a width-efficient simulation for constant width syntactically multilinear circuits by constant width syntactically multilinear algebraic branching programs; in our notation, sm-VsSC ⁰ ${\subseteq}$ ? sm-VBWBP. We then focus on polynomial size syntactically multilinear circuits and study relationships between classes of functions obtained by imposing various resource (width, depth, degree) restrictions on these circuits. Along the way, we also observe a characterization of the class NC ¹ in terms of a restricted class of planar branching programs of polynomial size. Finally, in contrast to the general case, we report closure and stability of coefficient functions for the syntactically multilinear classes studied in this paper.     

A Splitting Algorithm for Image Segmentation on Manifolds Represented by the Grid Based Particle Method

We propose a numerical approach to solve variational problems on manifolds represented by the grid based particle method (GBPM) recently developed in Leung et al. (J. Comput. Phys. 230(7):2540–2561, 2011), Leung and Zhao (J. Comput. Phys. 228:7706–7728, 2009a, J. Comput. Phys. 228:2993–3024, 2009b, Commun. Comput. Phys. 8:758–796, 2010). In particular, we propose a splitting algorithm for image segmentation on manifolds represented by unconnected sampling particles. To develop a fast minimization algorithm, we propose a new splitting method by generalizing the augmented Lagrangian method. To efficiently implement the resulting method, we incorporate with the local polynomial approximations of the manifold in the GBPM. The resulting method is flexible for segmentation on various manifolds including closed or open or even surfaces which are not orientable.     

Error Inhibiting Block One-step Schemes for Ordinary Differential Equations

The commonly used one step methods and linear multi-step methods all have a global error that is of the same order as the local truncation error (as defined in [1, 6, 8, 13, 15]). In fact, this is true of the entire class of general linear methods. In practice, this means that the order of the method is typically defined solely by order conditions which are derived by studying the local truncation error. In this work we investigate the interplay between the local truncation error and the global error, and develop a methodology which defines the construction of explicit error inhibiting block one-step methods (alternatively written as explicit general linear methods [2]). These error inhibiting schemes are constructed so that the accumulation of the local truncation error over time is controlled, which results in a global error that is one order higher than the local truncation error. In this work, we delineate how to carefully choose the coefficient matrices so that the growth of the local truncation error is inhibited. We then use this theoretical understanding to construct several methods that have higher order global error than local truncation error, and demonstrate their enhanced order of accuracy on test cases. These methods demonstrate that the error inhibiting concept is realizable. Future work will further develop new error inhibiting methods and will analyze the computational efficiency and linear stability properties of these methods.     

Small Space Analogues of Valiant’s Classes and the Limitations of Skew Formulas

In the uniform circuit model of computation, the width of a boolean circuit exactly characterizes the “space” complexity of the computed function. Looking for a similar relationship in Valiant’s algebraic model of computation, we propose width of an arithmetic circuit as a possible measure of space. In the uniform setting, we show that our definition coincides with that of VPSPACE at polynomial width. We introduce the class VL as an algebraic variant of deterministic log-space L; VL is a subclass of VP. Further, to define algebraic variants of non-deterministic space-bounded classes, we introduce the notion of “read-once” certificates for arithmetic circuits. We show that polynomial-size algebraic branching programs (an algebraic analog of NL) can be expressed as read-once exponential sums over polynomials in ${{\sf VL}, {\it i.e.}\quad{\sf VBP} \in \Sigma^R \cdot {\sf VL}}$ . Thus, read-once exponential sums can be viewed as a reasonable way of capturing space-bounded non-determinism. We also show that Σ ^R ·VBP = VBP, i.e. VBPs are stable under read-once exponential sums. Though the best upper bound we have for Σ ^R ·VL itself is VNP, we can obtain better upper bounds for width-bounded multiplicatively disjoint (md-) circuits. Without the width restriction, md- arithmetic circuits are known to capture all of VP. We show that read-once exponential sums over md- constant-width arithmetic circuits are within VP and that read-once exponential sums over md- polylog-width arithmetic circuits are within VQP. We also show that exponential sums of a skew formula cannot represent the determinant polynomial.     

An Efficient High-Order Time Integration Method for Spectral-Element Discontinuous Galerkin Simulations in Electromagnetics

We investigate efficient algorithms and a practical implementation of an explicit-type high-order timestepping method based on Krylov subspace approximations, for possible application to large-scale engineering problems in electromagnetics. We consider a semi-discrete form of the Maxwell’s equations resulting from a high-order spectral-element discontinuous Galerkin discretization in space whose solution can be expressed analytically by a large matrix exponential of dimension $\kappa \times \kappa $ . We project the matrix exponential into a small Krylov subspace by the Arnoldi process based on the modified Gram–Schmidt algorithm and perform a matrix exponential operation with a much smaller matrix of dimension $m\times m$ ( $m\ll \kappa $ ). For computing the matrix exponential, we obtain eigenvalues of the $m\times m$ matrix using available library packages and compute an ordinary exponential function for the eigenvalues. The scheme involves mainly matrix-vector multiplications, and its convergence rate is generally $O(\Delta t^{m-1})$ in time so that it allows taking a larger timestep size as $m$ increases. We demonstrate CPU time reduction compared with results from the five-stage fourth-order Runge–Kutta method for a certain accuracy. We also demonstrate error behaviors for long-time simulations. Case studies are also presented, showing loss of orthogonality that can be recovered by adding a low-cost reorthogonalization technique.     

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.     

Negative-Order Norm Estimates for Nonlinear Hyperbolic Conservation Laws

In this paper, we establish negative-order norm estimates for the accuracy of discontinuous Galerkin (DG) approximations to scalar nonlinear hyperbolic equations with smooth solutions. For these special solutions, we are able to extract this “hidden accuracy” through the use of a convolution kernel that is composed of a linear combination of B-splines. Previous investigations into extracting the superconvergence of DG methods using a convolution kernel have focused on linear hyperbolic equations. However, we now demonstrate that it is possible to extend the Smoothness-Increasing Accuracy-Conserving filter for scalar nonlinear hyperbolic equations. Furthermore, we provide theoretical error estimates for the DG solutions that show improvement to $(2k+m)$ -th order in the negative-order norm, where $m$ depends upon the chosen flux.     

Fehlerabschätzung für ein Runge-Kutta-Verfahren mit mehrfachen Knoten

Kastlunger-Wanner [2] recently studied Runge-Kutta methods with multiple nodes. Their paper using Taylor-expansion generalized results ofButcher [1]. In this paper we consider a Runge-Kutta method of order four with two double nodes. Inserting appropriate integration formulas we deduce a clearly arranged representation for the truncation error. Moreover one can easily derive the conditions for the coefficients. The obtained error bound has a rather simple form — compared with the error bound for the usual (classical) Runge-Kutta method — and in some cases carries a better result.     

Fast Polynomial-Space Algorithms Using Inclusion-Exclusion

Given a graph with n vertices, k terminals and positive integer weights not larger than c, we compute a minimum Steiner Tree in $\mathcal{O}^{\star}(2^{k}c)$ time and $\mathcal{O}^{\star}(c)$ space, where the $\mathcal{O}^{\star}$ notation omits terms bounded by a polynomial in the input-size. We obtain the result by defining a generalization of walks, called branching walks, and combining it with the Inclusion-Exclusion technique. Using this combination we also give $\mathcal{O}^{\star}(2^{n})$ -time polynomial space algorithms for Degree Constrained Spanning Tree, Maximum Internal Spanning Tree and #Spanning Forest with a given number of components. Furthermore, using related techniques, we also present new polynomial space algorithms for computing the Cover Polynomial of a graph, Convex Tree Coloring and counting the number of perfect matchings of a graph.