hp-Discontinuous Galerkin Finite Element Methods with Least-Squares Stabilization

We consider a family of hp-version discontinuous Galerkin finite element methods with least-squares stabilization for symmetric systems of first-order partial differential equations. The family includes the classical discontinuous Galerkin finite element method, with and without streamline-diffusion stabilization, as well as the discontinuous version of the Galerkin least-squares finite element method. An hp-optimal error bound is derived in the associated DG-norm. If the solution of the problem is elementwise analytic, an exponential rate of convergence under p-refinement is proved. We perform numerical experiments both to illustrate the theoretical results and to compare the various methods within the family.     

Convergence of linearized backward Euler–Galerkin finite element methods for the time-dependent Ginzburg–Landau equations with temporal gauge

We present error analysis of fully discrete Galerkin finite element methods for the time-dependent Ginzburg–Landau equations with the temporal gauge, where a linearized backward Euler scheme is used for the time discretization. We prove that the convergence rate is O(τ+h^r) if the finite element space of piecewise polynomials of degree r is used. Due to the degeneracy of the problem, the convergence rate is one order lower than the optimal convergence rate of finite element methods for parabolic equations. Numerical examples are provided to support our theoretical analysis.     

Two-level Stabilized Finite Element Methods for the Steady Navier–Stokes Problem

In this article, the two-level stabilized finite element formulations of the two-dimensional steady Navier–Stokes problem are analyzed. A macroelement condition is introduced for constructing the local stabilized formulation of the steady Navier–Stokes problem. By satisfying this condition the stability of the Q₁–P₀ quadrilateral element and the P₁–P₀ triangular element are established. Moreover, the two-level stabilized finite element methods involve solving one small Navier–Stokes problem on a coarse mesh with mesh size H, a large Stokes problem for the simple two-level stabilized finite element method on a fine mesh with mesh size h=O(H²) or a large general Stokes problem for the Newton two-level stabilized finite element method on a fine mesh with mesh size h=O(|log h|^1/2H³). The methods we study provide an approximate solution (u^h,p^h) with the convergence rate of same order as the usual stabilized finite element solution, which involves solving one large Navier–Stokes problem on a fine mesh with mesh size h. Hence, our methods can save a large amount of computational time.     

The Streamline–Diffusion Method for Conforming and Nonconforming Finite Elements of Lowest Order Applied to Convection–Diffusion Problems

We consider the streamline-diffusion finite element method with finite elements of lowest order for solving convection-diffusion problems. Our investigations cover both conforming and nonconforming finite element approximations on triangular and quadrilateral meshes. Although the considered finite elements are of the same interpolation order their stability and approximation properties are quite different. We give a detailed overview on the stability and the convergence properties in the L ²- and in the streamline–diffusion norm. Numerical experiments show that often the theoretical predictions on the convergence properties are sharp. Received December 7, 1999; revised October 5, 2000     

Root-finding by expansion with independent constraints

Elimination methods are highly effective for the solution of linear and nonlinear systems of equations, but reversal of the elimination principle can be beneficial as well: competent incorporation of additional independent constraints and variables or more generally immersion of the original computational problem into a larger task, defined by a larger number of independent constraints and variables can improve global convergence of iterative algorithms, that is their convergence from the start. A well known example is the dual linear and nonlinear programming, which enhances the power of optimization algorithms. We believe that this is just an ad hoc application of general Principle of Expansion with Independent Constraints; it should be explored systematically for devising iterative algorithms for the solution of equations and systems of equations and for optimization. At the end of this paper we comment on other applications and extensions of this principle.Presently we show it at work for the approximation of a single zero of a univariate polynomial p of a degree n. Empirical global convergence of the known algorithms for this task is much weaker than that of the algorithms for all n zeros, such as Weierstrass–Durand–Kerner’s root-finder, which reduces its root-finding task to Viète’s (Vieta’s) system of n polynomial equations with n unknowns. We adjust this root-finder to the approximation of a single zero of p, preserve its fast global convergence and decrease the number of arithmetic operations per iteration from quadratic to linear. Together with computing a zero of a polynomial p, the algorithm deflates this polynomial as by-product, and then could be reapplied to the quotient to approximate the next zero of p. Alternatively by using m processors that exchange no data, one can concurrently approximate up to m zeros of p. Our tests confirm the efficiency of the proposed algorithms.Technically our root-finding boils down to computations with structured matrices, polynomials and partial fraction decompositions. Our study of these links can be of independent interest; e.g., as by-product we express the inverse of a Sylvester matrix via its last column, thus extending the celebrated result of Gohberg and Sementsul (1972) [22] from Toeplitz to Sylvester matrix inverses.     

Superconvergence of Discontinuous Finite Element Solutions for Transient Convection–diffusion Problems

