Do you want to **read the rest** of this article?

# A BDDC algorithm for a class of staggered discontinuous Galerkin methods

**Article**

*in*Computers & Mathematics with Applications 67(7) · April 2014

*with*87 Reads

**How we measure 'reads'**

A 'read' is counted each time someone views a publication summary (such as the title, abstract, and list of authors), clicks on a figure, or views or downloads the full-text. Learn more

Abstract

A BDDC (Balancing Domain Decomposition by Constraints) algorithm is developed and analyzed for a staggered discontinuous Galerkin (DG) finite element approximation of second order scalar elliptic problems. On a quite irregular subdomain partition, an optimal condition number bound is proved for two-dimensional problems. In addition, a sub-optimal but scalable condition number bound is obtained for three-dimensional problems. These bounds are shown to be independent of coefficient jumps in the subdomain partition. Numerical results are also included to show the performance of the algorithm.

- ... Recently, a new class of discontinuous Galekin methods based on a novel type of staggered grid is introduced in Chung & Engquist [8, 9] for the wave equations, in Chung & Lee [12] and Chung & Kim [10] for the curl-curl operator, in Chung, Ciarlet & Yu [14] for Maxwell's equations, in Chung & Lee [13] for the convection-diffusion equation, in Kim, Chung & Lee [21] for the Stokes system and in Chan & Chung [5] for the Burgers equation. Moreover, wave transmission problems in the interface between classical material and meta-material using this kind of method is proposed and analyzed in Chung & Ciarlet [7], and fast solvers have been developed in Chung, Kim & Widlund [11], Kim, Chung & Lee [22] and Kim, Chung & Lee [23]. These methods have the advantages that the structures, such as energy and mass, arising from the partial differential equations are preserved. ...Article
- Sep 2015
- J COMPUT APPL MATH

In this paper, we develop and analyze a new class of spectral element methods for the simulations of elastic wave propagation. The major components of the method are the spatial discretization and the choice of interpolation nodes. The spatial discretization is based on piecewise polynomial approximation defined on staggered grids. The resulting method combines the advantages of both staggered-grid based methods and classical non-staggered-grid based spectral element methods. Our new method is energy conserving and does not require the use of any numerical flux, because of the staggered local continuity of the basis functions. Our new method also uses Radau points as interpolation nodes, and the resulting mass matrix is diagonal, thus time marching is explicit and is very efficient. Moreover, we give a rigorous proof for the optimal convergence of the method. In terms of dispersion, we present a numerical study for the numerical dispersion and show that this error is of very high order. Finally, some numerical convergence tests and applications to unbounded domain problems with perfectly matched layer are shown. - ... In particular, discretizing (1) by traditional numerical schemes based on finite element or discontinuous Galerkin methods (e.g. [11, 35]) will result in very large and ill-conditioned linear systems, which require large computational times and memory. It is therefore desirable to develop efficient numerical schemes with a small number of degrees of freedom. ...Article
- Jan 2015
- J COMPUT PHYS

The construction of local reduced-order models via multiscale basis functions has been an area of active research. In this paper, we propose online multiscale basis functions which are constructed using the offline space and the current residual. Online multiscale basis functions are constructed adaptively in some selected regions based on our error indicators. We derive an error estimator which shows that one needs to have an offline space with certain properties to guarantee that additional online multiscale basis function will decrease the error. This error decrease is independent of physical parameters, such as the contrast and multiple scales in the problem. The offline spaces are constructed using Generalized Multiscale Finite Element Methods (GMsFEM). We show that if one chooses a sufficient number of offline basis functions, one can guarantee that additional online multiscale basis functions will reduce the error independent of contrast. We note that the construction of online basis functions is motivated by the fact that the offline space construction does not take into account distant effects. Using the residual information, we can incorporate the distant information provided the offline approximation satisfies certain properties. In the paper, theoretical and numerical results are presented. Our numerical results show that if the offline space is sufficiently large (in terms of the dimension) such that the coarse space contains all multiscale spectral basis functions that correspond to small eigenvalues, then the error reduction by adding online multiscale basis function is independent of the contrast. We discuss various ways computing online multiscale basis functions which include a use of small dimensional offline spaces. - ... The errors and convergence rates are shown in the following tables. We remark that we can use the fast solvers developed in [7, 19]. In Tables 1 and 2, we record the errors and convergence rates for the piecewise linear (k = 1) and piecewise quadratic (k = 2) approximations, respectively, for various choices of mesh sizes. ...We show, in the framework of steady-state diffusion boundary-value problems, that the staggered discontinuous Galerkin (SDG) method [SIAM J. Numer. Anal., 47 (2009), pp. 3820–3848] can be obtained from a hybridizable discontinuous Galerkin (HDG) method [SIAM J. Numer. Anal., 47 (2009), pp. 1319–1365] by setting its stabilization function to zero at some suitably chosen element faces and by letting it go to infinity at all the remaining others. We then show that this point of view allows the SDG method to immediately acquire new properties all inherited from the HDG methods, namely, their efficient implementation (by hybridization), their postprocessings, and their superconvergence properties.
- ... However, the new HSDG method considered in this paper is different from any hybridized DG method in the way that no penalty parameter is involved in the scheme. Fast solvers for SDG methods have been recently developed; see [18] for an overlapping Schwarz type method and [19] for a balancing DD by constraints algorithm. To address a fast solver for the discrete system resulting from the HSDG discretization, we will see that the structure of the system naturally allows the use of a FETI-DP DD algorithm [20, 21], where the original algebraic equation is decoupled into subdomain problems, and the continuity of the solution on the subdomain interfaces is enforced strongly at the selected set of primal unknowns and weakly at the remaining unknowns on the interface by using Lagrange multipliers. ...Article
- Apr 2014
- Int J Numer Meth Eng

