The beginning of wisdom is the definition of terms.

― Socrates

Accuracy, Fidelity, Resolution and Stability, Robustness, Reliability

These six words matter a lot in the discussion of numerical methods yet their meanings are quite poorly understood or even regularly conflict. Even worse they are poorly articulated in the literature despite their prominent importance in the character of numerical methods and their instantiation in code. Maybe I can make some progress toward rectifying this issue here. Consider this post to be a follow-on and compliment to the earlier post on improving CFD codes, https://wjrider.wordpress.com/2015/07/10/cfd-codes-should-improve-but-wont-why/.

proofOne of the biggest issues in providing clarity in these matters is the ultimate inability of classical mathematics to provide clear guidance as we move from the abstract and ideal world to the real and messy reality. In using methods to solve problems with a lot of reality things that work well or even optimally in an idealized version of the World fall apart. In the ideal World very high-order approximations are wonderful, powerful and efficient. Reality tears this apart and all of these characteristics change to problematic, fragile and expensive. The failure to bridge methods over to the real world undermines progress and strands innovation behind.

Accuracy is a simple thing to define, the deviation of an approximation from reality. For an idealized mathematical representation this measurement is “easy”. The problem is measuring this for any real world circumstance is quite difficult to impossible. One way to define accuracy is related to the asymptotic rate of convergence as the degree of approximation is changed this is “order-of-accuracy”. The connection of order of accuracy, and numerical precision is rather ill defined and fuzzy. Moreover reality makes this even harder.

A clear way that the World becomes real is shock waves (and other similar nonlinear structures). A shock wave or similarly discontinuous solution renders most numerical methods first-order accurate at best. The current knowledge about how formal ideal high-order accuracy connects to measurable accuracy in the presence of discontinuities is sketchy. This manifests itself in having research in methods focus on high-order accuracy without any understanding of how this would translate to accuracy for real World problems. Today the efficacy of high-order methods is merely an article of faith.

We have alternative definitions of accuracy focus on the terms fidelity and resolution. Both of these terms are even more fuzzy that accuracy. These both get applied to methods that provide their value to (more) real World circumstances where formal accuracy is diminished. Thus important classes of methods are defined as “high-fidelity” or “high-resolution”. Both of these definitions are used to imply capability to provide good solutions when the ugliness of reality intrudes into our idealized reality.

