CBS constants for multilevel splitting of graph-Laplacian and application to preconditioning of discontinuous Galerkin systems

The goal of this work is to derive and justify a multilevel preconditioner of optimal arithmetic complexity for symmetric interior penalty discontinuous Galerkin finite element approximations of second order elliptic problems. Our approach is based on the following simple idea given in [R.D. Lazarov, P.S. Vassilevski, L.T. Zikatanov, Multilevel preconditioning of second order elliptic discontinuous Galerkin problems, Preprint, 2005]. The finite element space of piece-wise polynomials, discontinuous on the partition , is projected onto the space of piece-wise constant functions on the same partition that constitutes the largest space in the multilevel method. The discontinuous Galerkin finite element system on this space is associated to the so-called “graph-Laplacian”. In 2-D this is a sparse M-matrix with -1 as off diagonal entries and nonnegative row sums. Under the assumption that the finest partition is a result of multilevel refinement of a given coarse mesh, we develop the concept of hierarchical splitting of the unknowns. Then using local analysis we derive estimates for the constants in the strengthened Cauchy–Bunyakowski–Schwarz (CBS) inequality, which are uniform with respect to the levels. This measure of the angle between the spaces of the splitting was used by Axelsson and Vassilevski in [Algebraic multilevel preconditioning methods II, SIAM J. Numer. Anal. 27 (1990) 1569–1590] to construct an algebraic multilevel iteration (AMLI) for finite element systems. The main contribution in this paper is a construction of a splitting that produces new estimates for the CBS constant for graph-Laplacian. As a result we have a preconditioner for the system of the discontinuous Galerkin finite element method of optimal arithmetic complexity.     

Strengthened Cauchy–Bunyakowski–Schwarz inequality for a three‐dimensional elasticity system

The constant γ of the strengthened Cauchy–Bunyakowski–Schwarz (CBS) inequality plays a fundamental role in the convergence rate of multilevel iterative methods. The main purpose of this work is to give an estimate of the constant γ for a three‐dimensional elasticity system. The theoretical results obtained are practically important for the successful implementation of the finite element method to large‐scale modelling of complicated structures as they allow us to construct optimal order algebraic multilevel iterative solvers for a wide class of real‐life elasticity problems. Copyright © 2001 John Wiley & Sons, Ltd.     

Robust semi-coarsening multilevel preconditioning of biquadratic FEM systems

While a large amount of papers are dealing with robust multilevel methods and algorithms for linear FEM elliptic systems, the related higher order FEM problems are much less studied. Moreover, we know that the standard hierarchical basis two-level splittings deteriorate for strongly anisotropic problems. A first robust multilevel preconditioner for higher order FEM systems obtained after discretizations of elliptic problems with an anisotropic diffusion tensor is presented in this paper. We study the behavior of the constant in the strengthened CBS inequality for semi-coarsening mesh refinement which is a quality measure for hierarchical two-level splittings of the considered biquadratic FEM stiffness matrices. The presented new theoretical estimates are confirmed by numerically computed CBS constants for a rich set of parameters (coarsening factor and anisotropy ratio). In the paper we consider also the problem of solving efficiently systems with the pivot block matrices arising in the hierarchical basis two-level splittings. Combining the proven uniform estimates with the theory of the Algebraic MultiLevel Iteration (AMLI) methods we obtain an optimal order multilevel algorithm whose total computational cost is proportional to the size of the discrete problem with a proportionality constant independent of the anisotropy ratio.     

Some remarks on the constant in the strengthened CBS inequality: Estimate for hierarchical finite element discretizations of elasticity problems

For a class of two‐dimensional boundary value problems including diffusion and elasticity problems, it is proved that the constants in the corresponding strengthened Cauchy‐Buniakowski‐Schwarz (CBS) inequality in the cases of two‐level hierarchical piecewise‐linear/piecewise‐linear and piecewise‐linear/piecewise‐quadratic finite element discretizations with triangular meshes differ by the factor 0.75. For plane linear elasticity problems and triangulations with right isosceles triangles, formulas are presented that show the dependence of the constant in the CBS inequality on the Poisson's ratio. Furthermore, numerically determined bounds of the constant in the CBS inequality are given for plane linear elasticity problems discretized by means of arbitrary triangles and for three‐dimensional elasticity problems discretized by means of tetrahedral elements. Finally, the robustness of iterative solvers for elasticity problems is discussed briefly. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 469–487, 1999     