Convergence theories and a deluxe dual and primal finite element tearing and interconnecting algorithm are developed for a hybrid staggered DG finite element approximation of H(curl) elliptic problems in two dimensions. In addition to the advantages of staggered DG methods, the basis functions of the new hybrid staggered DG method are all locally supported in the triangular elements, and a Lagrange multiplier approach is applied to enforce the global connections of these basis functions. The interface problem on the Lagrange multipliers is further reduced to the resulting problem on the subdomain interfaces, and a dual and primal finite element tearing and interconnecting algorithm with an enriched weight factor is then applied to the resulting problem. Our algorithm is shown to give a condition number bound of C(1 + log(H ∕ h))2, independent of the two parameters, where H ∕ h is the number of triangles across each subdomain. Numerical results are included to confirm our theoretical bounds. Copyright © 2013 John Wiley & Sons, Ltd. - Article
- Oct 2017
- J SCI COMPUT

In this paper, we present for the first time guaranteed upper bounds for the staggered discontinuous Galerkin method for diffusion problems. Two error estimators are proposed for arbitrary polynomial degrees and provide an upper bound on the energy error of the scalar unknown and \(L^2\)-error of the flux, respectively. Both error estimators are based on the potential and flux reconstructions. The potential reconstruction is given by a simple averaging operator. The equilibrated flux reconstruction can be found by solving local Neumann problems on elements sharing an edge with a Raviart–Thomas mixed method. Reliability and efficiency of the two a posteriori error estimators are proved. Numerical results are presented to validate the theoretical results. - Article
- Sep 2016
- J COMPUT APPL MATH

A BDDC (Balancing Domain Decomposition by Constraints) algorithm for a staggered discontinuous Galerkin approximation is considered. After applying domain decomposition method, a global linear system on the subdomain interface unknowns is obtained and solved by the conjugate gradient method combined with a preconditioner. To construct a preconditioner that is robust to the coefficient variations, a generalized eigenvalue problem on each subdomain interface is solved and primal unknowns are selected from the eigenvectors using a predetermined tolerance. By the construction of the staggered discontinuous Galerkin methods, the degrees of freedom on subdomain interfaces are shared by only two subdomains, and hence the construction of primal unknowns are simplified. The resulting BDDC algorithm is shown to have the condition number bounded by the predetermined tolerance. A modified algorithm for parameter dependent problems is also introduced, where the primal unknowns are only computed in an offline stage. Numerical results are included to show the performance of the proposed method and to verify the theoretical estimate. - Article
- Mar 2016
- COMPUT MATH APPL

A mortar formulation is developed and analyzed for a class of staggered discontinuous Galerkin (SDG) methods applied to second order elliptic problems in two dimensions. The computational domain consists of nonoverlapping subdomains and a triangulation is provided for each subdomain, which need not conform across subdomain interfaces. This feature allows a more flexible design of discrete models for problems with complicated geometries, shocks, or singular points. A mortar matching condition is enforced on the solutions across the subdomain interfaces by introducing a Lagrange multiplier space. Moreover, optimal convergence rates in both and discrete energy norms are proved. Numerical results are presented to show the performance of the method. - Article
- Apr 2015
- MULTISCALE MODEL SIM