220px-Peter_Lax_in_Tokyo copy 2Peter Lax provided a definition of resolution in an unfortunately obscure source. There and in a fascinating interview with Lax by Phil Colella (http://history.siam.org/oralhistories/lax.htm) the concept was discussed with an astounding proposition, perhaps higher than second-order was too accurate and produced solutions that did not have enough “room” to capture true solutions. It is not a final answer, but it does yield a direction to thinking about such things.

Here is the key passage on the topic of resolution:

“COLELLA: So you have shocks, why second-order? What were you thinking?

LAX: Well, you want greater accuracy, but even more you want greater resolution. I defined a concept of resolution. If you take a difference method and you consider a set of initial value problems of interest, which in practice could be some ball in L1-space, anything will do, and then you look at the states into which it develops after the unit-time, any given time, that’s another set. The first surprise is that this set is much smaller for nonlinear…for linear equations where time is reversible, the size of this set is roughly the same as the original set. For nonlinear equations, which are not reversible and where the wave information is actually destroyed, it’s a much smaller set. And the measure of the set that is relevant is what’s called entropy or capacity with respect to some given scale delta. So the first thing to look at is what is the capacity or entropy of this set of exact solutions. Then you take a numerical method, you start, you discretize the same set of initial data, then you look at what you get after time t goes to whatever the test time was. A method has a proper resolving power if the size of this set is comparable to the size of the exact solution; if it’s very much smaller it clearly cannot resolve. And first-order methods have resolution that is too low, and many details are just washed out. Second-order methods have better resolution. In fact, I was trying to – well, I want to bring up the question: could it be that methods that are even higher order (third, fourth) have perhaps too much resolution, more resolution than is needed? I just bring this up as a question.”

I might offer a bit of support for that concept in the case of genuinely nonlinear problems below. In a nutshell, the second-order methods with conservation form provide truncation error that matches important aspects of the true physics. Higher order methods will not capture this aspect of the physics. I’ll also note that Len Margolin and I have followed a similar, but different line of thinking looking at implicit large eddy simulation (ILES). ILES is an observation that high-resolution methods appear to provide effective turbulence modeling without the benefit of explicitly added subgrid modeling.

So let’s talk about the archetype of nonlinear, real World, messy computations, shock waves. In some ways shocks are really nice, they are inherently dissipative even in the case where the system is free of explicit molecular viscosity. Dissipation in the limit of zero viscosity is one of the most profound aspects of our mathematical description of reality. For physical systems with a quadratic nonlinearity including shocks and turbulence, this dissipation scales, C \left(\partial_x u\right)^3 with u being the velocity and C being a constant. At its core is the imposition of reality on idealized math to describe reality, and provide a useful, utilitarian description of mathematically singular structures. This character is present in turbulence as well. Both have basically the same scaling law and deep philosophical implications.

sankaran_fig1_360This form of nonlinear dissipation comes directly from the application of the conservation form to methods with second-order accuracy. For energy this term is precisely the form of the asymptotic law except for its connection to the discrete system. If the method achieves a formally higher than second-order accuracy this term disappears. For very simple second-order schemes there are truncation errors that compete with this fortuitous term, but if the linear accuracy of the method is higher order, this term is the leading and dominant truncation error. This may explain why schemes like PPM, and FCT methods produce high quality turbulence simulations without explicit modeling, but methods like minmod or WENO do not. The minmod scheme has a nonlinear truncation error that dominates the control volume term. For WENO method the higher order accuracy means the dissipation is dominated by a combination hyperviscous terms.

These deep philosophical implications are ignored by the literature for the most part, with shocks and turbulence defining a separation of focus. The connections between these topics are diffuse and unfocused. A direct connection would be a stunning breakthrough, but entrenched interests in both areas conspire against this. This remarkable similarity of the limiting dissipation in the absence of viscosity have been systematically ignored by scientists. I see it as utterly compelling or simply brutally obvious for a quadratic nonlinearity. Either way the similarity is meaningful. One of the key problems is that turbulence is almost completely grounded in the belief that it can be completely described by incompressible flow. No one seems to ever question this assumption.

Incompressibility is a physically limited approximation of reality, but not reality. It renders the equations to be intractable in some ways (see the Clay prize for proving the existence of solutions!). The unphysical nature of the equations is two-fold: sound speeds are infinite and thermodynamics are removed (especially harmful is the loss of the second law). Perhaps more problematically is the loss of the very nonlinearity known to be the source of dissipation without viscosity for shock waves, that is the steepening of arbitrary disturbances into discontinuous shock waves.

I’ve written before about stability and robustness with a focus on the commonality of their definition https://wjrider.wordpress.com/2014/12/03/robustness-is-stability-stability-is-robustness-almost/. The default basic methodology for stability analysis was discussed too https://wjrider.wordpress.com/2014/07/15/conducting-von-neumann-stability-analysis/. If we add the term “reliable” the situation is quite analogous to the issues with accuracy. We ultimately don’t have the right technical definitions for the useful character of practical reliability and robustness of numerical methods and their executable instantiation in code. Stability is necessary for robustness and reliable, but robustness and reliable imply even more. Typically the concept of robustness applies to practical computational methods used for real World (i.e., messy) problems.Regions_02

The key issue for high order methods is the inherently non-smoothness and lack of clean structure in the real world. This messiness renders high-order methods of questionable utility. Showing that high-order methods improve real world, practical, pragmatic calculation is challenge for the research community working in this area. Generally high-order methods show a benefit, but at a cost that makes their viability in production software questionable. In addition the high-order methods tend to be more fragile than their lower order cousins. The two questions of robustness in use and efficiency are the keys to progress.

Given all of these considerations, what is a path forward to improving existing production codes with higher order methods?

I will close with a set of proposals on how we might see our way clear to improving methods in codes by balancing requirements for high-order accuracy, high-resolution, robustness and stability. The goal is to improve the solution of “real” “practical” problems, not idealized problems associated with publishing research papers.

  1. For practical accuracy high-order only matters for linear modes in the problem. Therefore seek high-order only for the leading order terms in the expansion. Full nonlinear accuracy is a waste of effort. Full nonlinear accuracy only matters if the flow is fully resolved and the fields contain the level of smoothness equal to the scheme (they never do!). This would allow the quadratures usually invoked by formally high-order methods could be reduced along with the costs.
  2. For nonlinear structures, you just need second-order accuracy, which gives you a truncation error that matches the asymptotic structure of dissipation analytically. Removing this term may actually harm the solution rather than improve. The reasoning follows Lax’s comments above.
  3. Nonlinear stability is more important than linear stability in fact nonlinear stability will allow you to use methods that are locally linearly unstable. Extending useful nonlinear stability beyond monotonicity is one of the keys to improving codes.
  4. Developing nonlinear stability principles beyond monotonicity preservation is one of the keys to progress. A test of a good principle is its ability to allow the use of linearly unstable methods without catastrophe. The principle should not create too much dissipation outside of shocked regions (this is why ENO and WENO are not good enough principles). In a key way monotonicity-preserving methods naturally extended the linear monotone and first order methods. The next step beyond monotonicity preservation has not built upon this foundation, but rather introduced an entirely different concept. A more hierarchical approach may be needed to achieve something of more practical utility.
  5. The option of fully degrading the accuracy of the method to first-order accuracy must always be in play. This step is the key to robustness. Methods that do not allow this to happen will never be robust enough for production work. This is another reason why ENO and WENO don’t work for production codes.

Logically, all things are created by a combination of simpler less capable components

– Scott Adams (or the Dogbert Principle that applies to high resolution schemes in Laney, Culbert B. Computational gasdynamics. Cambridge University Press, 1998).

References

Lax, Peter D. “Accuracy and resolution in the computation of solutions of linear and nonlinear equations.” Selected Papers Volume I (2005): 184-194.

Margolin, Len G., and William J. Rider. “A rationale for implicit turbulence modelling.” International Journal for Numerical Methods in Fluids 39.9 (2002): 821-841.

Grinstein, Fernando F., Len G. Margolin, and William J. Rider, eds. Implicit large eddy simulation: computing turbulent fluid dynamics. Cambridge university press, 2007.

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.

Broadwell, James E. “Shocks and energy dissipation in inviscid fluids: a question posed by Lord Rayleigh.” Journal of Fluid Mechanics 347 (1997): 375-380.

Bethe, Hans Albrecht. Report on” The Theory of Shock Waves for an Arbitrary Equation of State”… 1942.

Advertisements