Discontinous Galerkin: a breed of Finite Element, of Finite Volume, of both, or of neither?

If you google “Discontinous Galerkin“, you got 120,000 results. If you continue to read, you will be confused by the way people refer to this method: Discontinuous Galerkin Method (DGM), Discontinuous Galerkin (DG), Discontinuous Galerkin Finite Element Method (DG-FEM), Discontinuous Galerkin Finite Volume Element method, Discontinuous Galerkin Spectral Element Method (DG-SEM), etc.  So indeed what is the breed of discontinuous Galerkin, Finite Element (FE), or Finite Volume (FV)? Is it a stand-alone method in parallel with FE, FV, Spectral Method, Spectral Element Method, Continuous Galerkin Method? Confused even worse! This blog is to provide my point of view on discontinuous Galerkin method in the hope that it may clarify (or unify) various names in the literature.

First we start from Partial Differentiation Equations (PDFs), which are mathematical models for physical problems. For example, hyperbolic PDF can describe a wave propagation problem, elliptical PDF for a steady state heat distribution problem, ect. There are primarily three big (numerical) families to solve these PDFs: Finite Difference (FD), FE and FV (Wikipedia gives more). FD makes use of Taylor series and approximate the derivatives by difference; If Δx is the grid interval for all grid, FD can achieve 2~4 order of accuracy (O(Δx^2)~O(Δx^4)) easily. For higher accuracy, larger stencil is needed which may smear spatial properties. FD can also be formulated by Lagrange polynomial interpolation (e.g.,order of 2) on regular grid.

Inspired by this, FE was formulated, i.e.,  u(x,t)=∑u_i(t)N_i(x),   (1)   where N_i(x) is called shape function. Note that if N_i(x) is defined in the whole computation domain, this is called spectral method. In classical FE, N_i(x) is supported by two ending point of each element; thus N_i(x) is a linear function of x. Usually (1) is substituted into a weak form of PDFs (weighted residual), and the boundary conditions can be honored naturally. Note here that in the weighted residual method, if the testing function is identical to the shape function, it is called Galerkin projection. If all elements are assembled in a way to force the continuity across element, this is called continuous Galerkin method, otherwise discontinuous Galerkin method.

FV is also formulated on the weak form of PDFs. In contrast to FD, FE, the unknowns are not values at grid points but averaged value within the control volume (e.g., xi-1/2~xi+1/2 around grid xi). If values at the boundary of control volume are needed, they must be estimated by the averaged values and the estimated values are called numerical trace, or numerical flux. If the testing function in FE equals one in one element, FE becomes FV with minor difference between control volume and element mesh.

Now you see the tricks of FD, FE, and FV in solving PDFs are to discretize the model into segments each having typical scale h=Δx. The smaller the h is, the more accurate the result is. Thus they are called h-type method. Among three of them, FE allows another type of method, p-type method, i.e., by increasing the order of the shape function to increase the accuracy of the solution. This idea is termed Spectral Element Method (SEM) in fluid dynamics and p-FEM in structure mechanics. So hp-FEM is a type of FE with dual path of increasing accuracy, i.e., increasing polynomial order (p)  and decreasing element size (h). No wonder you read “SEM is a type of hp-FEM method”, since SEM = p-FEM. But SEM and p-FEM can have minor differences. For example, methods called SEM usually use Lagrange polynomials, or Chebychev polynomials. People who use other polynomials (hierarchy ones), such as Legendre, or modified Legendre basis may call their method p-FEM. The book titled “Spectral/hp Element Methods for CFD”, at the first glance coining another method, was actually trying to unite the readers who are using the same technique but under different names. Indeed, using different type of shape function in the framework of FE should NOT mean different type of technology. Either nodal basis or modal basis, they share the same family name and calling them Spectral/hp Element Method seems a fair idea. I like it.

What about discontinuous Galerkin? As mentioned in the section of FE, continuous and discontinuous Galerkin are two ways of assembling elements in the family of FE. CG obviously has much less freedom than DG thus less computation but less flexibility too. The dramatic difference renders it worthwhile to mention it in the name. Therefore people use discontinuous Galerkin call their method  DG-FEM.  DG requires extra function to communicate information among element boundary nodes, which was initially developed in FV. No wonder Wikipedia puts:”(CG) combine features of the finite element and the finite volume framework“. Therefore people may call their method using numerical flux Discontinuous Galerkin Finite Volume Element method. But you don’t need to name a method with all techniques involved, just like you don’t name a dish with all ingredients. Considering CG and DG are two different ways of combining elements under the umbrella of FE, and DG is relatively new comparing to CG, I think it might be fair to call CG based FE or hp-FEM Spectral/hp Element Method (i.e., CG by default) and call DG based FE or hp-FEM Discontinuous Galerkin Method (DGM), just not to against the convention in contemporary literature. But one should know that DGM can use a wide range of polynomial orders. P=0, DGM=FV; P=1, DGM=DG-FEM; P>=2, DGM=DG based hp-type FEM. If you are unsure how to name your new method, follow this checklist: (1) FD, FE, or FV? Take one into the name; (2) low order or high order? If low order, do nothing; if high order, take “spectral” in your name (3) CG or DG? Take one into the name. That’s it.

For now, I am developing a high order finite element method using discontinuous Galerkin method. Thus I can name it: Discontinuous Galerkin Spectral/hp Element Method, or DG based Spectral/hp element method, or DG-SEM, or DG-hpFEM, ect. Anyway, you know what I am talking about, so you name it!

by Junwei, first created on 12:10pm EDT, Oct 20 2010.

High Performance Travel Time Tomography Based on the Fast Sweeping Method and Adjoint-state Technique


In this paper, we present a program, PATT (Parallel Arrival Time Tomography), to perform transmission and/or reflection travel time tomography based on adjoint-state technique and Fast Sweeping Method (FSM). In contrast to classical ray based tomography algorithm, this algorithm utilizes a finite difference based Eikonal equation solver to circumvent the non-linearity of conventional ray shooting and bending approaches. The adjoint-state technique is used to obtain the gradient of the objective function without estimation of Fréchet derivative matrix, which is usually computationally prohibitive for large scale problems. Based on Huygens’ Principle, we extend the capability of FSM to calculate reflection time and show that the joint tomography using both transmission and reflection time can further mitigate the non-linearity of inverse modeling and reveal deeper features not visible to transmission waves.

This paper describes the theoretical basis of the algorithm, provides the details of the parallel implementation and demonstrates the scalability of the high performance program on a distributed memory system. We then evaluate the performance of transmission, reflection and joint tomography on a synthetic model and a two-dimensional (2D) seismic survey conducted in Northwest Territories of Canada where complex thermokarst lakes and heterogeneous permafrost are present in the shallow subsurface. The accuracy of travel time using FSM and the resolution of the tomographic model in the presence of white noise are analyzed in the appendices.