A posteriori error estimation for the Stokes–Darcy coupled problem on anisotropic discretization

This paper presents an a posteriori error analysis for the stationary Stokes–Darcy coupled problem approximated by finite element methods on anisotropic meshes in or 3. Korn's inequality for piecewise linear vector fields on anisotropic meshes is established and is applied to non‐conforming finite element method. Then the existence and uniqueness of the approximation solution are deduced for non‐conforming case. With the obtained finite element solutions, the error estimators are constructed and based on the residual of model equations plus the stabilization terms. The lower error bound is proved by means of bubble functions and the corresponding anisotropic inverse inequalities. In order to prove the upper error bound, it is vital that an anisotropic mesh corresponds to the anisotropic function under consideration. To measure this correspondence, a so‐called matching function is defined, and its discussion shows it to be useful tool. With its help, the upper error bound is shown by means of the corresponding anisotropic interpolation estimates and a special Helmholtz decomposition in both media. Copyright © 2016 John Wiley & Sons, Ltd.     

Superconvergent estimates of conforming finite element method for nonlinear time‐dependent Joule heating equations

In this article, we study the superconvergence analysis of conforming bilinear finite element method (FEM) for nonlinear Joule heating equations. Based on the rigorous estimates together with high accuracy analysis of this element, mean value technique and interpolation postprocessing approach, the superclose and superconvergent estimates about the related variables in H¹‐norm are derived for semidiscrete and a linearized backward Euler fully discrete schemes, which extends the results of optimal estimates obtained for conforming FEMs in the previous literature. At last, a numerical experiment is performed to verify the theoretical analysis.     

On the relationship between finite volume and finite element methods applied to the Stokes equations

We investigate the relationship between finite volume and finite element approximations for the lower‐order elements, both conforming and nonconforming for the Stokes equations. These elements include conforming, linear velocity‐constant pressure on triangles, conforming bilinear velocity‐constant pressure on rectangles and their macro‐element versions, and nonconforming linear velocity‐constant pressure on triangles and nonconforming rotated bilinear velocity‐constant pressure on rectangles. By applying the relationship between the two methods, we obtain the convergence finite volume solutions for the Stokes equations. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17: 440–453, 2001.     

Upper bound of the constant in the strengthened C.B.S. inequality for FEM 2D elasticity equations

The basic theory of the strengthened Cauchy–Buniakowskii–Schwarz (C.B.S.) inequality is the main tool in the convergence analysis of the recently proposed algebraic multilevel iterative methods. An upper bound of the constant γ in the strengthened C.B.S. inequality for the case of the finite element solution of 2D elasticity problems is obtained. It is assumed that linear triangle finite elements are used, the initial mesh consisting of right isosceles triangles and the mesh refinement procedure being uniform. For the resulting linear algebraic systems we have proved that γ²<0.75 uniformly on the mesh parameter and on Poisson's ratio ν ? (0, 1/2). Furthermore, the presented numerical tests show that the same relation holds for arbitrary initial right triangulations, even in the case of degeneracy of triangles. The theoretical results obtained are practically important for successful implementation of the finite element method to large-scale modeling of complicated structures. They allow us to construct optimal order algebraic multilevel iterative solvers for a wide class of real–life elasticity problems.     

Robust AMLI methods for parabolic Crouzeix-Raviart FEM systems

For the iterative solution of linear systems of equations arising from finite element discretization of elliptic problems there exist well-established techniques to construct numerically efficient and computationally optimal preconditioners. Among those, most often preferred choices are Multigrid methods (geometric or algebraic), Algebraic MultiLevel Iteration (AMLI) methods, Domain Decomposition techniques.In this work, the method in focus is AMLI. We extend its construction and the underlying theory over to systems arising from discretizations of parabolic problems, using non-conforming finite element methods (FEM). The AMLI method is based on an approximated block two-by-two factorization of the original system matrix. A key ingredient for the efficiency of the AMLI preconditioners is the quality of the utilized block two-by-two splitting, quantified by the so-called Cauchy-Bunyakowski-Schwarz (CBS) constant, which measures the abstract angle between the two subspaces, associated with the two-by-two block splitting of the matrix.The particular choice of space discretization for the parabolic equations, used in this paper, is Crouzeix-Raviart non-conforming elements on triangular meshes. We describe a suitable splitting of the so-arising matrices and derive estimates for the associated CBS constant. The estimates are uniform with respect to discretization parameters in space and time as well as with respect to coefficient and mesh anisotropy, thus providing robustness of the method.     

