Efficient Implementation of Smoothness-Increasing Accuracy-Conserving (SIAC) Filters for Discontinuous Galerkin Solutions

The discontinuous Galerkin (DG) methods provide a high-order extension of the finite volume method in much the same way as high-order or spectral/hp elements extend standard finite elements. However, lack of inter-element continuity is often contrary to the smoothness assumptions upon which many post-processing algorithms such as those used in visualization are based. Smoothness-increasing accuracy-conserving (SIAC) filters were proposed as a means of ameliorating the challenges introduced by the lack of regularity at element interfaces by eliminating the discontinuity between elements in a way that is consistent with the DG methodology; in particular, high-order accuracy is preserved and in many cases increased. The goal of this paper is to explicitly define the steps to efficient computation of this filtering technique as applied to both structured triangular and quadrilateral meshes. Furthermore, as the SIAC filter is a good candidate for parallelization, we provide, for the first time, results that confirm anticipated performance scaling when parallelized on a shared-memory multi-processor machine.     

Smoothness-Increasing Accuracy-Conserving (SIAC) Filtering for Discontinuous Galerkin Solutions: Improved Errors Versus Higher-Order Accuracy

Smoothness-increasing accuracy-conserving (SIAC) filtering has demonstrated its effectiveness in raising the convergence rate of discontinuous Galerkin solutions from order $k+\frac{1}{2}$ to order 2k+1 for specific types of translation invariant meshes (Cockburn et al. in Math. Comput. 72:577?C606, 2003; Curtis et al. in SIAM J. Sci. Comput. 30(1):272?C289, 2007; Mirzaee et al. in SIAM J. Numer. Anal. 49:1899?C1920, 2011). Additionally, it improves the weak continuity in the discontinuous Galerkin method to k?1 continuity. Typically this improvement has a positive impact on the error quantity in the sense that it also reduces the absolute errors. However, not enough emphasis has been placed on the difference between superconvergent accuracy and improved errors. This distinction is particularly important when it comes to understanding the interplay introduced through meshing, between geometry and filtering. The underlying mesh over which the DG solution is built is important because the tool used in SIAC filtering??convolution??is scaled by the geometric mesh size. This heavily contributes to the effectiveness of the post-processor. In this paper, we present a study of this mesh scaling and how it factors into the theoretical errors. To accomplish the large volume of post-processing necessary for this study, commodity streaming multiprocessors were used; we demonstrate for structured meshes up to a 50× speed up in the computational time over traditional CPU implementations of the SIAC filter.     

One-Sided Smoothness-Increasing Accuracy-Conserving Filtering for Enhanced Streamline Integration through Discontinuous Fields

The discontinuous Galerkin (DG) method continues to maintain heightened levels of interest within the simulation community because of the discretization flexibility it provides. One of the fundamental properties of the DG methodology and arguably its most powerful property is the ability to combine high-order discretizations on an inter-element level while allowing discontinuities between elements. This flexibility, however, generates a plethora of difficulties when one attempts to use DG fields for feature extraction and visualization, as most post-processing schemes are not designed for handling explicitly discontinuous fields. This work introduces a new method of applying smoothness-increasing, accuracy-conserving filtering on discontinuous Galerkin vector fields for the purpose of enhancing streamline integration. The filtering discussed in this paper enhances the smoothness of the field and eliminates the discontinuity between elements, thus resulting in more accurate streamlines. Furthermore, as a means of minimizing the computational cost of the method, the filtering is done in a one-dimensional manner along the streamline.     

Fast Numerical Integration on Polytopic Meshes with Applications to Discontinuous Galerkin Finite Element Methods

In this paper we present efficient quadrature rules for the numerical approximation of integrals of polynomial functions over general polygonal/polyhedral elements that do not require an explicit construction of a sub-tessellation into triangular/tetrahedral elements. The method is based on successive application of Stokes’ theorem; thereby, the underlying integral may be evaluated using only the values of the integrand and its derivatives at the vertices of the polytopic domain, and hence leads to an exact cubature rule whose quadrature points are the vertices of the polytope. We demonstrate the capabilities of the proposed approach by efficiently computing the stiffness and mass matrices arising from hp-version symmetric interior penalty discontinuous Galerkin discretizations of second-order elliptic partial differential equations.     

Positivity-Preserving Well-Balanced Discontinuous Galerkin Methods for the Shallow Water Equations on Unstructured Triangular Meshes