A balancing domain decomposition by constraints (BDDC) algorithm with enriched coarse spaces is developed and analyzed for two-dimensional elliptic problems with oscillatory and high contrast coefficients. To obtain a robust algorithm based on the classical BDDC framework for conforming finite element methods, a set of enriched primal unknowns is constructed. The enriched component of the primal unknowns is chosen to reflect the local structures of the coefficient by solving two types of generalized eigenvalue problems. These problems are solved locally for every two adjacent subdomains, so that the computations of the enriched primal unknowns are very efficient. Given a tolerance, dominant eigenfunctions with eigenvalues larger than this tolerance are precomputed and used to form coarse basis functions. The resulting condition number by using this enriched coarse space is proved to be bounded above by this tolerance and the maximum number of edges per subdomain, independent of the contrast of the given coefficient. Furthermore, numerical results are presented for various model problems and various choices of primal unknowns to show the performance of the proposed algorithm. - Accurate simulation of seismic waves is of critical importance in a variety of geophysical applications. Based on recent works on staggered discontinuous Galerkin methods, we have developed a new method for the simulations of seismic waves, which has energy conservation and extremely low grid dispersion, so that it naturally provided accurate numerical simulations of wave propagation useful for geophysical applications and was a generalization of classical staggered-grid finite-difference methods. Moreover, it could handle with ease irregular surface topography and discontinuities in the subsurface models. Our new method discretized the velocity and the stress tensor on this staggered grid, with continuity imposed on different parts of the mesh. The symmetry of the stress tensor was enforced by the Lagrange multiplier technique. The resulting method was an explicit scheme, requiring the solutions of a block diagonal system and a local saddle point system in each time step, and it was, therefore, very efficient. To tailor our scheme to Rayleigh waves, we developed a mortar formulation of our method. Specifically, a fine mesh was used near the free surface and a coarse mesh was used in the rest of the domain. The two meshes were in general not matching, and the continuity of the velocity at the interface was enforced by a Lagrange multiplier. The resulting method was also efficient in time marching. We also developed a stability analysis of the scheme and an explicit bound for the time step size. In addition, we evaluated some numerical results and found that our method was able to preserve the wave energy and accurately computed the Rayleigh waves. Moreover, the mortar formulation gave a significant speed up compared with the use of a uniform fine mesh, and provided an efficient tool for the simulation of Rayleigh waves.
- Article
- Jun 2014
- APPL MATH COMPUT

In this paper, we present the first a-posteriori error analysis for the staggered discontinuous Galerkin (SDG) method. Specifically, we consider the approximation of the time-harmonic Maxwell's equations by a SDG method, and prove that our residual based a-posteriori error indicator is both reliable and efficient. We validate the performance of the indicator within an adaptive mesh refinement procedure and show its asymptotic exactness for a range of test problems. - Article
- Dec 2014
- COMPUT MATH APPL

In this paper, a class of FETI-DP preconditioners is developed for a fast solution of the linear system arising from staggered discontinuous Galerkin discretization of the two-dimensional Stokes equations. The discretization has been recently developed and has the distinctive advantages that it is optimally convergent and has a good local conservation property. In order to efficiently solve the linear system, two kinds of FETI-DP preconditioners, namely, lumped and Dirichlet preconditioners, are considered and analyzed. Scalable bounds C(H/h)C(H/h) and C(1+log(H/h))2C(1+log(H/h))2 are proved for the lumped and Dirichlet preconditioners, respectively, with the constant CC depending on the inf–sup constant of the discrete spaces but independent of any mesh parameters. Here H/hH/h stands for the number of elements across each subdomain. Numerical results are presented to confirm the theoretical estimates.

- In this paper, we study domain decomposition preconditioners for multiscale ∞ows in high contrast media. Our problems are motivated by porous media applications where low conductivity regions play an important role in determin- ing ∞ow patterns. We consider ∞ow equations governed by elliptic equations in heterogeneous media with large contrast between high and low conductivity regions. This contrast brings an additional small scale (in addition to small spatial scales) into the problem expressed as the ratio between low and high conductivity values. Using weighted coarse interpolation, we show that the condition number of the preconditioned systems using domain decomposition methods is independent of the contrast. For this purpose, Poincare inequalities for weighted norms are proved in the paper. The results are further generalized by employing extension theorems from homogenization theory. Our numerical observations conflrm the theoretical results.
- Article
- Apr 2012
- J Numer Math

