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

# A deluxe FETI-DP algorithm for a hybrid staggered discontinuous Galerkin method for H(curl)-elliptic problems

**Article**

*in*International Journal for Numerical Methods in Engineering 98(1) · April 2014

*with*40 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

DOI: 10.1002/nme.4617

Cite this publicationAbstract

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.

- ... , N . In contrast to the original choice of diagonal matrices D (i) (see, e.g., [115,112,38,81,130,78,105] for FETI-DP and earlier related works on other domain decomposition methods), there are recent works using nondiag- onal matrices; see, e.g., [24,22,6,18,16]. Nondiagonal scalings were initially introduced for BDDC (see [24]) but they are easily transferable and have already been used in FETI-DP methods; see, e.g., [18,75,62,68]. ...... In contrast to the original choice of diagonal matrices D (i) (see, e.g., [115,112,38,81,130,78,105] for FETI-DP and earlier related works on other domain decomposition methods), there are recent works using nondiag- onal matrices; see, e.g., [24,22,6,18,16]. Nondiagonal scalings were initially introduced for BDDC (see [24]) but they are easily transferable and have already been used in FETI-DP methods; see, e.g., [18,75,62,68]. ...... The nondiagonal scaling matrices used in [24,22,6,18,75,63,16,7,101,17,134,103,62,68] are, however, block diagonal with respect to the underlying geometry, i.e., the blocks are of the size of the edges and the faces. Consider ...ThesisFull-text available
- Jun 2018

