Publications

Publications / Conference

A new algorithm for computing multivariate Gauss-like quadrature points

Taylor, Mark A.

The diagonal-mass-matrix spectral element method has proven very successful in geophysical applications dominated by wave propagation. For these problems, the ability to run fully explicit time stepping schemes at relatively high order makes the method more competitive then finite element methods which require the inversion of a mass matrix. The method relies on Gauss-Lobatto points to be successful, since the grid points used are required to produce well conditioned polynomial interpolants, and be high quality 'Gauss-like' quadrature points that exactly integrate a space of polynomials of higher dimension than the number of quadrature points. These two requirements have traditionally limited the diagonal-mass-matrix spectral element method to use square or quadrilateral elements, where tensor products of Gauss-Lobatto points can be used. In non-tensor product domains such as the triangle, both optimal interpolation points and Gauss-like quadrature points are difficult to construct and there are few analytic results. To extend the diagonal-mass-matrix spectral element method to (for example) triangular elements, one must find appropriate points numerically. One successful approach has been to perform numerical searches for high quality interpolation points, as measured by the Lebesgue constant (Such as minimum energy electrostatic points and Fekete points). However, these points typically do not have any Gauss-like quadrature properties. In this work, we describe a new numerical method to look for Gauss-like quadrature points in the triangle, based on a previous algorithm for computing Fekete points. Performing a brute force search for such points is extremely difficult. A common strategy to increase the numerical efficiency of these searches is to reduce the number of unknowns by imposing symmetry conditions on the quadrature points. Motivated by spectral element methods, we propose a different way to reduce the number of unknowns: We look for quadrature formula that have the same number of points as the number of basis functions used in the spectral element method's transform algorithm. This is an important requirement if they are to be used in a diagonal-mass-matrix spectral element method. This restriction allows for the construction of cardinal functions (Lagrange interpolating polynomials). The ability to construct cardinal functions leads to a remarkable expression relating the variation in the quadrature weights to the variation in the quadrature points. This relation in turn leads to an analytical expression for the gradient of the quadrature error with respect to the quadrature points. Thus the quadrature weights have been completely removed from the optimization problem, and we can implement an exact steepest descent algorithm for driving the quadrature error to zero. Results from the algorithm will be presented for the triangle and the sphere.