This paper is concerned with the staggered discontinuous Galerkin method for convection-diffusion equations. Over the past few decades, staggered type methods have been applied successfully to many problems, such as wave propagation and fluid flow problems. A distinctive feature of these methods is that the physical laws arising from the corresponding partial differential equations are automatically preserved. Nevertheless, staggered methods for convection-diffusion equations are rarely seen in literature. It is thus the main goal of this paper to develop and analyze a class of staggered numerical schemes for the approximation of convection-diffusion equations. We will prove that our new method preserves the underlying physical laws in some discrete sense.Moreover, the stability and convergence of the method are proved. Numerical results are shown to verify the theoretical estimates. - Discontinuous Galerkin (DG) methods are a cl ass of efficient tools for solving fluid flow problems. There are in the literature many greatly successful DG methods. In this paper, a new staggered DG method for the Stokes system is developed and analyzed. The key feature of our method is that the discrete system preserves the structures of the continuous problem, which results from the use of our new staggered DG spaces. This also provides local and global conservation properties, which are desirable for fluid flow applications. The method is based on the first order mixed formulation involving pressure, velocity, and velocity gradient. The velocity and velocity gradient are approximated by polynomials of the same degree while the choice of polynomial degree for pressure is flexible, namely, the approximation degree for pressure can be chosen as either that of velocity or one degree lower than that of velocity. In any case, stability and optimal convergence of the method are proved. Moreover, a superconvergence result with respect to a discrete H 1-norm for the velocity is proved. Furthermore, a local postprocessing technique is proposed to improve the divergence free property of the velocity approximation and it is proved that the postprocessed velocity retains the original accuracy and is weakly divergence free with respect to pressure test functions. Numerical results are included to validate our theoretical estimates and to present the ability of our method for capturing singular solutions.
- Two overlapping Schwarz algorithms are developed for a discontinuous Galerkin (DG) finite element approximation of second order scalar elliptic problems in both two and three dimensions. The discontinuous Galerkin formulation is based on a staggered discretization introduced by Chung and Engquist [13] for the acoustic wave equation. Two types of coarse problems are introduced for the two-level Schwarz algorithms. The first is built on a nonoverlapping subdomain partition, which allows quite general subdomain partitions, and the second on introducing an additional coarse triangulation that can also be quite independent of the fine triangulation. Condition number bounds are established and numerical results are presented.
- Article
- May 2013
- Numer Lin Algebra Appl

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. - In this article we address the question of efficiently solving the algebraic linear system of equations arising from the discretization of a symmetric, elliptic boundary value problem using hp-version discontinuous Galerkin finite element methods. In particular, we introduce a class of domain decomposition preconditioners based on the Schwarz framework, and prove bounds on the condition number of the resulting iteration operators. Numerical results confirming the theoretical estimates are also presented.
- Article
- Jul 2000
- Numer Meth Part Differ Equat

In this article, we analyze a discontinuous finite element method recently introduced by Bassi and Rebay for the approximation of elliptic problems. Stability and error estimates in various norms are proven. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 365–378, 2000 - Article
- Feb 2003
- SIAM J NUMER ANAL

Poincaré--Friedrichs inequalities for piecewise H1 functions are established. They can be applied to classical nonconforming finite element methods, mortar methods, and discontinuous Galerkin methods. - In this article, we discuss domain decomposition parallel iterative solvers for highly heterogeneous problems of flow and transport in porous media. We are particularly interested in highly unstructured coefficient variation where standard periodic or stochastic homogenization theory is not applicable. When the smallest scale at which the coefficient varies is very small, it is often necessary to scale up the equation to a coarser grid to make the problem computationally feasible. Standard upscaling or multiscale techniques require the solution of local problems in each coarse element, leading to a computational complexity that is at least linear in the global number N of unknowns on the subgrid. Moreover, except for the periodic and the isotropic random case, a theoretical analysis of the accuracy of the upscaled solution is not yet available. Multilevel iterative methods for the original problem on the subgrid, such as multigrid or domain decomposition, lead to similar computational complexity (i.e. 𝒪(N)) and are therefore a viable alternative. However, previously no theory was available guaranteeing the robustness of these methods to large coefficient variation. We review a sequence of recent papers where simple variants of domain decomposition methods, such as overlapping Schwarz and one-level FETI, are proposed that are robust to strong coefficient variation. Moreover, we also extend the theoretical results, for the first time, to the dual-primal variant of FETI.
- Book
- Jan 2003

