Skip to main content

Theory of Summation By Parts Finite Differences

Computational Aero-Acoustics (CAA) simulation results from ECMI.

Computational Aero-Acoustics (CAA) involves using computer simulations to model sound generated by and propagating through air flows. Applications range from hand driers and computer cooling fans to aircraft engines and wind turbines. These simulations push the limits of modern computers, and are (or should be) perfectly balanced between being too dissipative and being unstable. The simulations therefore rely on a significant body of mathematical theory. This project concerns recent developments in the theory of finite differences, commonly used in computational aero-acoustics simulations.

Video of some Computational Aero-Acoustics simulations by Exa.

Summation By Parts (SBP) dates from 1993, and is a clever way to require finite difference simulations to be provably stable. It works by mimicking integration by parts (IBP). See below for (brief) details. Most physical systems are provably stable, as they have some conserved quantities (such as Energy, for example) which give a bound on the growth rate of any instabilities. The proof involves rearranging the governing equations using Integration By Parts to form a governing equation for the conserved quantity. For a Summation By Parts finite difference scheme, the same proof shows that the numerical discretized solution is also stable, and that it too supports some sort of exactly conserved quantity.

What is not obvious is how to find such a finite difference derivative operator, together with its metric. Most publications simply use brute force algebra on the components of matrices representing them. In this project, we will look at whether there is some deeper theory behind such derivative schemes, using ideas from Functional Analysis and Approximation Theory, informed and motivated by some of the underlying theory behind Finite Element simulations.

This project has very few if any pre-requisites. Knowledge of any of the following might be helpful, but could be learnt during the project if needed:

  • Linear Algebra.
  • Functional Analysis and Approximation Theory.
  • Solutions to linear wave equations.
  • The theory behind Finite Difference calculations.
  • Some theory behind Finite Element simulations.

Brief mathematical details

For integration by parts, we know that $$ \left\langle f, \frac{\mathrm{d}g}{\mathrm{d}x}\right\rangle = \big[f(x)g(x)\big]_a^b - \left\langle g, \frac{\mathrm{d}f}{\mathrm{d}x}\right\rangle, \qquad\qquad\text{where}\qquad \langle f,g\rangle = \int_a^bf(x)g(x)\,\mathrm{d}x,$$ and the angle brackets give a (real) inner product. In finite differences, we discretize a function \(f(x)\) by \(f_j = f(x_j)\) for \(j=0,\ldots, N\) with \(x_0 = a\) and \(x_N = b\). Summation by parts may then be defined similarly as $$ \big\langle \mathbf{f}, \mathsf{D}\mathbf{g}\big\rangle_\mathsf{P} = \big[f_Ng_N - f_0g_0] - \big\langle \mathbf{g}, \mathsf{D}\mathbf{f}\big\rangle_\mathsf{P}, \qquad\qquad\text{where}\qquad \langle \mathbf{f},\mathbf{g}\rangle_\mathsf{P} = \mathbf{f}^T\mathsf{P}\mathbf{g},$$ \(\mathbf{f} = (f_0,\ldots,f_N)^T\) is a vector of values of the function \(f\) in the interval \([a,b]\), \(\mathsf{P}\) is a symmetric, positive definite matrix defining the inner product, and \(\mathsf{D}\) is the finite difference differentiation operator. Typically we also specify an accuracy requirement, of the form $$ \max_{0\leq j\leq N}\left|(\mathsf{D}f)_j - \frac{\mathrm{d}f}{\mathrm{d}x}(x_j)\right| = O\big(N^{-d}\big) \qquad\qquad\text{as}\qquad N \to \infty,$$ for some order of accuracy \(d\).

In the finite element context, we would instead decide on some basis functions \(\psi_j(x)\). Without loss of generality, let us assume that these are interpolating, so that \(\psi_j(x_k) = \delta_{jk}\). Then we may approximate \(f(x)\) by $$f^N(x) = \sum_{j=0}^N f_j\psi_j(x), \qquad\qquad\text{where}\qquad f_j = f(x_j).$$ In this case, defining \(\mathsf{P}\) and \(\mathsf{D}\) such that $$\mathsf{P}_{jk} = \int_a^b \psi_j(x)\psi_k(x)\,\mathrm{d}x \qquad\quad\text{and}\qquad\quad (\mathsf{PD})_{jk} = \int_a^b\psi_j(x)\frac{\mathrm{d}\psi_k}{\mathrm{d}x}(x)\,\mathrm{d}x$$ gives a Summation By Parts scheme (but of unknown order). The derivative \(\mathsf{D}f^N\) can be shown to correspond to the orthogonal projection of the derivative \(\mathrm{d}f^N/\mathrm{d}x\) into the space spanned by the \(\psi_j\) basis functions.

This project aims to investigate this connection between summation by parts finite differences and finite elements.