# Quadrature order for finite elements and time dependent discontinuous Galerkin

When setting up a finite element system you have to use quadrature to calculate the integrals. I'm having trouble understanding what order rule to use.

I know of some rules of thumb, for example with the 1D Hemholtz you end up with the matrix $M + S$, where $M_{ij} = (\phi_i, \phi_j)$ and $S_{ij} = (\phi_i', \phi_j')$. In this case if $\phi$ is a polynomial of degree $n$, then the integrals in $M$ will of degree $2n$ and the integrals in $S$ will be of degree $2(n-1)$. Using a Gauss rule of order $n$ is recommended here, which integrates $S$ exactly.

When using DG on the advection equation the "stiffness" matrix becomes $S_{ij} = (\phi_i', \phi_j)$. In this case I found that using an order $n$ Gauss quadrature rule (which should still integrate $S$ exactly) gives me a singular matrix, and that I have to use a rule of order $n+1$ to get an invertible matrix. Is there some way to know beforehand what order rule to use, or it just determined experimentally?

EDIT: As per comments below, I'm using DG with Langrangian elements on a uniform grid to solve the time dependent advection equation $u_t + au_x = 0$. I have periodic boundary conditions on the domain $[0, 2\pi]$ and the initial condition $u(x,0) = \sin(x)$.

This is my first attempt coding DG myself, so I'm using central flux and backwards Euler for the time step. Using basis functions of degree $n$ and $\Delta t = h^{n+1}$, the solutions converge to the exact solution in the $L^2$ norm as $O(h^{n+1})$.

• I'm guessing it's the quadrature because if I add the extra quadrature point the matrix is invertible and the solutions converge at the theoretical rate (at least for my simple test case). In 1D the interface terms are not integrals and are independent of the quadrature rule. – Lukas Bystricky Aug 27 '15 at 12:38
• Small aside: for the advection equation $u_x = f$, the stiffness matrix should have entries $S_{ij} = (\phi_i,\phi_j')$ (test functions correspond to rows, not columns -- this is assuming standard mathematical notation that the first index corresponds to the row). – Christian Clason Aug 27 '15 at 13:04
• On the choice of quadrature rules for DG applied to conservation laws from the point of view optimal accuracy, see this paper dx.doi.org/10.1090/S0025-5718-1990-1010597-0 – cpraveen Jun 21 '16 at 4:02

Now you can fairly easily show that the mass matrix will be positive definite if the quadrature is exact. As the product of two polynomials of order $n$ is $2n$, Gauß quadrature of order $n$ is not sufficient and you need at least order $n+1$ (as you have already noted).
The converse is not as obvious, but there's a bit of "finite element folklore" (at least in the engineering community) that each Gauß quadrature point adds $d$ (the space dimension) to the rank of the elemental mass matrix, and full rank is equal to the number of degrees of freedom in each element. In 1D, this is $n+1$, so you need $n+1$ points.
• The highest-order term is the one involving the highest occurring derivatives (such as $(\nabla \phi_i,\nabla \phi_j)$ for the second-order equation $-\Delta y +\nabla y = f$). If this term has the highest derivatives, it will have the lowest order polynomials to integrate, so this is the least restriction on the quadrature order. – Christian Clason Aug 27 '15 at 16:51