The first iterative methods used for solving large linear systems were based on relaxation of the coordinates. Beginning with a given approximate solution, these methods modify the components of the approximation, one or a few at a time and in a certain order, until convergence is reached. Each of these modifications, called relaxation steps, is aimed at annihilating one or a few components of the residual vector. Now these techniques are rarely used separately. However, when combined with the more efficient methods described in later chapters, they can be quite successful. Moreover, there are a few application areas where variations of these methods are still quite popular. - Article
- Oct 2003
- Numer Lin Algebra Appl

A convergence theory is presented for a substructuring preconditioner based on constrained energy minimization concepts. The substructure spaces consist of local functions with zero values of the constraints, while the coarse space consists of minimal energy functions with the constraint values continuous across substructure interfaces. In applications, the constraints include values at corners and optionally averages on edges and faces. The preconditioner is reformulated as an additive Schwarz method and analysed by building on existing results for balancing domain decomposition. The main result is a bound on the condition number based on inequalities involving the matrices of the preconditioner. Estimates of the form C(1+log2(H/h)) are obtained under the standard assumptions of substructuring theory. Computational results demonstrating the performance of method are included. Published in 2003 by John Wiley & Sons, Ltd. - Article
- Mar 2001
- Int J Numer Meth Eng

The FETI method and its two-level extension (FETI-2) are two numerically scalable domain decomposition methods with Lagrange multipliers for the iterative solution of second-order solid mechanics and fourth-order beam, plate and shell structural problems, respectively.The FETI-2 method distinguishes itself from the basic or one-level FETI method by a second set of Lagrange multipliers that are introduced at the subdomain cross-points to enforce at each iteration the exact continuity of a subset of the displacement field at these specific locations. In this paper, we present a dual–primal formulation of the FETI-2 concept that eliminates the need for that second set of Lagrange multipliers, and unifies all previously developed one-level and two-level FETI algorithms into a single dual–primal FETI-DP method. We show that this new FETI-DP method is numerically scalable for both second-order and fourth-order problems. We also show that it is more robust and more computationally efficient than existing FETI solvers, particularly when the number of subdomains and/or processors is very large. Copyright © 2001 John Wiley & Sons, Ltd. - Chapter
- Jan 2009

In the theory for domain decomposition methods, it has previously often been assumed that each subdomain is the union of a small set of coarse shape-regular triangles or tetrahedra. Recent progress is reported, which makes it possible to analyze cases with irregular subdomains such as those produced by mesh partitioners. The goal is to extend the analytic tools so that they work for problems on subdomains that might not even be Lipschitz and to characterize the rates of convergence of domain decomposition methods in terms of a few, easy to understand, geometric parameters of the subregions. For two dimensions, some best possible results have already been obtained for scalar elliptic and compressible and almost incompressible linear elasticity problems; the subdomains should be John or Jones domains and the rates of convergence are determined by parameters that characterize such domains and that of an isoperimetric inequality. Technical issues for three dimensional problems are also discussed. - Chapter
- Aug 2008

Standard Galerkin methods based on C0-piecewise-polynomial spaces often can lead to unsatisfactory approximations of solutions of problems having dominant transport terms. A penalty on the jump in the normal derivative across the interior edges of elements can produce an apparent stiffness intermediate between C0 and C1, and such a method is proposed and analyzed for elliptic and parabolic equations. - Article
- Jul 2005
- APPL NUMER MATH

FETI and BDD are two widely used substructuring methods for the solution of large sparse systems of linear algebraic equations arising from discretization of elliptic boundary value problems. The two most advanced variants of these methods are the FETI-DP and the BDDC methods, whose formulation does not require any information beyond the algebraic system of equations in a substructure form. We formulate the FETI-DP and the BDDC methods in a common framework as methods based on general constraints between the substructures, and provide a simplified algebraic convergence theory. The basic implementation blocks including transfer operators are common to both methods. It is shown that commonly used properties of the transfer operators in fact determine the operators uniquely. Identical algebraic condition number bounds for both methods are given in terms of a single inequality, and, under natural additional assumptions, it is proved that the eigenvalues of the preconditioned problems are the same. The algebraic bounds imply the usual polylogarithmic bounds for finite elements, independent of coefficient jumps between substructures. Computational experiments confirm the theory. - Article
- Aug 2007
- J COMPLEXITY

A discontinuous Galerkin (DG) discretization of Dirichlet problem for second-order elliptic equations with discontinuous coefficients in 2-D is considered. For this discretization, balancing domain decomposition with constraints (BDDC) algorithms are designed and analyzed as an additive Schwarz method (ASM). The coarse and local problems are defined using special partitions of unity and edge constraints. Under certain assumptions on the coefficients and the mesh sizes across ∂Ωi, where the Ωi are disjoint subregions of the original region Ω, a condition number estimate C(1+maxilog(Hi/hi))2 is established with C independent of hi, Hi and the jumps of the coefficients. The algorithms are well suited for parallel computations and can be straightforwardly extended to the 3-D problems. Results of numerical tests are included which confirm the theoretical results and the necessity of the imposed assumptions. - Article
- Jan 2007
- COMPUT METHOD APPL M