A multilevel finite element method in space‐time for the Navier‐Stokes problem

A multilevel finite element method in space‐time for the two‐dimensional nonstationary Navier‐Stokes problem is considered. The method is a multi‐scale method in which the fully nonlinear Navier‐Stokes problem is only solved on a single coarsest space‐time mesh; subsequent approximations are generated on a succession of refined space‐time meshes by solving a linearized Navier‐Stokes problem about the solution on the previous level. The a priori estimates and error analysis are also presented for the J‐level finite element method. We demonstrate theoretically that for an appropriate choice of space and time mesh widths: h_j ～ h, k_j ～ k, j = 2, …, J, the J‐level finite element method in space‐time provides the same accuracy as the one‐level method in space‐time in which the fully nonlinear Navier‐Stokes problem is solved on a final finest space‐time mesh. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005     

Superconvergence of a two‐grid method for fourth‐order dispersive‐dissipative wave equations

In this paper, the superconvergence analysis of a two‐grid method (TGM) with low‐order finite elements is presented for the fourth‐order dispersive‐dissipative wave equations for a second order fully discrete scheme. The superclose estimates in the H¹‐norm on the two grids are obtained by the combination technique of the interpolation and Ritz projection. Then, with the help of the interpolated postprocessing technique, the global superconvergence properties are deduced. Finally, numerical results are provided to show the performance of the proposed TGM for conforming bilinear element and nonconforming element, respectively. It shows that the TGM is an effective method to the problem considered of our paper compared with the traditional Galerkin finite element method (FEM).     

On the convergence of nonnested multigrid methods with nested spaces on coarse grids

Multigrid methods for discretized partial differential problems using nonnested conforming and nonconforming finite elements are here defined in the general setting. The coarse‐grid corrections of these multigrid methods make use of different finite element spaces from those on the finest grid. In general, the finite element spaces on the finest grid are nonnested, while the spaces are nested on the coarse grids. An abstract convergence theory is developed for these multigrid methods for differential problems without full elliptic regularity. This theory applies to multigrid methods of nonnested conforming and nonconforming finite elements with the coarse‐grid corrections established on nested conforming finite element spaces. Uniform convergence rates (independent of the number of grid levels) are obtained for both the V and W‐cycle methods with one smoothing on all coarse grids and with a sufficiently large number of smoothings solely on the finest grid. In some cases, these uniform rates are attained even with one smoothing on all grids. The present theory also applies to multigrid methods for discretized partial differential problems using mixed finite element methods. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 265–284, 2000     

Robust multilevel methods for quadratic finite element anisotropic elliptic problems

This paper discusses a class of multilevel preconditioners based on approximate block factorization for conforming finite element methods employing quadratic trial and test functions. The main focus is on diffusion problems governed by a scalar elliptic partial differential equation with a strongly anisotropic coefficient tensor. The proposed method provides a high robustness with respect to non‐grid‐aligned anisotropy, which is achieved by the interaction of the following components: (i) an additive Schur complement approximation to construct the coarse‐grid operator; (ii) a global block (Jacobi or Gauss–Seidel) smoother complementing the coarse‐grid correction based on (i); and (iii) utilization of an augmented coarse grid, which enhances the efficiency of the interplay between (i) and (ii). The performed analysis indicates the high robustness of the resulting two‐level method. Moreover, numerical tests with a nonlinear algebraic multilevel iteration method demonstrate that the presented two‐level method can be applied successfully in the recursive construction of uniform multilevel preconditioners of optimal or nearly optimal order of computational complexity. Copyright © 2013 John Wiley & Sons, Ltd.     

A general approach to analyse preconditioners for two‐by‐two block matrices

