You can only exceed your limits if you’ve discovered them.

― Roel van Sleeuwen

About 15 years ago I wrote a simple paper with Len Margolin about options for modifying limiters used in high resolution schemes. Generally the paper didn’t get the success it deserved like so much else. It was studied by folks at Brown University, and was repurposed as a general positivity limiter. I will grant that the researchers at Brown did some really good work with the limiter especially proving how it could preserve accuracy (the positivity preserving limiter also preserves the design accuracy of the original reconstruction). I returned to this form in one of my recent papers, “Reconsidering Remap Methods” published earlier this year and the topic of a number of blog posts. Last week I realized that even more can be done with it and the form is really convenient for expressing a wide variety of nonlinear stability mechanisms in a more uniform manner.

The moment that crystalized my thinking was a re-reading and analysis of a limiter devised my Phil Colella and Michael Sekora for the PPM algorithm. This limiter was a “competitor” to an entirely different “limiting” strategy that I worked with Jeff Greenough and Jim Kamm. I now realized that the two limiters could be written in very nearly identical ways. Moreover, both of these ideas can be viewed as rather direct decedents of work by HT Huynh and Suresh from the late 1990’s. Each method attempts to extend nonlinear stability ideas beyond simply preserving monotonicity, to preserving valid extrema in solutions. Monontonicity preservation has the problem of seriously damping extrema with the limiter. All of these limiters can be expressed as different choices for a common form allowing direct comparison or mix and match ideas to be utilized effectively.

So, what is this common form?

Given a polynomial (or more general functions perhaps) representation of a solution in a computational cell, $p\left(\theta\right)$ where $\theta = \left(x-x_j\right)/\Delta x$, the limiter is implemented as $\tilde{p}\left(\theta\right) = u_j + \phi \left(\delta p_j \right)$, $\phi$ is the general limiter and $u_j + \delta p_j = p\left(\theta\right)$. The limiter has a general form, $\phi = \min\left(1, \frac{\mbox{Standard}}{\mbox{Reconstruction Choice}}\right)$. The “Standard” is the test that defines the nonlinear control of the solution while “Reconstruction Choice” is the feature being controlled. I will give some examples below. It is important to note that $p\left(\theta\right) = u_j$ is the reconstruction that produces an upwind scheme that is the canonical linear monotonicity preserving (positive) method, but only first-order accurate. Higher order polynomials can be defined for higher accuracy, but without the limiter they are invariably oscillatory.

The most common choice is the definition of a positivity preserving limiter. In this case $\mbox{Standard} = u_j-u_{min}$ where $u_{min}$ is the lowest value of $u$ that will be tolerated for physical reasons. Next our reconstruction is interrogated $\mbox{Reconstruction Choice} = u_j -\min\left[p\left(\theta\right)\right]$.

The same can be done for monotonicity-preserving limiters. Here the most common application is “slope-limiting” where a common choice is $\mbox{Standard} = 2 \min\mod\left(\Delta_{j-1/2} u,\Delta_{j+1/2} u\right)$ here $\min\mod$ is the famous minimum modulus function that returns the smallest magnitude argument if the arguments have the same sign. $\mbox{Reconstruction Choice} = s_j$ where $s_j$ is the “high-order” slope that you desire to use and control the stability of.

For extrema preservation I will provide a couple of choices from my own work and Colella & Sekora. In both cases the extrema preservation will only be applied if a local extrema is detected by the scheme. Generally speaking a monotonicity preserving limiter will help do this by setting $p\left(\theta\right) = u_j$.

The idea that I worked on had a couple of key concepts: don’t give up on the original high-order scheme yet, at an extrema a ENO or WENO scheme might be useful, and the monotonicity preserving method has good nonlinear stability properties. My limiter worked on edge values that then helped define the reconstruction polynomial. It turns out that the general limiter can work here too, $\tilde{u}_{j+1/2} = u_j + \phi \delta u_{j+1/2}$, $\delta u_{j+1/2} = u_{j+1/2} - u_j$ and everything else follows. The parts of the limiter are $\mbox{Standard} = \mbox{median}\left( u_{j+1/2}^{MP} -u_j, u_{j+1/2}^{HO}-u_j, u_{j+1/2}^{WENO} -u_j \right)$ with $u_{j+1/2}^{MP}$ being the monotonicity preserving edge value, $u_{j+1/2}^{HO}$ is the high-order edge values and $u_{j+1/2}^{WENO}$ is the WENO edge value. Next, the limiter is completed with $\mbox{Reconstruction Choice} = \delta u_{j+1/2}^{HO}$. Part of the key idea is to use two complimentary nonlinear stability properties from monotonicity preservation and WENO to assure the stability of the method should the high-order method be chosen. In this case the high-order method is bounded by two nonlinearly stable approximation choices. I thought it actually worked pretty well.

Colella and Sekora had a different approach based on looking at the local curvature (second derivative) of the parabolic reconstruction used in PPM. If the second derivatives of the reconstruction and the neighborhood of the reconstruction all have the same sign and roughly the same magnitude, the extrema is viewed as valid and worth propagating undistorted by the sort of damping monotonicity preserving methods produce. A simple way to implement this approach can be implemented using the general limiter I discuss. First we need to define the second derivative of the polynomial reconstruction $\delta_2 p= \partial_{\theta\theta} p\left( \theta \right)$. In this case the specifics of the limiter are $\mbox{Standard} = \min\mod\left(\delta_2 p, C \Delta^2_j u, C \Delta^2_{j-1} u, C \Delta^2_{j+1} u,\right)$ where $\Delta^2_j u$ is the classical second derivative on the mesh and $C \ge 1$. The choice of method to define the denominator in the limiter is $\mbox{Reconstruction Choice} = \delta_2 p$. The resulting limiter can either be applied to the edge values or equivalently to the reconstructing polynomial.

In my next post I will talk about how edge values, $u_{j+1/2}$ can be used productively to improve the robustness, resolution and stability of these methods.

Set Goals, not Limits.

― Manoj Vaz

Rider, William J., and Len G. Margolin. “Simple modifications of monotonicity-preserving limiter.” Journal of Computational Physics 174.1 (2001): 473-488.

Qiu, Jianxian, and Chi-Wang Shu. “A Comparison of Troubled-Cell Indicators for Runge–Kutta Discontinuous Galerkin Methods Using Weighted Essentially Nonoscillatory Limiters.” SIAM Journal on Scientific Computing 27.3 (2005): 995-1013.

Zhang, Xiangxiong, and Chi-Wang Shu. “Maximum-principle-satisfying and positivity-preserving high-order schemes for conservation laws: survey and new developments.” Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences. The Royal Society, 2011.

Zhang, Xiangxiong, and Chi-Wang Shu. “On maximum-principle-satisfying high order schemes for scalar conservation laws.” Journal of Computational Physics229.9 (2010): 3091-3120.

Colella, Phillip, and Michael D. Sekora. “A limiter for PPM that preserves accuracy at smooth extrema.” Journal of Computational Physics 227.15 (2008): 7069-7076.

Suresh, A., and H. T. Huynh. “Accurate monotonicity-preserving schemes with Runge–Kutta time stepping.” Journal of Computational Physics 136.1 (1997): 83-99.

Huynh, Hung T. “Accurate upwind methods for the Euler equations.” SIAM Journal on Numerical Analysis 32.5 (1995): 1565-1619.

Rider, William J., Jeffrey A. Greenough, and James R. Kamm. “Accurate monotonicity-and extrema-preserving methods through adaptive nonlinear hybridizations.” Journal of Computational Physics 225.2 (2007): 1827-1848.