The connection between the BDDC (balancing domain decomposition by constraints) algorithm and the FETI-DP (finite element tearing and interconnecting dual–primal) algorithm is discussed in the language of function spaces, operators and linear functionals. - Article
- Jun 2005
- J SCI COMPUT

We present some two-level non-overlapping additive and multiplicative Schwarz methods for a discontinuous Galerkin method for solving the biharmonic equation. We show that the condition numbers of the preconditioned systems are of the order O( H3/h3) for the non-overlapping Schwarz methods, where h and H stand for the fine mesh size and the coarse mesh size, respectively. The analysis requires establishing an interpolation result for Sobolev norms and Poincaré–Friedrichs type inequalities for totally discontinuous piecewise polynomial functions. It also requires showing some approximation properties of the multilevel hierarchy of discontinuous Galerkin finite element spaces. - We propose and analyze several two-level additive Schwarz preconditioners for a weakly over-penalized symmetric interior penalty method for second order elliptic boundary value problems. We also report numerical results that illustrate the parallel performance of these preconditioners. KeywordsDomain decomposition–Two-level additive Schwarz preconditioner–Interior penalty–Weak over-penalization
- Article
- Jul 2012
- IMA J NUMER ANAL

This paper is concerned with a staggered discontinuous Galerkin method for the curl–curl operator arising from the time-harmonic Maxwell equations. One distinctive feature of the method is that the discrete operators preserve the properties of the differential operators. Moreover, the numerical solution automatically satisfies a discrete divergence-free condition. Stability and optimal convergence of the method are analysed. Numerical experiments for smooth and singular solutions are shown to verify the optimal order of convergence. Furthermore, the method is applied to the corresponding eigenvalue problem. Numerical results for rectangular and L-shaped domains show that our method is able to produce nonspurious eigenvalues. - Article
- Jan 2010
- MULTISCALE MODEL SIM

In this paper, robust preconditioners for multiscale flow problems are investigated. We consider elliptic equations with highly varying coefficients. We design and analyze two-level domain decomposition preconditioners that converge independent of the contrast in the media properties. The coarse spaces are constructed using selected eigenvectors of a local spectral problem. Our new construction enriches any given initial coarse space to make it suitable for high-contrast problems. Using the initial coarse space we construct local mass matrices for the local eigenvalue problems. We show that there is a gap in the spectrum of the eigenvalue problem when high-conductivity regions are disconnected. The eigenvectors corresponding to small, asymptotically vanishing eigenvalues are chosen to construct an enrichment of the initial coarse space. Only via a judicious choice of the initial space do we reduce the dimension of the resulting coarse space. Classical coarse basis functions such as multiscale or energy minimizing basis functions can be taken as the basis for the initial coarse space. In particular, if we start with classical multiscale basis, the selected eigenvectors represent only high-conductivity features that cannot be localized within a coarse-grid block, e.g., high-conductivity channels that connect the boundaries of a coarse-grid block. Numerical experiments are presented. The new construction presented here can handle tensor coefficients. The results of this paper substantially extend those presented in [J. Galvis and Y. Efendiev, Multiscale Model. Simul., 8 (2010), pp. 1461-1483], where only scalar coefficients are considered and the coarse space dimension can be very large because the coarse space includes all isolated high-conductivity features that are within a coarse block. - In this paper, we develop and analyze a new class of discontinuous Galerkin (DG) methods for the acoustic wave equation in mixed form. Traditional mixed finite element (FE) methods produce energy conserving schemes, but these schemes are implicit, making the time-stepping inefficient. Standard DG methods give explicit schemes, but these approaches are typically dissipative or suboptimally convergent, depending on the choice of numerical fluxes. Our new method can be seen as a compromise between these two kinds of techniques, in the way that it is both explicit and energy conserving, locally and globally. Moreover, it can be seen as a generalized version of the Raviart-Thomas FE method and the finite volume method. Stability and convergence of the new method are rigorously analyzed, and we have shown that the method is optimally convergent. Furthermore, in order to apply the new method for unbounded domains, we apply our new method with the first order absorbing boundary condition. The stability of the resulting numerical scheme is analyzed.
- Article
- Jan 2008
- SIAM J NUMER ANAL

