“Progress in science depends on new techniques, new discoveries and new ideas, probably in that order.” – Sydney Brenner

I’m going to revisit a paper that has a special place in my heart. It is a premature apex of a body of work terminated too early. A bit of the loss is my own fault as I moved to Sandia Labs. It was also fairly brutal to get published. It is a line of work that has potential, but the final development needs a boost. It is an investment in a stagnant area of research. There is also resistance from gatekeepers, who hold progress hostage. The important aspects of this are efficiency on realistic problems and selective preservation of extrema in the solution. The efficiency and verification aspects are progressing due to some recent effort.

I will elaborate on both below.

“You are more likely to be remembered by your expository work than by your original research.” – Gian-Carlo Rota,

Simply publishing the paper took some of the wind out of the sails of the results. This is all related to what determines the effectiveness of the method. As one might guess, this comes down to verification of results on discontinuous problems. As noted before, the accuracy of shocked problems is rarely computed in results. The results are purely judged qualitatively. Thus, fundamental beliefs and premises are not subjected to testing via quantitative verification. This is a community-wide accepted practice.

“The scientific paper in its orthodox form does embody a totally mistaken conception, even a travesty, of the nature of scientific thought.” – Peter Medawar

Accuracy is only considered quantitatively for smooth problems. In this way, one can demonstrate the formal order of accuracy. This formal order of accuracy does not determine the accuracy on problems with discontinuities. The entire field is focused on producing methods that can practically solve problems with discontinuities. These are virtually all practical applications we design the method to solve. In my view, this is an enormous community-wide gap. We only measure accuracy on problems that are immaterial to the applications.

A recipe for lack of progress!

It should come as no surprise that this is what we have got. Gatekeepers are removing progress, and “barbaric” new ideas are kept outside the walls of the high-resolution castle. The gatekeepers have ensured their legacies for now.

This gap in measurement is the central focus of this line of research. In my opinion, this is also the source of stagnation in methods’ development and progress.

To see the origin of my thinking, one needs to go back a few years. A seminal effort of my own was a collaboration with Jeff Greenough from Livermore. We studied the relative accuracy of a fifth-order weighted ENO method compared to a high-quality second-order Godunov algorithm. The knee-jerk response is that this is a futile contest. How can a second-order method compete with a fifth-order method? For smooth problems, it cannot. For problems with discontinuities, the answer is different, and the second-order method crushes WENO. This is especially true when cost is taken into account. WENO only wins in efficiency at enormous resolutions for problems replete with structure.

“Simplicity is prerequisite for reliability.” – Edsger Dijkstra

Details matter a lot in explaining this rather curious result. WENO methods typically use multistep time integration. This has two clear effects that determine most of the cost. The standard is a three-stage third-order Runge-Kutta integrator. Thus, the space discretization must be evaluated three times. The second impact is a factor of two decrease in time step size for similar CFL constraints. These two elements combine for a factor of six multiplier in cost for WENO in unit cost per mesh cell. For the most part, the spatial discretization cost is about the same per evaluation. As I will discuss later, any advantage for WENO can be eliminated by developing an adaptive method. The adaptive method in principle combines the lower-order method with WENO selectively. WENO is overly dissipative and inaccurate in monotone regions of the flow.

Another key aspect of this study is the nature of the low-order method. In the case of the piecewise linear method, the linear profile is optimally fourth-order accurate for the slope. In a similar fashion, the base PPM method uses a fourth-order edge value for each cell. In each case, monotonicity is checked and the approximation is modified if problems are found. Nonetheless, the high-order initial approximation endows the method with accuracy. This makes these methods far more competitive than a fully second-order approximation like Van Leer introduced. It is a lesson to apply going forward.

Add to this the effective accuracy of the two methods. On simple problems like Sod’s shock tube, WENO is half the accuracy of the second-order method. For the interacting blast waves, the accuracies are about the same. Finally, for the Shu-Osher problem at very late time, WENO is twice as accurate on a per-mesh-cell basis. The lesson being that WENO is only better if the problem has a great deal of structure and many extrema. To be more efficient requires extremely fine meshes. This motivates the development of a more adaptive discretization that accounts for this behavior.

“Since all models are wrong the scientist must be alert to what is importantly wrong. It is inappropriate to be concerned about mice when there are tigers abroad.” – George Box

The basic idea is to move between discretizations that are best for discontinuous solutions and those best for smooth extrema. One still needs to find and eliminate spurious oscillations. Separate these from physically resolvable oscillations. This is sort of a holy grail for numerical methods for hyperbolic PDEs. Some great work from the late 1990’s comes to the rescue. Two researchers from NASA Glenn (Suresh & Huynh) published a great paper on doing much of this work. First reproducing a monotonicity-preserving method and then added extrema detection and preservation to it. This was a great general-purpose approach that works for multistep methods like Runge-Kutta.

This work uses the median function developed and used by HT Huynh. In a sense, I fell in love with this function as a means of engineering methods. The method takes three arguments and returns the one bounded by the other two. Thus, it is great at enforcing bounds, which is the whole game for high-resolution methods. It also has the property that if two of the arguments are a certain order of accuracy, the output retains that order of accuracy. This is because the result is a convex combination of the other two, or one of those two. I have postulated that this result applies to linear and nonlinear stability properties too.