Two‐by‐two block matrices arise in various applications, such as in domain decomposition methods or when solving boundary value problems discretised by finite elements from the separation of the node set of the mesh into ‘fine’ and ‘coarse’ nodes. Matrices with such a structure, in saddle point form arise also in mixed variable finite element methods and in constrained optimisation problems. A general algebraic approach to construct, analyse and control the accuracy of preconditioners for matrices in two‐by‐two block form is presented. This includes both symmetric and nonsymmetric matrices, as well as indefinite matrices. The action of the preconditioners can involve element‐by‐element approximations and/or geometric or algebraic multigrid/multilevel methods. Copyright © 2011 John Wiley & Sons, Ltd.     

Upper Bound of the Constant in Strengthened C.B.S. Inequality for Systems of Linear Partial Differential Equations

The constant in the strengthened Cauchy–Bunyakowski–Schwarz (C.B.S.) inequality plays a crucial role in the convergence rate of multilevel iterative methods as well as in the efficiency of a posteriori error estimators, that is the framework of finite element approximations of systems of partial differential equations. We consider an approximation of general systems of linear partial differential equations in R ³. Concerning a multilevel convergence rate corresponding to nested general tetrahedral meshes of size h and 2h, we give an estimate of this constant for general three-dimensional cases.     

Plate Contact问题的混合有限元逼近

论文考虑了Plate Contact问题的混合有限元逼近,其变分问题为第二类四阶椭圆变分不等问题.首先,根据正则化方法,得到原问题的正则化问题.再根据网格依赖范数技巧,考虑了正则化问题的Ciarlet-Raviart混合有限元逼近,并证明了真解与逼近解之间的误差估计.最后通过数值算例验证了理论分析的结果.     

Preconditioning and a posteriori error estimates using h‐ and p‐hierarchical finite elements with rectangular supports

We show some of the properties of the algebraic multilevel iterative methods when the hierarchical bases of finite elements (FEs) with rectangular supports are used for solving the elliptic boundary value problems. In particular, we study two types of hierarchies; the so‐called h‐ and p‐hierarchical FE spaces on a two‐dimensional domain. We compute uniform estimates of the strengthened Cauchy–Bunyakowski–Schwarz inequality constants for these spaces. Moreover, for diagonal blocks of the stiffness matrices corresponding to the fine spaces, the optimal preconditioning matrices can be found, which have tri‐ or five‐diagonal forms for h‐ or p‐refinements, respectively, after a certain reordering of the elements. As another use of the hierarchical bases, the a posteriori error estimates can be computed. We compare them in test examples for h‐ and p‐hierarchical FEs with rectangular supports. Copyright © 2008 John Wiley & Sons, Ltd.     

A robust preconditioner for higher order finite element discretizations in linear elasticity

Based on the auxiliary space method, a preconditioner is studied in this paper for linear systems of equations arising from higher order finite element (FEM) discretizations of linear elasticity equations. The main idea, which is proposed by Xu (Computing 1996; 56 :215–235) for the scalar PDE, is to construct the preconditioner as a combination of a smoother and a coarse level solver, where the systems of equations arising from lower order FEM discretizations are used in the coarse level solver. It is theoretically shown that the condition number of the preconditioned systems is uniformly bounded with respect to both the problem size and moderate Poisson's ratio. When the Poisson's ratio is near the limit of 0.5, we have presented some numerical tests for the case of fourth‐order FEM discretization in a combination with quadratic conforming FEM as a coarse space. The results are almost robust when Poisson's ratio is near the limit of 0.5. Copyright © 2011 John Wiley & Sons, Ltd.     

Error estimates for finite element method solution of the Stokes problem in the primitive variables

Summary In this paper we derive error estimates for a class of finite element approximation of the Stokes equation. These elements, popular among engineers, are conforming lagrangian both in velocity and pressure and therefore based on a mixed variational principle. The error estimates are established from a new Brezzi-type inequality for this kind of mixed formulation. The results are true in 2 or 3 dimensions.     

A balancing domain decomposition by constraints preconditioner for a weakly over‐penalized symmetric interior penalty method

We develop a balancing domain decomposition by constraints preconditioner for a weakly over‐penalized symmetric interior penalty method for second‐order elliptic problems. We show that the condition number of the preconditioned system satisfies similar estimates as those for conforming finite element methods. Corroborating numerical results are also presented. Copyright © 2012 John Wiley & Sons, Ltd.