The shallow water equations model flows in rivers and coastal areas and have wide applications in ocean, hydraulic engineering, and atmospheric modeling. In “Xing et al. Adv. Water Resourc. 33: 1476–1493, 2010)”, the authors constructed high order discontinuous Galerkin methods for the shallow water equations which can maintain the still water steady state exactly, and at the same time can preserve the non-negativity of the water height without loss of mass conservation. In this paper, we explore the extension of these methods on unstructured triangular meshes. The simple positivity-preserving limiter is reformulated, and we prove that the resulting scheme guarantees the positivity of the water depth. Extensive numerical examples are provided to verify the positivity-preserving property, well-balanced property, high-order accuracy, and good resolution for smooth and discontinuous solutions.     

Discontinuous Galerkin Methods for Second-Order Elliptic PDE with Low-Regularity Solutions

In this paper we derive an a priori error analysis for interior penalty discontinuous Galerkin finite element discretizations of the Poisson equation with exact solution in W ^2,p , p∈(1,2]. We show that the DGFEM converges at an optimal algebraic rate with respect to the number of degrees of freedom.     

Performance and Scalability Improvements for Discontinuous Galerkin Solutions to Conservation Laws on Unstructured Grids

This paper presents a computational framework developed to improve both the serial and parallel performance of two dimensional, unstructured, discontinuous Galerkin (DG) solutions to hyperbolic conservation laws. The coding techniques employed factor in advancements trending in HPC technologies. They are designed to maximize loop vectorization, efficiently utilize cache, facilitate straightforward shared memory parallelization, reduce message passing volume, and increase the overlap between computation and communication. With today’s CPU technology and HPC networks rapidly evolving, it is important to quantitatively assess and compare these methodologies with standard paradigms in order to maximize current computational resources. In our benchmark studies, we specifically investigate the shallow water equations to show that the refactored algorithm implementation is able to provide a significant performance increase over the conventional elemental DG code structure in terms of both CPU time and parallel scalability. Our results show that the serial optimizations result in a 28–38 % performance increase. For parallel computations our improvements give rise to a 1.5–2.0 speedup factor for local problem sizes between 10 and 2000 elements per core, regardless of the overall problem size. The computational benchmarks were performed on the Lonestar and Stampede supercomputers at the Texas Advanced Computing Center.     

Optimal Error Estimates of the Local Discontinuous Galerkin Method for Surface Diffusion of Graphs on Cartesian Meshes

In (Xu and Shu in J. Sci. Comput. 40:375–390, 2009), a local discontinuous Galerkin (LDG) method for the surface diffusion of graphs was developed and a rigorous proof for its energy stability was given. Numerical simulation results showed the optimal order of accuracy. In this subsequent paper, we concentrate on analyzing a priori error estimates of the LDG method for the surface diffusion of graphs. The main achievement is the derivation of the optimal convergence rate k+1 in the L ² norm in one-dimension as well as in multi-dimensions for Cartesian meshes using a completely discontinuous piecewise polynomial space with degree k≥1.     

Hybridized Discontinuous Galerkin Method for Elliptic Interface Problems: Error Estimates Under Low Regularity Assumptions of Solutions

New hybridized discontinuous Galerkin (HDG) methods for the interface problem for elliptic equations are proposed. Unknown functions of our schemes are \(u_h\) in elements and \(\hat{u}_h\) on inter-element edges. That is, we formulate our schemes without introducing the flux variable. We assume that subdomains \(\Omega _1\) and \(\Omega _2\) are polyhedral domains and that the interface \(\Gamma =\partial \Omega _1\cap \partial \Omega _2\) is polyhedral surface or polygon. Moreover, \(\Gamma \) is assumed to be expressed as the union of edges of some elements. We deal with the case where the interface is transversely connected with the boundary of the whole domain \(\overline{\Omega }=\overline{\Omega _1\cap \Omega _2}\). Consequently, the solution u of the interface problem may not have a sufficient regularity, say \(u\in H^2(\Omega )\) or \(u|_{\Omega _1}\in H^2(\Omega _1)\), \(u|_{\Omega _2}\in H^2(\Omega _2)\). We succeed in deriving optimal order error estimates in an HDG norm and the \(L^2\) norm under low regularity assumptions of solutions, say \(u|_{\Omega _1}\in H^{1+s}(\Omega _1)\) and \(u|_{\Omega _2}\in H^{1+s}(\Omega _2)\) for some \(s\in (1/2,1]\), where \(H^{1+s}\) denotes the fractional order Sobolev space. Numerical examples to validate our results are also presented.     