We present a study of the local discontinuous Galerkin method for transient convection–diffusion problems in one dimension. We show that p-degree piecewise polynomial discontinuous finite element solutions of convection-dominated problems are O(Δx ^p+2) superconvergent at Radau points. For diffusion- dominated problems, the solution’s derivative is O(Δx ^p+2) superconvergent at the roots of the derivative of Radau polynomial of degree p+1. Using these results, we construct several asymptotically exact a posteriori finite element error estimates. Computational results reveal that the error estimates are asymptotically exact.This revised version was published online in July 2005 with corrected volume and issue numbers.     

Self-adaptive finite elements in fracture mechanics

A new finite element capability which permits the analyst to vary the order of polynomial approximation over each finite element is discussed with reference to its potential for application to stress intensity factor computations in linear elastic fracture mechanics. Computational experiments, in which polynomial orders ranging from 1 to 8 were used, indicated strong and monotonie convergence of the strain energy release rate even for very coarse finite element meshes as the order p of the approximating polynomial was increased. Pointwise convergence of stresses was achieved by averaging approximations of different polynomial orders. The strong and monotonie convergence of K_I factors with respect to increasing p provides a new method for computing stress intensity factors. The main advantage of this method is that the accuracy of approximation can be established without mesh refinement or the use of special procedures.     

二阶收敛的光滑正则化压缩感知信号重构方法

目的压缩感知信号重构过程是求解不定线性系统稀疏解的过程。针对不定线性系统稀疏解3种求解方法不够鲁棒的问题:最小化l₀-范数属于NP问题,最小化l₁-范数的无解情况以及最小化l_p-范数的非凸问题,提出一种基于光滑正则凸优化的方法进行求解。方法为了获得全局最优解并保证算法的鲁棒性,首先,设计了全空间信号l₀-范数凸拟合函数作为优化的目标函数;其次,将n元函数优化问题转变为n个一元函数优化问题;最后,求解过程中利用快速收缩算法进行求解,使收敛速度达到二阶收敛。结果该算法无论在仿真数据集还是在真实数据集上,都取得了优于其他3种类型算法的效果。在仿真实验中,当信号维数大于150维时,该方法重构时间为其他算法的50%左右,具有快速性;在真实数据实验中,该方法重构出的信号与原始信号差的F-范数为其他算法的70%,具有良好的鲁棒性。结论本文算法为二阶收敛的凸优化算法,可确保快速收敛到全局最优解,适合处理大型数据,在信息检索、字典学习和图像压缩等领域具有较大的潜在应用价值。     

Quadratic Finite Element Approximations of the Monge-Amp��re Equation

We prove several new results of the C ⁰ finite element method introduced in (S.C.?Brenner et al., Math. Comput. 80:1979?C1995, 2011) for the fully nonlinear Monge-Ampère equation. These include the convergence of quadratic finite element approximations, W ^2,p quasi-optimal error estimates, localized pointwise error estimates, and convergence of Newton??s method with explicit dependence on the discretization parameter. Numerical experiments are presented which back up the theoretical results.     

A Refined Finite Element Convergence Theory for Highly Indefinite Helmholtz Problems

It is well known that standard h-version finite element discretisations using lowest order elements for Helmholtz' equation suffer from the following stability condition: ``The mesh width h of the finite element mesh has to satisfy k <sup>2</sup> h≲1', where k denotes the wave number. This condition rules out the reliable numerical solution of Helmholtz equation in three dimensions for large wave numbers k≳50. In our paper, we will present a refined finite element theory for highly indefinite Helmholtz problems where the stability of the discretisation can be checked through an ``almost invariance' condition. As an application, we will consider a one-dimensional finite element space for the Helmholtz equation and apply our theory to prove stability under the weakened condition hk≲1 and optimal convergence estimates. Dedicated to Prof. Dr. Ivo Babuška on the occasion of his 80th birthday.     

Materially and geometrically nonlinear analysis of laminated anisotropic plates by p-version of FEM

A p-version finite element model based on degenerate shell element is proposed for the analysis of orthotropic laminated plates. In the nonlinear formulation of the model, the total Lagrangian formulation is adopted with moderately large deflections and small rotations being accounted for in the sense of von Karman hypothesis. The material model is based on the Huber-Mises yield criterion and Prandtl-Reuss flow rule in accordance with the theory of strain hardening yield function, which is generalized for anisotropic materials by introducing the parameters of anisotropy. The model is also based on the equivalent-single layer laminate theory. The integrals of Legendre polynomials are used for shape functions with p-level varying from 1 to 10. Gauss-Lobatto numerical quadrature is used to calculate the stresses at the nodal points instead of Gauss points. The validity of the proposed p-version finite element model is demonstrated through several comparative points of view in terms of ultimate load, convergence characteristics, nonlinear effect, and shape of plastic zone.     

A Hermitian Box-scheme for One-dimensional Elliptic Equations – Application to Problems with High Contrasts in the Ellipticity