Numerical methods are often well-suited for the solution of (elliptic) partial differential equations (PDEs) modeling naturally occuring processes. Many different solvers can be applied to systems which are obtained after discretization by the finite element method. Parallel architectures in modern computers facilitate the efficient use of diverse divide and conquer strategies. The intuitive approach, to divide a large (global) problem into subproblems, which are then solved in parallel, can significantly reduce the solution time. It is obvious that the solvers on the local subproblems then should deliver the contributions of the global solution restricted to the subdomains of computational region. The class of domain decomposition methods provides widely-used iterative algorithms for the parallel solution of implicit finite element problems. Often, an additional coarse space, which introduces a coupling between the subdomains, is used to ensure a global transport of information between the subdomains across the entire domain. The FETI-DP and BDDC domain decomposition methods are highly scalable parallel algorithms. However, when the parameter or coefficient distribution in the underlying partial differential equation becomes highly heterogeneous, classical methods, with a priori chosen coarse spaces, might not converge in a limited number of iterations. A remedy is offered by problem-dependent coarse spaces. These coarse spaces can be provided by adaptive methods, which then can improve the convergence at the cost of additional constraints. In this thesis, we introduce robust FETI-DP and BDDC methods for three-dimensional problems. These methods incorporate constraints, which are computed from local eigenvalue problems on faces and edges between subdomains, into the coarse space. The implementation of the constraints is performed by a deflation or balancing approach or by partial finite element assembly after a transformation of basis. For the latter, we introduce the generalized transformation-of-basis approach and show its correspondence to a deflation or balancing approach. An efficient parallel implementation of adaptive FETI-DP is discussed in the last part of this thesis. We provide weak and strong parallel scalability results for our adaptive algorithm executed on the supercomputer magnitUDE of the University of Duisburg-Essen. For weak scaling, we can show very good results up to 4,096 cores. We can also present very good strong scaling results up to 864 cores. - ... For a variety of PDEs discretized by the finite element method, a poly-logarithmic bound C(1 + log(H/h)) 2 of the spectral condition number of the preconditioned system has been established, where H/h is the maximal ratio of subdomain diameter and element size. Covered cases are scalar diffusion problems [78, 59, 71, 55], linear elasticity [58], Stokes flow [68, 44], almost incompressible elasticity [56, 87, 35], Reissner-Mindlin plates [66], as well as positive definite problems in H(curl) [23, 16, 12, 114] and H(div) [84, 85]. The same kind of bound has been obtained for spectral elements [86], boundary elements [88, 89], mortar methods [40, 41], discontinuous Galerkin [27, 14, 16, 28, 99], and isogeometric analysis [5, 7, 60, 63, 6]. ...... Covered cases are scalar diffusion problems [78, 59, 71, 55], linear elasticity [58], Stokes flow [68, 44], almost incompressible elasticity [56, 87, 35], Reissner-Mindlin plates [66], as well as positive definite problems in H(curl) [23, 16, 12, 114] and H(div) [84, 85]. The same kind of bound has been obtained for spectral elements [86], boundary elements [88, 89], mortar methods [40, 41], discontinuous Galerkin [27, 14, 16, 28, 99], and isogeometric analysis [5, 7, 60, 63, 6]. Without giving a list of further references, Date: May 16, 2016. 1 CST AG, Bad Nauheimer Str. 19, 64289 Darmstadt, Germany (formerly: Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Altenberger Str. ...... The deluxe scaling introduced in [22] (for early experiments see also [21]) breaks with this rule as the weights are dense matrices per subdomain face/edge/vertex. For subdomain faces, it was observed several times, that the deluxe scaling can lead to very good results [23, 84, 7, 16, 66, 50]. Computationally economic versions are discussed in [23, 49]. ...Technical ReportFull-text available
- May 2016

In this theoretical study, we explore how to automate the selection of weights and primal constraints in BDDC methods for general SPD problems. In particular, we address the three-dimensional case and non-diagonal weight matrices, such as the deluxe scaling. We provide an overview of existing approaches, show connections between them, and present new theoretical results: A localization of the global BDDC estimate leads to a reliable condition number bound and to a local generalized eigenproblem on each glob, i.e., each subdomain face, edge, and possibly vertex. We discuss how the eigenvectors corresponding to the smallest eigenvalues can be turned into generalized primal constraints. These can be either treated as they are, or (which is much simpler to implement) be enforced by (possibly stronger) classical primal constraints. We show that the second option is the better one. Furthermore, we discuss equivalent versions of the face and edge eigenproblem which match with previous works and show an optimality property of the deluxe scaling. Lastly, we give a localized algorithm which guarantees the definiteness of the matrix $\tilde S$ underlying the BDDC preconditioner under mild assumptions on the subdomain matrices. - ... Recently, a new class of staggered discontinuous Galerkin methods based on staggered meshes was proposed and analyzed. In particular, the staggered DG (SDG) method has been successfully developed for many wave propagation problems ( Engquist, 2006, 2009; Chung et al., 2013a; Chung and Ciarlet, 2013; Chung and Lee, 2012; Chan et al., 2013) and other applications (Chung et al., 2013b; Kim et al., 2013; Chung and Kim, 2014; Chung et al., 2014a; Kim et al., 2014; Chung et al., 2014b). The SDG method is typically applied to the first order formulation of wave equations, and starts with two sets of irregular, staggered grids, for each of the two unknown functions involved; furthermore, it designs two finite-element spaces on those two sets of staggered grids and carries out integration-by-parts to derive corresponding weak formulations; finally, it applies the standard leap-frog scheme for explicit time stepping. ...... Recently, a new class of staggered discontinuous Galerkin methods based on staggered meshes was proposed and analyzed. In particular, the staggered DG (SDG) method has been successfully developed for many wave propagation problems ( Engquist, 2006, 2009; Chung et al., 2013a; Chung and Ciarlet, 2013; Chung and Lee, 2012; Chan et al., 2013) and other applications (Chung et al., 2013b; Kim et al., 2013; Chung and Kim, 2014; Chung et al., 2014a; Kim et al., 2014; Chung et al., 2014b). The SDG method is typically applied to the first order formulation of wave equations, and starts with two sets of irregular, staggered grids, for each of the two unknown functions involved; furthermore, it designs two finite-element spaces on those two sets of staggered grids and carries out integration-by-parts to derive corresponding weak formulations; finally, it applies the standard leap-frog scheme for explicit time stepping. ...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.
- ... (i) u ; see (4.5). Secondly, we introduce deluxe scaling; see, e.g, [9,7,1,5,3]. Therefore, the Schur complement of the stiffness matrix on the interface Γ, i.e., ...Technical ReportFull-text available
- Apr 2017

http://tu-freiberg.de/sites/default/files/media/fakultaet-fuer-mathematik-und-informatik-fakultaet-1-9277/prep/2017-01_fertig.pdf - ... Last, we consider deluxe-scaling, which was introduced recently; see, e.g, [11,9,1,7,5]. Deluxe-scaling is computationally expensive. Let us define the Schur complement of the stiffness matrix on the interface Γ, i.e., ...Technical ReportFull-text available
- Jul 2017

Axel Klawonn, Martin Kühn, and Oliver Rheinbach. Adaptive FETI-DP and BDDC methods with a generalized transformation of basis for heterogeneous problems. Electron. Trans. Numer. Anal., 49:1–27, 2018. DOI: 10.1553/etna_vol49s1 @article{etna_vol49_pp1-27, author = {Axel Klawonn and Martin K\"uhn and Oliver Rheinbach}, title = {Adaptive FETI-DP and BDDC methods with a generalized transformation of basis for heterogeneous problems}, journal = {Electron. Trans. Numer. Anal.}, volume = {49}, year = {2018}, pages = {1--27}, doi = {10.1553/etna_vol49s1}, } Preprint at: http://tu-freiberg.de/sites/default/files/media/fakultaet-fuer-mathematik-und-informatik-fakultaet-1-9277/prep/preprint_04_fertig.pdf - ... Mostly, they involve the solution of generalized eigenvalue problems to fa- cilitate certain estimates which are needed to prove the condition number bounds for the corresponding domain decomposition method. For instance, adaptive coarse spaces are available for two-level Neumann-Neumann meth- ods [37,36], for overlapping Schwarz algorithms [188,189,94,95] and based thereon for FETI and BDD methods [190,101], and for FETI-DP and BDDC methods [132,49,130,151,131,165]. ...ThesisFull-text available
- Apr 2016

Accurate simulations of transmural wall stresses in artherosclerotic coronary arteries may help to predict plaque rupture. Therefore, a robust and efficient numerical framework for Fluid-Structure Interaction (FSI) of the blood flow and the arterial wall has to be set up, and suitable material laws for the modeling of the fluid and the structural response have to be incorporated. In this thesis, monolithic coupling algorithms and corresponding monolithic preconditioners are used to simulate FSI using highly nonlinear anisotropic polyconvex hyperelastic and anisotropic viscoelastic material models for the arterial wall. An MPI-parallel FSI software from the LifeV library is coupled to the software FEAP in order to enable access to the structural material models implemented in FEAP. To define a benchmark test for highly nonlinear material models in FSI, a simple geometry corresponding to a section of an idealized coronary artery, suitable boundary conditions, and material parameters adapted to experimental data are used. In particular, the geometry is chosen to be nonsymmetric to make effects due to the anisotropy of the structure visible. An initialization phase and several heartbeats are simulated, and systematical studies with meshes of increasing refinement and different space discretizations are carried out. The results indicate that, for the highly nonlinear material models, piecewise quadratic or F-bar element discretizations lead to significantly better results than piecewise linear shape functions. The results using piecewise linear shape functions are less accurate with respect to the displacements and, in particular, to the approximation of the stresses. To improve the performance of the FSI simulations, a more robust preconditioner for the highly nonlinear structural material models has to be used. Therefore, a parallel implementation of the GDSW (Generalized Dryja-Smith-Widlund) preconditioner, which is a geometric two-level overlapping Schwarz preconditioner with energy-minimizing coarse space, is presented. The implementation, which is based on the software library Trilinos, is held flexible to make further extensions of the preconditioner possible. Even though the dimension of its coarse space is comparably large, parallel scalability for two and three dimensional scalar elliptic and linear elastic problems for thousands of cores is demonstrated. Also for unstructured domain decompositions and for a hybrid version of the preconditioner, convincing scalability is presented. When used as a preconditioner for the structure block in FSI simulations, the GDSW preconditioner shows excellent performance as well: scalability for up to 512 cores and a significant reduction of the simulation time and of the number of iterations with respect to the previously used preconditioner, IFPACK, are observed. IFPACK is an algebraic one-level overlapping Schwarz preconditioner. Finally, highly heterogeneous (multiscale) problems are investigated. Since the GDSW coarse space is not robust for general problems of this type, spaces based on Approximate Component Mode Synthesis (ACMS) are considered. On the basis of the ACMS space, coarse spaces for overlapping Schwarz methods are constructed, and a parallel implementation of a special finite element method is presented. For the coarse spaces, preliminary results indicating numerical scalability and robustness are discussed. For the parallel implementation of the special finite element method, very good parallel weak scalability is observed with respect to the construction of the basis functions and to the solution of the resulting linear system using the FETI-DP (Finite Element Tearing and Interconnecting - Dual Primal) method. - ... Therefore, it is desirable to combine these ideas, and develop spectral element methods based on staggered grids. 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]. ...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. - Article
- Apr 2018
- J SCI COMPUT

A hybrid staggered discontinuous Galerkin method is developed for the Korteweg–de Vries equation. The equation is written into a system of first order equations by introducing auxiliary variables. Two sets of finite element functions are introduced to approximate the solution and the auxiliary variables. The staggered continuity of the two finite element function spaces gives a natural flux condition and trace value on the element boundaries in the derivation of Galerkin approximation. On the other hand, to deal with the third order derivative term an hybridization idea is used and additional flux unknowns are introduced. The auxiliary variables can be eliminated in each element and the resulting algebraic system on the solution and the additional flux unknowns is solved. Stability of the semi discrete form is proven for various boundary conditions. Numerical results present the optimal order of \(L^2\)-errors of the proposed method for a given polynomial order. - 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. - Chapter
- Jan 2016

We will consider BDDC domain decomposition algorithms for finite element approximations of a variety of elliptic problems. The BDDC (Balancing Domain Decomposition by Constraints) algorithms were introduced by Dohrmann [5], following the introduction of FETI-DP by Farhat et al. [9]. These two families are closely related algorithmically and have a common theory. The design of a BDDC algorithm involves the choice of a set of primal degrees of freedom and the choice of an averaging operator, which restores the continuity of the approximate solution across the interface between the subdomains into which the domain of the given problem has been partitioned. We will also refer to these operators as scalings. - 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
- Jan 2015
- ELECTRON T NUMER ANA

A bound is obtained for the condition number of a two-level overlapping Schwarz algorithm for problems posed in H (curl) in two dimensions, where the subdomains are only assumed to be John subdomains. The coarse space is based on energy minimization and its dimension equals the number of interior subdomain edges. Local direct solvers are used on the overlapping subdomains. Our bound depends only on a few geometric parameters of the decomposition. This bound is independent of jumps in the coefficients across the interface between the subdomains for most of the different cases considered. Numerical experiments that verify the result are shown, including some with subdomains with fractal edges and others obtained by a mesh partitioner. - 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.

- Article
- Feb 2013
- J COMPUT PHYS

In this paper, a new type of staggered discontinuous Galerkin methods for the three dimensional Maxwell’s equations is developed and analyzed. The spatial discretization is based on staggered Cartesian grids so that many good properties are obtained. First of all, our method has the advantages that the numerical solution preserves the electromagnetic energy and automatically fulfills a discrete version of the Gauss law. Moreover, the mass matrices are diagonal, thus time marching is explicit and is very efficient. Our method is high order accurate and the optimal order of convergence is rigorously proved. It is also very easy to implement due to its Cartesian structure and can be regarded as a generalization of the classical Yee’s scheme as well as the quadrilateral edge finite elements. Furthermore, a superconvergence result, that is the convergence rate is one order higher at interpolation nodes, is proved. Numerical results are shown to confirm our theoretical statements, and applications to problems in unbounded domains with the use of PML are presented. A comparison of our staggered method and non-staggered method is carried out and shows that our method has better accuracy and efficiency. - A BDDC algorithm for Raviart–Thomas vector fields Isogeometric BDDC preconditioners with Deluxe Scaling
- Jan 2013
- 1-23

- Oh
- Clark Ob
- Dr
- L Veiga
- Pavarino Lf
- S Scacchi
- Widlund Ob
- Zampini

Oh D-s, Widlund OB, Clark DR. A BDDC algorithm for Raviart–Thomas vector fields. Technical Report, Department of Computer Science, Courant Institute, New York University, 2013. 33. Beirao da Veiga L, Pavarino LF, Scacchi S, Widlund OB, Zampini S. Isogeometric BDDC preconditioners with Deluxe Scaling. Technical Report, Department of Computer Science, Courant Institute, New York University, 2013. Copyright © 2013 John Wiley & Sons, Ltd. Int. J. Numer. Meth. Engng 2014; 98:1–23 DOI: 10.1002/nme - A BDDC algorithm for Raviart-Thomas vector fields
- Jan 2013

- D-S, Oh
- Ob Widlund
- Dr Clark

Oh D-s, Widlund OB, Clark DR. A BDDC algorithm for Raviart-Thomas vector fields. Technical Report, Department of Computer Science, Courant Institute, New York University, 2013. - Article
- Jan 2014
- INT J NUMER METH ENG

We propose a full Eulerian framework for solving fluid-structure interaction (FSI) problems based on a unified formulation in which the fluid-structure interactions are modeled by introducing an extra stress in the momentum equation. The obtained three-field velocity, pressure and stress system is solved using a stabilized finite element method. The key feature of this unified formulation is the ability to describe different kind of interactions between the fluid and the structure, which can be either elastic or a perfect rigid body, without the need of treating this last case via penalization. The level set method combined with a dynamic anisotropic mesh adaptation is used to track the fluid-solid interface. - 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. - 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. - 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.
- Article
- Jan 2013

We present some recent domain decomposition tools and a BDDC algorithm for 3D problems in the space H(curl; Ω). Of primary interest is a face decomposition lemma which allows us to obtain improved estimates for a BDDC algorithm under less restrictive as-sumptions than have appeared previously in the literature. Numerical results are also presented to confirm the theory and to provide additional insights. - Article
- Jan 2014
- SIAM J SCI COMPUT

A balancing domain decomposition by constraints (BDDC) preconditioner with a novel scaling, introduced by Dohrmann for problems with more than one variable coefficient and here denoted as deluxe scaling, is extended to isogeometric analysis of scalar elliptic problems. This new scaling turns out to be more powerful than the standard ρ- and stiffness scalings considered in a previous isogeometric BDDC study. Our h-analysis shows that the condition number of the resulting deluxe BDDC preconditioner is scalable with a quasi-optimal polylogarithmic bound which is also independent of coefficient discontinuities across subdomain interfaces. Extensive numerical experiments support the theory and show that the deluxe scaling yields a remarkable improvement over the older scalings, in particular for large isogeometric polynomial degree and high regularity. - Article
- Jan 2013
- SIAM J NUMER ANAL

In this paper a Nitsche-type discretization based on a discontinuous Galerkin (DG) method for an elliptic two-dimensional problem with discontinuous coefficients is considered. The problem is posed on a polygonal region Ω which is a union of N disjoint polygonal subdomains Ωi of diameter O(Hi). The discontinuities of the coefficients, possibly very large, are assumed to occur only across the subdomain interfaces ∂Ωi. Inside each subdomain, a conforming finite element space on a quasi-uniform triangulation with mesh size O(hi) is introduced. To handle the nonmatching meshes across the subdomain interfaces, a DG discretization is applied only on the interfaces. For solving the resulting discrete system, a FETI-DP-type method is proposed and analyzed. It is established that the condition number of the preconditioned linear system is estimated by C(1 + maxi logHi/hi)2 with a constant C independent of hi, hi/hj, Hi and the jumps of coefficients. The method is well suited for parallel computations and it can be extended to three-dimensional problems. Numerical results are presented to validate the theory. - 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.
- Article
- Jan 2013
- INT J NUMER ANAL MOD

Staggered discontinuous Galerkin methods have been developed recently and are adopted successfully to many problems such as wave propagation, elliptic equations, convection-diffusion equations and the Maxwell’s equations. For wave propagation, the method is proved to have the desirable properties of energy conservation, optimal order of convergence and blockdiagonal mass matrices. In this paper, we perform an analysis for the dispersion error and the CFL constant. Our results show that the staggered method provides a smaller dispersion error compared with the classical finite element method as well as non-staggered discontinuous Galerkin methods. - 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. - Article
- Jan 2014
- GEOPHYSICS

Conventional finite-difference methods produce accurate solutions to the acoustic and elastic wave equation for many applications, but they face significant challenges when material properties vary significantly over distances less than the grid size. This challenge is likely to occur in reservoir characterization studies, because important reservoir heterogeneity can be present on scales of several meters to ten meters. Here, we describe a new multiscale finite-element method for simulating acoustic wave propagation in heterogeneous media that addresses this problem by coupling fine-and coarse-scale grids. The wave equation is solved on a coarse grid, but it uses basis functions that are generated from the fine grid and allow the representation of the fine-scale variation of the wavefield on the coarser grid. Time stepping also takes place on the coarse grid, providing further speed gains. Another important property of the method is that the basis functions are only computed once, and time savings are even greater when simulations are repeated for many source locations. We first present validation results for simple test models to demonstrate and quantify potential sources of error. These tests show that the fine-scale solution can be accurately approximated when the coarse grid applies a discretization up to four times larger than the original fine model. We then apply the multiscale algorithm to simulate a complete 2D seismic survey for a model with strong, fine-scale scatterers and apply standard migration algorithms to the resulting synthetic seismograms. The results again show small errors. Comparisons to a model that is upscaled by averaging densities on the fine grid show that the multiscale results are more accurate. - The BDDC algorithm is extended to a large class of discontinuous Galerkin (DG) discretizations of second order elliptic problems. An estimate of C(1 + log(H/h))2 is obtained for the condition number of the preconditioned system where C is a constant independent of h or H or large jumps in the coefficient of the problem. Numerical simulations are presented which confirm the theoretical results. A key component for the development and analysis of the BDDC algorithm is a novel perspective presenting the DG discretization as the sum of element-wise “local” bilinear forms. The element-wise perspective allows for a simple unified analysis of a variety of DG methods and leads naturally to the appropriate choice for the subdomain-wise local bilinear forms. Additionally, this new perspective enables a connection to be drawn between the DG discretization and a related continuous finite element discretization to simplify the analysis of the BDDC algorithm.
- Article
- Apr 2014
- COMPUT MATH APPL

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. - Article
- Feb 2013
- J COMPUT APPL MATH

Some electromagnetic materials exhibit, in a given frequency range, effective dielectric permittivity and/or magnetic permeability which are negative. In the literature, they are called negative index materials, left-handed materials or meta-materials. We propose in this paper a numerical method to solve a wave transmission between a classical dielectric material and a meta-material. The method we investigate can be considered as an alternative method compared to the method presented by the second author and co-workers. In particular, we shall use the abstract framework they developed to prove well-posedness of the exact problem. We recast this problem to fit later discretization by the staggered discontinuous Galerkin method developed by the first author and co-worker, a method which relies on introducing an auxiliary unknown. Convergence of the numerical method is proven, with the help of explicit inf–sup operators, and numerical examples are provided to show the efficiency of the method. - Jan 2006
- INT J NUMER METH ENG
- 250-271

- J Li
- Ob Widlund
- Feti-Dp
- Bddc
- Block Cholesky Methods

Li J, Widlund OB. FETI-DP, BDDC, and block Cholesky methods. International Journal for Numerical Methods in Engineering 2006; 66:250-271.- Article
- Jan 2007
- ELECTRON T NUMER ANA

The BDDC (balancing domain decomposition by constraints) methods have been applied successfully to solve the large sparse linear algebraic systems arising from conforming finite element discretizations of elliptic boundary value problems. In this paper, the scalar elliptic problems for flow in porous media are discretized by a hybrid finite element method which is equivalent to a nonconforming finite element method. The BDDC algorithm is extended to these problems which originate as saddle point problems. Edge/face average constraints are enforced across the interface and the same rate of convergence is obtained as in conforming cases. The condition number of the preconditioned system is estimated and numerical experiments are discussed. - 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. - Article
- Jan 2010
- COMPUT METHOD APPL M

In this paper, we introduce a hybridizable discontinuous Galerkin method for Stokes flow. The method is devised by using the discontinuous Galerkin methodology to discretize a velocity–pressure–gradient formulation of the Stokes system with appropriate choices of the numerical fluxes and by applying a hybridization technique to the resulting discretization. One of the main features of this approach is that it reduces the globally coupled unknowns to the numerical trace of the velocity and the mean of the pressure on the element boundaries, thereby leading to a significant reduction in the size of the resulting matrix. Moreover, by using an augmented lagrangian method, the globally coupled unknowns are further reduced to the numerical trace of the velocity only. Another important feature is that the approximations of the velocity, pressure, and gradient converge with the optimal order of k+1 in the L2-norm, when polynomials of degree k⩾0 are used to represent the approximate variables. Based on the optimal convergence of the HDG method, we apply an element-by-element postprocessing scheme to obtain a new approximate velocity, which converges with order k+2 in the L2-norm for k⩾1. The postprocessing performed at the element level is less expensive than the solution procedure. Numerical results are provided to assess the performance of the method. - 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
- Apr 2006
- MATH COMPUT

We devise and analyze a new local discontinuous Galerkin (LDG) method for the Stokes equations of incompressible fluid flow. This optimally convergent method is obtained by using an LDG method to discretize a vorticity-velocity formulation of Stokes equations and by applying a new hybridization to the resulting discretization. One of the main features of the hybridized method is that it provides a globally divergence-free approximate velocity without having to construct globally divergence-free finite-dimensional spaces; only elementwise divergence-free basis functions are used. Another important feature is that it has significantly less degrees of freedom than all other LDG methods in the current literature; in particular, the approximation to the pressure is only defined on the faces of the elements. On the other hand, we show that, as expected, the condition number of the Schur-complement matrix for this approximate pressure is of order h -2 in the mesh size h. Finally, we present numerical experiments that confirm the sharpness of our theoretical a priori error estimates. - ArticleFull-text available
- Apr 2011

Seismic data are routinely used to infer in situ properties of earth materials on many scales, ranging from global studies to investigations of surficial geological formations. While inversion and imaging algorithms utilizing these data have improved steadily, there are remaining challenges that make detailed measurements of the properties of some geologic materials very difficult. For example, the determination of the concentration and orientation of fracture systems is prohibitively expensive to simulate on the fine grid and, thus, some type of coarse-grid simulations are needed. In this paper, we describe a new multiscale finite element algorithm for simulating seismic wave propagation in heterogeneous media. This method solves the wave equation on a coarse grid using multiscale basis functions and a global coupling mechanism to relate information between fine and coarse grids. Using a mixed formulation of the wave equation and staggered discontinuous basis functions, the proposed multiscale methods have the following properties. • The total wave energy is conserved. • Mass matrix is diagonal on a coarse grid and explicit energy-preserving time discretization does not require solving a linear system at each time step. • Multiscale basis functions can accurately capture the subgrid variations of the solution and the time stepping is performed on a coarse grid. We discuss various subgrid capturing mechanisms and present some preliminary numerical results. - Article
- Jan 2005
- SIAM J NUMER ANAL

RESUMEN RESUMEN We will consider both explicit and implicit fully discrete finite volume schemes for solving three-dimensional Maxwell's equations with discontinuous physical coefficients on general polyhedral domains. Stability and convergence for both schemes are analyzed. We prove that the schemes are second order accurate in time. Both schemes are proved to be first order accurate in space for the Voronoi -- Delaunay grids and second order accurate for nonuniform rectangular grids. We also derive explicit expressions for the dependence on the physical parameters in all estimates. - 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.
- In this paper, we analyze a recently d evelopedfinite volume methodfor the time- dependent Maxwell's equations in a three-dimensional polyhedral domain composed of two dielectric materials with different parameter values for the electric permittivity and the magnetic permeability. Convergence anderror estimates of the numerical scheme are establishedfor general nonuniform tetrahedral triangulations of the physical domain. In the case of nonuniform rectangular grids, the scheme converges with second order accuracy in the discrete L2-norm, despite the low regularity of the true solution over the entire domain. In particular, the finite volume method is shown to be superconvergent in the discrete H(curl; Ω)-norm. In addition, the explicit dependence of the error estimates on the material parameters is given.
- Article
- May 2011
- MATH COMPUT

In this paper, we analyze a hybridizable discontinuous Galerkin method for numerically solving the Stokes equations. The method uses polynomials of degree k for all the components of the approximate solution of the gradient-velocity-pressure formulation. The novelty of the analysis is the use of a new projection tailored to the very structure of the numerical traces of the method. It renders the analysis of the projection of the errors very concise and allows us to see that the projection of the error in the velocity superconverges. As a consequence, we prove that the approximations of the velocity gradient, the velocity and the pressure converge with the optimal order of convergence of k+1 in L(2) for any k >= 0. Moreover, taking advantage of the superconvergence properties of the velocity, we introduce a new element-by-element postprocessing to obtain a new velocity approximation which is exactly divergence-free, H(div)-conforming, and converges with order k + 2 for k >= 1 and with order 1 for k = 0. Numerical experiments are presented which validate the theoretical results. - We introduce a unifying framework for hybridization of finite element methods for second order elliptic problems. The methods fitting in the framework are a general class of mixed-dual finite element methods including hybridized mixed, continuous Galerkin, nonconforming, and a new, wide class of hybridizable discontinuous Galerkin methods. The distinctive feature of the methods in this framework is that the only globally coupled degrees of freedom are those of an approximation of the solution defined only on the boundaries of the elements. Since the associated matrix is sparse, symmetric, and positive definite, these methods can be efficiently implemented. Moreover, the framework allows, in a single implementation, the use of different methods in different elements or subdomains of the computational domain, which are then automatically coupled. Finally, the framework brings about a new point of view, thanks to which it is possible to see how to devise novel methods displaying very localized and simple mortaring techniques, as well as methods permitting an even further reduction of the number of globally coupled degrees of freedom.
- Article
- Oct 2000
- Numer Lin Algebra Appl

We blend dual and primal domain decomposition approaches to construct a fast iterative method for the solution of large-scale systems of equations arising from the finite element discretization of second- and fourth-order partial differential equations. We show numerically that our method is scalable with respect to the mesh size, the subdomain size, and the number of elements per subdomain. We apply it to the solution of several realistic structural mechanics problems, and report on parallel performance results obtained on an Origin 2000 system, as well as the ASCI Option Red supercomputer. - 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. - 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.