“Normal science, the activity in which most scientists inevitably spend almost all their time, is predicated on the assumption that the scientific community knows what the world is like… Normal science often suppresses fundamental novelties because they are necessarily subversive of its basic commitments.” – Thomas Kuhn

As a sidebar to the whole extrema preservation study, I rewrote the limiter for the PPM method using the median. Once the median is defined, the PPM limiter can be expressed in four median function calls. It is compact and IMHO far clearer than the classical PPM description, which is elaborate and somewhat non-intuitive. Looking at the (magical) median as a bounding function provides the necessary clarity of approach. Being parabolic in each cell, the PPM method could potentially support smooth extrema.

The simplest version of the basic idea is brutally simple. If the data is monotone and the approximation preserves this, simply use that. If it is not, then one can switch over to WENO, or some other extrema-preserving method. The cost of WENO is only taken where it matters. It also isolates WENO from the dissipative solution it gives for monotone circumstances. Under those conditions, WENO produces something akin to the dissipative minmod result. WENO is only superior with smooth extrema. This method improves on both methods. With PPM, I can make this a single-step method. It has a larger CFL and accelerates the WENO solution by a factor of six, plus sharpens the results in general.

“Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.” – Antoine de Saint-Exupéry,

This unveils the basic approach for the advance. If some version of high-order works as a monotonicity-preserving approximation, use it. Do not do more work. If it does not, look at the data. Is it monotone or at an extremum? If it is monotone perhaps looks at other high-order, but lower than the initial attempt approximations. If one is at an extremum, determine if it is smooth and do something safe there. ENO or WENO are those sorts of approximations. If it is close to a shock, allow yourself to go to first-order. That’s it. It really is not that elaborate. It extends monotonicity methods to something more, and the verification work shows this. These methods are more accurate on a broad class of methods. In practice, this accuracy also makes them efficient. Colella and Sekora published a method with a lot in common with my ideas.

“My work always tried to unite the true with the beautiful; but when I had to choose one or the other, I usually chose the beautiful.” – Hermann Weyl

Now we get to the unfortunate part of the paper. The verification got removed in review. The associate editor demanded it rather bluntly: “If you want this published, take that shit out!” He and one of the reviewers, who is an asshole, killed this. I will note that the asshole reviewer is extremely good technically. Exceptional. Those are some of the most dangerous forms of assholes, by the way. I folded and removed the material. Now, 20 years later, I can finally get the basic idea of verifying shock tubes published. I can include a far better and more focused explanation and recipe for doing this. This includes a strong motivation in mathematics and efficiency from differences in accuracy.

I hope it helps alleviate the stagnation.

“Every genuine test of a theory is an attempt to falsify it, or to refute it.” – Karl Popper

The other idea that might have traction is the BVD and THINC-based methods. Combining this with high-order leads to impressive results. Imperfect, but hopeful. I was a reviewer of one of the articles, and felt like it was an arc of progress. I believe THINC might be the key here. It is a nonlinear first-order method that can deliver monotonicity with much less dissipation. The details are choosing the steepness parameter (and it having a parameter!). The other issue might be how the lack of first-order dissipation impacts the entropy condition. The question is whether the lack of dissipation in THINC ever threatens the entropy condition. It would be something good to study and put effort into.

“A new scientific truth does not triumph by convincing its opponents and making them see the light, but rather because its opponents eventually die, and a new generation grows up that is familiar with it.” – Max Planck

References

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, no. 2 (2007): 1827-1848. (105 Citations)

Greenough, J. A., and W. J. Rider. “A quantitative comparison of numerical methods for the compressible Euler equations: fifth-order WENO and piecewise-linear Godunov.” Journal of Computational Physics 196, no. 1 (2004): 259-281. (85 Citations)

Suresh, Ambady, and Hung T. Huynh. “Accurate monotonicity-preserving schemes with Runge–Kutta time stepping.” Journal of Computational Physics 136, no. 1 (1997): 83-99.

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

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

Deng, Xi, Yuya Shimizu, and Feng Xiao. “A fifth-order shock capturing scheme with two-stage boundary variation diminishing algorithm.” Journal of Computational Physics 386 (2019): 323-349.

Deng, Xi, Yuya Shimizu, Bin Xie, and Feng Xiao. “Constructing higher order discontinuity-capturing schemes with upwind-biased interpolations and boundary variation diminishing algorithm.” Computers & Fluids 200 (2020): 104433.

Rider, W. J., J. A. Greenough, and J. R. Kamm. “Combining high-order accuracy with non-oscillatory methods through monotonicity preservation.” International journal for numerical methods in fluids 47, no. 10-11 (2005): 1253-1259.

Rider, William J., and James R. Kamm. “How effective are high-order approximations in shock-capturing methods? Is there a law of diminishing returns?.” In Computational Fluid Dynamics 2004: Proceedings of the Third International Conference on Computational Fluid Dynamics, ICCFD3, Toronto, 12–16 July 2004, pp. 401-405. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006.