We introduce a new box-scheme, called ``hermitian box-scheme' on the model of the one-dimensional Poisson problem. The scheme combines features of the box-scheme of Keller, [20], [13], with the hermitian approximation of the gradient on a compact stencil, which is characteristic of compact schemes, [9], [21]. The resulting scheme is proved to be 4th order accurate for the primitive unknown u and its gradient p. The proved convergence rate is 1.5 for (u,p) in the discrete L ² norm. The connection with a non standard mixed finite element method is given. Finally, numerical results are displayed on pertinent 1-D elliptic problems with high contrasts in the ellipticity, showing in practice convergence rates ranging from 1 to 2.5 in the discrete H ¹ norm. This work has been performed with the support of the GDR MOMAS, (ANDRA, CEA, EDF, BRGM and CNRS): Modélisation pour le stockage des déchets radioactifs. The author thanks especially A. Bourgeat for his encouragements and his interest in this work.     

Fast adaptive algorithms for minor component analysis using Householder transformation

In this paper, we propose new adaptive algorithms for the extraction and tracking of the least (minor) or eventually, principal eigenvectors of a positive Hermitian covariance matrix. The main advantage of our proposed algorithms is their low computational complexity and numerical stability even in the minor component analysis case. The proposed algorithms are considered fast in the sense that their computational cost is O(np) flops per iteration where n is the size of the observation vector and p<n is the number of eigenvectors to estimate.We consider OJA-type minor component algorithms based on the constraint and non-constraint stochastic gradient technique. Using appropriate fast orthogonalization procedures, we introduce new fast algorithms that extract the minor (or principal) eigenvectors and guarantee good numerical stability as well as the orthogonality of their weight matrix at each iteration. In order to have a faster convergence rate, we propose a normalized version of these algorithms by seeking the optimal step-size. Our algorithms behave similarly or even better than other existing algorithms of higher complexity as illustrated by our simulation results.     

Finite element analysis of the Girkmann problem using the modern hp-version and the classical h-version

We perform finite element analysis of the so called Girkmann problem in structural mechanics. The problem involves an axially symmetric spherical shell stiffened with a foot ring and is approached (1) by using the axisymmetric formulation of linear elasticity theory and (2) by using a dimensionally reduced shell-ring model. In the first approach the problem is solved with a fully automatic hp-adaptive finite element solver whereas the classical h-version of the finite element method is used in the second approach. We study the convergence behaviour of the different numerical models and show that accurate stress resultants can be obtained with both models by using effective post-processing formulas.     

Convergence of an upwind control-volume mixed finite element method for convection–diffusion problems

Summary We consider a upwind control volume mixed finite element method for convection–diffusion problem on rectangular grids. These methods use the lowest order Raviart–Thomas mixed finite element space as the trial functional space and associate control-volumes, or covolumes, with the vector variable as well as the scalar variable. Chou et al. [6] established a one-half order convergence in discrete L ²-norms. In this paper, we establish a first order convergence for both the vector variable as well as the scalar variable in discrete L ²-norms.      

Optimal Quadrilateral Finite Elements on Polygonal Domains

We propose three quadrilateral mesh refinement algorithms to improve the convergence of the finite element method approximating the singular solutions of elliptic equations, which are due to the non-smoothness of the domain. These algorithms result in graded meshes consisting of convex and shape-regular quadrilaterals. With analysis in weighted spaces, we provide the selection criteria for the grading parameter, such that the optimal convergence rate can be recovered for the associated finite element approximation. Various numerical tests verify the theory. In addition to the bi-k elements, we also investigate the serendipity elements on the graded quadrilateral meshes in the numerical experiments.     

Antichains and compositional algorithms for LTL synthesis

In this paper, we present new monolithic and compositional algorithms to solve the LTL realizability problem. Those new algorithms are based on a reduction of the LTL realizability problem to a game whose winning condition is defined by a universal automaton on infinite words with a k-co-Büchi acceptance condition. This acceptance condition asks that runs visit at most k accepting states, so it implicitly defines a safety game. To obtain efficient algorithms from this construction, we need several additional ingredients. First, we study the structure of the underlying automata constructions, and we show that there exists a partial order that structures the state space of the underlying safety game. This partial order can be used to define an efficient antichain algorithm. Second, we show that the algorithm can be implemented in an incremental way by considering increasing values of k in the acceptance condition. Finally, we show that for large LTL formulas that are written as conjunctions of smaller formulas, we can solve the problem compositionally by first computing winning strategies for each conjunct that appears in the large formula. We report on the behavior of those algorithms on several benchmarks. We show that the compositional algorithms are able to handle LTL formulas that are several pages long.     

The Discontinuous Galerkin Method for Two-Dimensional Hyperbolic Problems. Part I: Superconvergence Error Analysis

In this paper we investigate the superconvergence properties of the discontinuous Galerkin method applied to scalar first-order hyperbolic partial differential equations on triangular meshes. We show that the discontinuous finite element solution is O(h ^p+2) superconvergent at the Legendre points on the outflow edge for triangles having one outflow edge. For triangles having two outflow edges the finite element error is O(h ^p+2) superconvergent at the end points of the inflow edge. Several numerical simulations are performed to validate the theory. In Part II of this work we explicitly write down a basis for the leading term of the error and construct asymptotically correct a posteriori error estimates by solving local hyperbolic problems with no boundary conditions on more general meshes.