In the theory for domain decomposition algorithms of the iterative substructuring family, each subdomain is typically assumed to be the union of a few coarse triangles or tetrahedra. This is an unrealistic assumption, in particular if the subdomains result from the use of a mesh partitioner, in which case they might not even have uniformly Lipschitz continuous boundaries. The purpose of this study is to derive bounds for the condition number of these preconditioned conjugate gradient methods which depend only on a parameter in an isoperimetric inequality, two geometric parameters characterizing John and uniform domains, and the maximum number of edges of any subdomain. A related purpose is to explore to what extent well-known technical tools previously developed for quite regular subdomains can be extended to much more irregular subdomains. Some of these results are valid for any John domain, while an extension theorem, which is needed in this study, requires that the subdomains have complements which are uniform. The results, so far, are complete only for problems in two dimensions. Details are worked out for a FETI-DP algorithm and numerical results support the findings. Some of the numerical experiments illustrate that care must be taken when selecting the scaling of the preconditioners in the case of irregular subdomains. - Article
- Jan 2002
- SIAM J NUMER ANAL

We present some two-level nonoverlapping and overlapping additive Schwarz methods for a discontinuous Galerkin method for solving second order elliptic problems. It is shown that the condition numbers of the preconditioned systems are of the order $O(\frac{H}{h})$ for the nonoverlapping Schwarz methods and of the order $O(\frac{H}{\delta})$ for the overlapping Schwarz methods, where h and H stand for the fine-mesh size and the coarse-mesh size, respectively, and $\delta$ denotes the size of the overlaps between subdomains. Numerical experiments are provided to gauge the efficiency of the methods and to validate the theory. - Three Galerkin methods using discontinuous approximation spaces are introduced to solve elliptic problems. The underlying bilinear form for all three methods is the same and is nonsymmetric. In one case, a penalty is added to the form and in another, a constraint on jumps on each face of the triangulation. All three methods are locally conservative and the third one is not restricted. Optimal a priori hp error estimates are derived for all three procedures.
- Three Galerkin methods using discontinuous approximation spaces are introduced to solve elliptic problems. The underlying bilinear form for all three methods is the same and is nonsymmetric. In one case, a penalty is added to the form and in another, a constraint on jumps on each face of the triangulation. All three methods are locally conservative and the third one is not restricted. Optimal a priori hp error estimates are derived for all three procedures.
- We provide a framework for the analysis of a large class of discontinuous methods,for second-order elliptic problems. It allows for the understanding and comparison of most of the dis- continuous Galerkin methods that have been proposed over the past three decades for the numerical treatment of elliptic problems. Key words. elliptic problems, discontinuous Galerkin, interior penalty AMS subject classification. 65N30 PII. S0036142901384162
- Article
- Jan 2007
- COMPUT METHOD APPL M

Iterative substructuring methods with Lagrange multipliers are considered for heterogeneous linear elasticity problems with large discontinuities in the material stiffnesses. In particular, results for algorithms belonging to the family of dual-primal FETI methods are presented. The core issue of these algorithms is the construction of an appropriate global problem, in order to obtain a robust method which converges independently of the material discontinuities. In this article, several necessary and sufficient conditions arising from the theory are numerically tested and confirmed. Furthermore, results of numerical experiments are presented for situations which are not covered by the theory, such as curved edges and material discontinuities not aligned with the interface, and an attempt is made to develop rules for these cases. - Article
- Apr 2006
- INT J NUMER METH ENG

The FETI-DP and BDDC algorithms are reformulated using Block Cholesky factorizations, an approach which can provide a useful framework for the design of domain decomposition algorithms for solving symmetric positive definite linear system of equations. Instead of introducing Lagrange multipliers to enforce the coarse level, primal continuity constraints in these algorithms, a change of variables is used such that each primal constraint corresponds to an explicit degree of freedom. With the new formulation of these algorithms, a simplified proof is provided that the spectra of a pair of FETI-DP and BDDC algorithms, with the same set of primal constraints, are essentially the same. Numerical experiments for a two-dimensional Laplace's equation also confirm this result. - Article
- Sep 2003
- SIAM J SCI COMPUT

A preconditioner for substructuring based on constrained energy minimization concepts is presented. The preconditioner is applicable to both structured and unstructured meshes and offers a straightforward approach for the iterative solution of second- and fourth-order structural mechanics problems. The approach involves constraints associated with disjoint sets of nodes on substructure boundaries. These constraints provide the means for preconditioning at both the substructure and global levels. Numerical examples are presented that demonstrate the good performance of the method in terms of iterations, compute time, and condition numbers of the preconditioned equations. - Article
- May 2008
- ESAIM-MATH MODEL NUM