A Review of Element-Based Galerkin Methods for Numerical Weather Prediction: Finite Elements,Spectral Elements,and Discontinuous Galerkin

Numerical weather prediction (NWP) is in a period of transition. As resolutions increase, global models are moving towards fully nonhydrostatic dynamical cores, with the local and global models using the same governing equations; therefore we have reached a point where it will be necessary to use a single model for both applications. The new dynamical cores at the heart of these unified models are designed to scale efficiently on clusters with hundreds of thousands or even millions of CPU cores and GPUs. Operational and research NWP codes currently use a wide range of numerical methods: finite differences, spectral transform, finite volumes and, increasingly, finite/spectral elements and discontinuous Galerkin, which constitute element-based Galerkin (EBG) methods. Due to their important role in this transition, will EBGs be the dominant power behind NWP in the next 10 years, or will they just be one of many methods to choose from? One decade after the review of numerical methods for atmospheric modeling by Steppeler et al. (Meteorol Atmos Phys 82:287–301, 2003), this review discusses EBG methods as a viable numerical approach for the next-generation NWP models. One well-known weakness of EBG methods is the generation of unphysical oscillations in advection-dominated flows; special attention is hence devoted to dissipation-based stabilization methods. Since EBGs are geometrically flexible and allow both conforming and non-conforming meshes, as well as grid adaptivity, this review is concluded with a short overview of how mesh generation and dynamic mesh refinement are becoming as important for atmospheric modeling as they have been for engineering applications for many years.     

Exploiting Batch Processing on Streaming Architectures to Solve 2D Elliptic Finite Element Problems: A Hybridized Discontinuous Galerkin (HDG) Case Study

Numerical methods for elliptic partial differential equations (PDEs) within both continuous and hybridized discontinuous Galerkin (HDG) frameworks share the same general structure: local (elemental) matrix generation followed by a global linear system assembly and solve. The lack of inter-element communication and easily parallelizable nature of the local matrix generation stage coupled with the parallelization techniques developed for the linear system solvers make a numerical scheme for elliptic PDEs a good candidate for implementation on streaming architectures such as modern graphical processing units (GPUs). We propose an algorithmic pipeline for mapping an elliptic finite element method to the GPU and perform a case study for a particular method within the HDG framework. This study provides comparison between CPU and GPU implementations of the method as well as highlights certain performance-crucial implementation details. The choice of the HDG method for the case study was dictated by the computationally-heavy local matrix generation stage as well as the reduced trace-based communication pattern, which together make the method amenable to the fine-grained parallelism of GPUs. We demonstrate that the HDG method is well-suited for GPU implementation, obtaining total speedups on the order of 30–35 times over a serial CPU implementation for moderately sized problems.     

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

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

Object-oriented Analysis with Structured and Integrated Specifications and Solutions (OASISS) for production system control

Tool specification for production system control requires the identification of the main characteristics of the production system. The production systems are varied, and the production control tools (such as scheduling algorithms and resource assignment rules) are often dedicated to only one class of these systems. Tool assessment for production system control requires modelling of the production system. We propose a new approach to production systems, to identify the nature and the complexity of the system according to the classification of Conway et al., and to specify a dynamic model that will allow us to simulate production control decisions. This paper presents this object-oriented approach, which identifies the resources and the organization features of the studied system. It then, proposes some predetermined classes of objects, which enable us to classify the system components and to use pre-existing dynamic models. These dynamic models are based on timed and coloured Petri nets. The overall architecture of our methodology follows three steps: top-down analysis of resources and bottom-up recognition of predetermined objects, instantiation and integration of objects, and implementation of objects. An example illustrates its use in the textile industry.     

L2(H1 Norm A PosterioriError Estimation for Discontinuous Galerkin Approximations of Reactive Transport Problems

Explicita posteriori residual type error estimators in L²(H¹) norm are derived for discontinuous Galerkin (DG) methods applied to transport in porous media with general kinetic reactions. They are flexible and apply to all the four primal DG schemes, namely, Oden–Babuška–Baumann DG (OBB-DG), non-symmetric interior penalty Galerkin (NIPG), symmetric interior penalty Galerkin (SIPG) and incomplete interior penalty Galerkin (IIPG). The error estimators use directly all the available information from the numerical solution and can be computed efficiently. Numerical examples are presented to demonstrate the efficiency and the effectivity of these theoretical estimators.The authors would like to thank the anonymous referees for their incisive suggestions which contributed toward improving the paper. AMS subject classifications:65M15;65M60;65M50.This revised version was published online in July 2005 with corrected volume and issue numbers.