In this paper we introduce and analyze some non-overlapping multiplicative Schwarz methods for discontinuous Galerkin (DG) approximations of elliptic problems. The construction of the Schwarz preconditioners is presented in a unified framework for a wide class of DG methods. For symmetric DG approximations we provide optimal convergence bounds for the corresponding error propagation operator, and we show that the resulting methods can be accelerated by using suitable Krylov space solvers. A discussion on the issue of preconditioning non-symmetric DG approximations of elliptic problems is also included. Extensive numerical experiments to confirm the theoretical results and to assess the robustness and the efficiency of the proposed preconditioners are provided. - We propose and study some new additive, two-level non-overlapping Schwarz preconditioners for the solution of the algebraic linear systems arising from a wide class of discontinuous Galerkin approximations of elliptic problems that have been proposed up to now. In particular, two-level methods for both symmetric and non-symmetric schemes are introduced and some interesting features, which have no analog in the conforming case, are discussed. Both the construction and analysis of the proposed domain decomposition methods are presented in a unified framework. For symmetric schemes, it is shown that the condition number of the preconditioned system is of order $O(H/h)$, where $H$ and $h$ are the mesh sizes of the coarse and fine grids respectively, which are assumed to be nested. For non-symmetric schemes, we show by numerical computations that the Eisenstat et al. [SIAM J. Numer. Anal. 20 (1983) 345–357] GMRES convergence theory, generally used in the analysis of Schwarz methods for non-symmetric problems, cannot be applied even if the numerical results show that the GMRES applied to the preconditioned systems converges in a finite number of steps and the proposed preconditioners seem to be scalable. Extensive numerical experiments to validate our theory and to illustrate the performance and robustness of the proposed two-level methods are presented.
- We have developed and analyzed a new class of discontinuous Galerkin methods (DG) which can be seen as a compromise between standard DG and the finite element (FE) method in the way that it is explicit like standard DG and energy conserving like FE. In the literature there are many methods that achieve some of the goals of explicit time marching, unstructured grid, energy conservation, and optimal higher order accuracy, but as far as we know only our new algorithms satisfy all the conditions. We propose a new stability requirement for our DG. The stability analysis is based on the careful selection of the two FE spaces which verify the new stability condition. The convergence rate is optimal with respect to the order of the polynomials in the FE spaces. Moreover, the convergence is described by a series of numerical experiments.
- We extend the construction and analysis of the non-overlapping Schwarz preconditioners proposed in Antonietti et al. [Math. Model. Numer. Anal., 41(1):21-54, 2007] and [Math. Model. Numer. Anal., submitted, 2006] to the (non-consistent) super penalty discontinuos Galerkin methods introduced by Babuska et al. [SIAM J. Numer. Anal., 10:863-875, 1973] and by Brezzi et al. [Numer. Methods Partial Differential Equations, 16(4):365-378, 2000]. We show that the resulting preconditioners are scalable, and we provide the convergence estimates. We also present numerical experiments demonstrating the theoretical results.
- Article
- Sep 1997
- SIAM J NUMER ANAL

this paper, we study the Local Discontinuous Galerkin methods for nonlinear, time-dependent convection-diffusion systems. These methods are an extension of the Runge-Kutta Discontinuous Galerkin methods for purely hyperbolic systems to convection-diffusion systems and share with those methods their high parallelizability, their high-order formal accuracy, and their easy handling of complicated geometries, for convection dominated problems. It is proven that for scalar equations, the Local Discontinuous Galerkin methods are L - Article
- Dec 2000
- MATH COMPUT

. We consider a scalar advection{diusion problem and a recently proposed discontinuous Galerkin approximation, which employs discontinuous nite element spaces and suitable bilinear forms containing interface terms that ensure consistency. For the corresponding sparse, nonsymmetric linear system, we propose and study an additive, two{level overlapping Schwarz preconditioner, consisting of a coarse problem on a coarse triangulation and local solvers associated to suitable problems dened on a family of subdomains. This is a generalization of the corresponding overlapping method for approximations on continuous nite element spaces. Related to the lack of continuity of our approximation spaces, some interesting new features arise in our generalization, which have no analog in the conforming case. We prove an upper bound for the number of iterations obtained by using this preconditioner with GMRES, which is independent of the number of degrees of freedom of the original problem and the n...