Given the broader spectrum of variables to choose from new schemes with exceptional properties can be developed.  One can blend volume-averaged, point, moment and derivatives together.  These schemes are all compact and have exceptional numerical properties.  We introduced them earlier as the extensions of the basic interpolations employed by Van Leer, but using the same principles.

On thing to recognize immediately is that the famous PPM scheme is a cell-centered implementation of the basic approach associated with Scheme V.  The difference is the construction of edge-centered data from cell-centered quantities.  The way that the original PPM overcame the issue was to use higher order approximations for the cell-edge quantities, specifically fourth-order edges for what is an intrinsically third-order scheme.  This allows the approximation to asymptotically approach fourth-order accuracy in the limit of vanishing Courant number.

More recently fifth, sixth and seventh order approximations have been used with PPM to good effect.  These have been applied to the use of PPM in global climate model dynamic cores as well as by Colella.  The author used this approach in his extrema-preserving methodology where the edge values are utilized to produce useful approximations in regions with smooth extrema.  The bottom line is that this approach has proven to be enormously flexible in practice due to the choice of the edge values coupled with a cell-average preserving reconstructing polynomial.  It is reasonable to have faith in the ability for other schemes presented next to be used in a similarly flexible manner.  Indeed the construction of approximations via polynomial reconstruction is highly amenable to such extensions as the geometric picture offered greatly aids the subsequent method development and testing.

One route to nonlinear stability are ENO methods that offer adaptive stencil selection.  These methods are based upon the choice of the “smoothest” stencil defined in some sense.  Another maxim from the ENO literature is the need to bias the stencils toward being upstream-centered.  Put differently, Van Leer’s paper presents a set of upstream-centered approximation that should be favored over other approximations.  Given this approach we might define an ENO scheme based on Scheme V as predominantly using that scheme, but choosing other more upwind or downwind stencils if the function being approximated is insufficiently smooth.

For a positive characteristic velocity an upwind stencil could define a parabola, by , and .  This gives a parabola of

.

This produces a semi-discrete scheme with third-order accuracy and a dispersion relation of .

A second stencil to choose from resulting in a third-order method is defined by , and . This gives a parabola of

.

This produces a semi-discrete scheme with third-order accuracy and a dispersion relation of .

The downwind stencil defined by  , and ends up not being useful because it results in a scheme with centered support.  This gives a parabola of

.

The updates become effectively decoupled because of cancelation of terms and the order of accuracy drops to second-order.  This produces a semi-discrete scheme with third-order accuracy and a dispersion relation of .

The same thing happens for a stencil of latex u^n_{j+1}$, and .

Now we can move to describing the performance of high-order methods based on Van Leer’s ideas, but extended to slightly larger support.  All these methods will, at most, reference their nearest neighbor cells.  The first is rather obvious and gives fifth-order accuracy.  The reconstruction is defined by cell-averages, and cell-edge values, .  This defines a quartic polynomial,

.

This produces a semi-discrete scheme with fifth-order accuracy and a dispersion relation of .  This is exceedingly accurate with the dispersion relation peaking at with an error of only 2.5%.

The next method was discussed and recommended by Phil Roe at the JRV symposium and a conversation at another meeting.  It uses the cell-average , the edge values , and the edge-first-derivatives, .It is also similar to the PQM method proposed for climate studies.  The PQM method is implemented much like PPM in that the edge variables are approximated in terms of the cell-centered degrees of freedom.  Here we will describe these variables as independent degrees of freedom.  The polynomial reconstruction defined by these conditions is

.

This produces a semi-discrete scheme with fifth-order accuracy and a dispersion relation of .  This is exceedingly accurate with the dispersion relation peaking at $latex\theta=\pi$ with an error of only 1.2%.

We will close with a couple of schemes that are more speculative, but use the degrees of freedom differently than before.  Both will be based on a cubic polynomial reconstruction and involve the first moment of the solution along with either edge-values or edge-slopes.  Aside from the use of the first moment it is similar to the schemes above.  The reconstruction for the moment, cell-average and cell-edge values is

.

.

As previous experience would indicate the use of the moment has remarkable properties, with this method producing the same error as the quartic reconstruction based on edge-values and slopes plus the cell-average, but one order lower reconstruction.

I will close by presenting three schemes based on cubic reconstructions, but utilizing the first moments.  Two will achieve fifth-order accuracy, and the last will suffer from cancellation effects that lower the accuracy to fourth-order.  These methods are unlike the discontinuous Galerkin methods in that their support will go beyond a single cell.  The first of the three will use the three cell-centered variables, and the moment of the central cell , giving a polynomial,

.

This produces a semi-discrete scheme with fifth-order accuracy and a dispersion relation of .  This is exceedingly accurate with the dispersion relation peaking at $latex\theta=\pi$ with an error of only 3.1%.

The next method uses the cell-center values of the cell and it upwind neighbor and the moments in each of those cells.  The reconstructing polynomial is

.

This produces a semi-discrete scheme with fifth-order accuracy and a dispersion relation of .  This is  accurate with the dispersion relation peaking at $latex\theta=\pi$ with an error about 12%.

Our final method uses the cell-centered value of the cell and its downwind neighbor along with the first moment in each of those cells.  The reconstruction takes the form,

.

We note that this stencil produces cancellation that lowers its accuracy by one order.  This produces a semi-discrete scheme with fifth-order accuracy and a dispersion relation of .  This is  accurate with the dispersion relation peaking at $latex\theta=\pi$ with an error of 10%. The last two methods may not be particularly interesting in and of themselves, but may be useful as alternative stencils for ENO-type methods.

Some of these options were profitably framed a long time ago in one of Van Leer’s papers (the fourth of his series published in 1977).  In that paper he described two methods that came into widespread use, the second-order accurate method that is lives on as the origin of much of the limiter work in the 1980’s, and is the most common modern approach used in aerodynamic codes, unstructured codes, and for remap in ALE codes.  He also introduced the base method that became the PPM method.  Ironically, these two methods were the worst of the six methods introduced.  Van Leer labeled them as schemes 1 and 4.    Van Leer’s scheme 1 is called the “piecewise linear method” and the scheme 4 is the “piecewise parabolic method (PPM).”  The polynomial approximation used in scheme 1 uses the integral average of cell value, and the derived gradient (or slope) to define the linear approximation.  Other linear approximations could be developed using biased approximation for the slope, but these methods would not be considered upstream centered.  The PPM approximation is built defining a parabola that reconstructs the integral of a cell and its two neighbors.  The more famous PPM method uses a polynomial matching the cell average, and high-order approximations to the values at the edge of the cell. 

Two other classes of methods were provided.  One of these is based on the moments of a solution (the zeroth moment is the cell average value).  These methods are equivalent to the discontinuous Galerkin (DG) method, which is the focus of copious research today, and one of the key approaches being explored to deal with the upcoming changes in computing architecture.    This is enabled by the scheme being developed to carry extra degrees of freedom in each computational cell (i.e., the moments, a single moment gives a linear basis, a second moment a quadratic basis).  Van Leer labeled them as schemes 3 and 6.  Scheme 6 was not described in details, but has been developed as the PPB (piecewise parabolic Boltzmann) scheme by Paul Woodward, and as a quadratic finite element method with the DG research.  The polynomial derivation will match the cell average and the first and/or second moment of the distribution.

It is notable that the bane of DG methods is the development of nonlinear limiters that do not destroy the increases in accuracy fidelity that the basic (linear) DG methods provide.  Thus far it is the development of effective limiters for DG that has most greatly “limited” their adoption by the community more broadly.  This is coupled to the next issue related to stability.

The methods in Van Leer’s paper used characteristic information to enhance their stability resulting in a Courant condition that was not restrictive.  Most DG methods developed today rely upon method-of-lines approaches, which means the spatial part of the operator is discretized, and the time operator is done using an ODE method.  This approach when using explicit methods results in a very restrictive Courant condition.  A challenge is to produce methods of this sort will greater stability.  Selectively reintroducing the characteristic information may be an answer.

The third class of approaches in Van Leer’s paper is significantly under-developed and deserves attention.  Moreover, I believe it can be profitably being extended to encompass even broader design principles.  As briefly commented on above these methods utilize point values of the quantity being integrated and derivative values.  In order to capture shocks, the integral of the quantity (i.e., the cell-centered value) is also integrated using the familiar control volume form.  Thus these methods can be described as combinations of finite volume and finite difference methods.    Van Leer’s Scheme 2 uses the integral average and a cell-centered derivative to define a linear polynomial.  The difference between this method and Scheme 1 is that Scheme 2’s derivative is evolved in time using the derivative of the PDE.  Scheme 5 is different.  The parabola is defined by the integral average and the edge values.  The difference between this method and the classic PPM method is that the edge values are evolved in time by the continuous version of the PDE.  By continuous version of the PDE I mean the strong differentiable form of the PDE and not the weak form used to integrate the integral average values or moments.

There is no reason, that this approach can’t be taken even further to include moments as well.  This provides the capability to design methods with tailored performance, both in terms of accuracy and memory use.  The key is to provide the capability to introduce appropriate nonlinear stability mechanisms of equivalent impact to those common with Van Leer’s piecewise linear or parabolic methods.  For example, a cubic polynomial could be derived using the integral average, the first moment and the cell-edge values.  A suggestion made by Phil Roe is to use the integral average with the cell-edge and cell-edge-derivative values to define a quartic polynomial and thus a fifth-order method.

Stability and accuracy analysis for these schemes becomes necessarily complex.  Using tools such as Mathematica renders the problem tractable.  I will note that Van Leer analyzed the method without such help, and this makes the analysis contained in his paper all the more masterful.

A Basis for Reconsidering Remap Methods

William J. Rider

Sandia National Laboratories, Albuquerque 

Abstract

Methods for discretizing remap are based on algorithms developed for hyperbolic conservation laws.  Since its introduction in 1977 Van Leer’s monotonicity-preserving piecewise linear method and its extensions have been ubiquitous in remap. In that 1977 paper Van Leer introduced another five algorithms, which largely have not been used for remap despite the observation that the piecewise linear method had the least favorable properties. This adoption parallels the algorithmic choices in other related fields.  Two factors have led to the lack of attraction to the five algorithms: the simplicity and effectiveness of the piecewise linear method, and complications in practical implementation of the other methods. Plainly, stated Van Leer’s piecewise linear method enabled ALE methods to move forward by providing a high resolution, monotonicity-preserving remap.  As a cell-centered scheme, the extension to remap was straightforward.  Several factors may be conspiring to reconsider these methods anew: computing architectures are more favorable towards floating point intensive methods, lacking data movement, and 30 years of experience in devising nonlinear stability mechanisms (e.g., limiters).  In particular, one of the method blends characteristics of finite volume and finite difference methods together in an ingenious manner that has exceptional numerical properties, and should be considered a viable alternative to the ubiquitous piecewise linear method.

 Introduction

In the numerical solution of hyperbolic PDEs, a series of papers by Bram Van Leer is considered seminal.  It was a five paper series with the august title “Towards the Ultimate Differencing Scheme…” In the fourth paper of the series a whole set of different methods were proposed (six in total).  Each of the methods is based on piecewise polynomial interpolation using the degrees of freedom to define the polynomials.   A first order polynomial leads to a second-order method, and a second-order polynomial leads to a third order method because of the integration involved in the solution.  Furthermore, each method developed was fundamentally upwind biased.  The broad class of methods can be described as being upstream centered, which is a centered basis for the polynomial with an upwind bias for information propagation.  This class of methods is well known to be advantageous mathematically.

Subsequently most of the development of numerical methods was based upon two of these methods.  The starkest aspect of this thread is that the two base methods were actually the least attractive from their fundamental numerical properties (accuracy, dissipation and propagation or phase error).  The reason for this is related to the more elaborate techniques necessary for nonlinear stability of solutions and practical use.  These techniques go by the name of “limiters” that serve to keep solutions physical and properly bounded. 

The relatively unexplored methods are interesting for several reasons.  Some of the basic design principles are quite different.  The favored methods are all based on integrating over control volumes, implying the use of conservation form (as essentially dictated to the community by Lax-Wendroff’s famous theorem).  A couple of the methods use other integrated quantities such as moments of a solution where the first moment is the integral of the quantity multiplied by a linear function, the second moment, the integral of the quantity multiplied by a quadratic function and so on.  The evolution equations for the moments is derived using the same procedure, and naturally invokes the weak form of the PDE.  The other form uses the differential form of the PDEs and involves introducing point quantities, such as the solution at a point, or derivatives of the solution at a point.  One of the key aspects of this development is to make sure the quantities are all dependent upon each other so that degrees-of-freedom are well coupled.

The present day interest should be driven by the needs of modern computers that are already far different than the previous generations, with massive and pervasive levels of parallelism.  New computers will greatly penalize memory references and communication compared to floating point operations.  In other words, once you’ve got something in your computer memory, you will be greatly rewarded for doing lots of floating point operations.  This character will offer benefits to methods having their data local and high-order accuracy requiring many operations.  The key for all these methods is to develop robust and sensible stability enhancing techniques that do no undermine the fundamental properties of the methods they are applied to. 

As note, by far, the greatest amount of effort for solving hyperbolic PDEs* has gone into cell-centered schemes due to their intrinsic simplicity and connection to existing computational approaches.  This work has been enormously successful over the past thirty some odd years.  Starting in the early 1970’s key concepts were added to the repertoire of scientist that allowed one to simultaneously achieve the physically appealing results provided by first-order method such as upwind differencing with the accuracy of second-order methods such as Lax-Wendroff.  These techniques were probably first introduced in the form of flux-corrected transport (FCT) by Jay Boris (and later in collaboration with David Book), but also independently by Bram Van Leer in his “Toward the Ultimate” series of papers.  There is also the compelling case of a third invention of these methods by Kolgan in the Soviet Union.  Kolgan died before receiving any attention and his invention was only recently uncovered.  A fourth stream of development looks similar in the passage of time is due to the Israeli mathematician, Ami Harten, who figures prominently in our tale later.

These methods are known as monotonicity preserving where the numerical solution of the PDE does not produce any new minimum or maximum values.  This is a property of the simplest form of the equation used extensively in the development of numerical methods.   Upwind differencing is the archetypical monotonicity-preserving linear scheme, and Lax-Friedrichs is another example.  Monotone schemes are first-order accurate.  The work of Boris, Van Leer and Kolgan all sought to produce monotonicity preserving methods that were not limited to first-order accuracy.

All three developments were made with knowledge of Godunov’s theorem that disallows the possibility of developing a linear method that at once second-order accurate and monotone.   The key to the theorem is the word linear.  The key advancement made was to introduce nonlinearity into the method even in the case of solving a linear PDE.  What is a linear scheme?  A linear method uses the same finite difference stencil (or formula) everywhere, while a nonlinear scheme adapts the finite difference scheme to the solution itself.  In other words, the scheme detects the nature of the solution and adapts the finite difference scheme to optimally solve it. 

At a detail level, the developments were much different, but the conceptual framing is nearly identical.  FCT uses a sequential process where the limiter adds back as little of the first-order monotone dissipation as possible to still produce monotone results.  Both Van Leer and Kolgan developed second-order extensions of Godunov’s method**.

In the field of hyperbolic PDEs nonlinear scheme changed everything?  In many fields of computational science this development was like an event horizon.  These nonlinear differencing schemes were an enabling technology for many numerical simulations, and resulted in an order of magnitude or more increase in the effective accuracy of simulations.

From this foundation there was a flurry of research activity in the 1980’s and 1990’s developing, extending and using this broad class of methods.  Examples abound in the literature and the success of these approaches in undeniable.  Several of the ore successful methods from the line of work, are the piecewise parabolic method (PPM), and the weighted essentially non-oscillatory (WENO) methods, which dominate modern use of these methods.  Both of these approaches have the appeal of utilizing elements of method design that are higher order accurate and produce results of significantly higher fidelity than the original nonlinear methods.  For example, PPM dominates the field of astrophysical simulation and WENO dominates mathematical research and related simulations.  Both methods are based on developing a numerical solution for variables all defined at the center of control volumes.

A clear downside to this approach is the need to communicate the information of many control volumes to update the values for any other control volume.  This communication is becoming increasingly problematic on modern computing platforms because of the cost of communication relative to floating-point operations, or memory access.  In order to get the most out of modern computers both communication of information, and memory access must be carefully managed.  Relatively speaking, floating point operations are “free,” which more accurately is that they are not the rate limiting aspect of computing.   Therefore we can stand to have algorithms that are very floating point intensive as long as they have relatively low communication intensity, and memory requirements.  The key is striking the right sort of balance.  Because of this issue it is time to rethink the design of algorithms in a major way.  Recent results at a conference stunned me by showing (for the first time I can remember), new computing architectures actually providing worse performance.  The new chips were better for many things, but not scientific computing.  It has the potential to be a true “wake-up call.”

Some of Van Leer’s methods have received attention and extension, most notably the PPM method developed by Colella and Woodward.  This method is extensively used in astrophysics, but not significantly in remap methods although a very close variant to Van Leer’s approach (scheme IV) as been adopted by ALEGRA.    The PPM method can be thought of as a reasonable cell-centered approach to scheme V where the edge-centered variables are replaced with temporary high-order variables. Perhaps the most extensive development of this method was undertaken by Eymann in conjuction with Roe.  This extension provided a number of advances that may prove useful in the setting of remap.  More direct implementations of scheme V have been followed by Guinot, and Popov (with Norman).  These approaches highlight the positive aspects of the method as we will reiterate below, but thus far have not achieved widespread adoption.  Zeng’s hybrid finite-difference-finite volume method is yet another closely related scheme that may include extensions of the approach important for practical adoption.

Discontinuous Galerkin methods have received the most attention although the direct descendents of Van Leer’s approach are far more limited with the line of work arising from Cockburn and Shu being widest in adoption.  Woodward has developed Van Leer’s sixth method in detail despite its sparseness of detail in the 1977 paper.

*Hyperbolic PDE methods can also be described as solving an advection equation, convection or remapping values from one grid to another.  Where I work, remap is the most common term.  Remap can also be done purely geometrically, and the advection is applied using a mathematical transformation to achieve equivalence.

**Godunov’s work was done largely in isolation to the progress made in the West.  He produced the theorem mentioned above, which is fundamental, and a unique numerical method for solving systems of hyperbolic PDEs.  This method is a fairly pure extension of first-order upwinding to systems.  Godunov used the Riemann problem to provide upwinding to the system, a truly inspired choice.  The Riemann problem is the analytical solution to the pure initial value problem of two semi-infinite states interacting.   In this solution we must note that the number of independent modes of transport, or waves is equal to the number of equations in a system.  The magnitude of the wave’s speed can vary significantly and differ in direction.   This muddies the meaning of upwind in the classical sense.  The Riemann solution is used to sort this out in a physically appealing way.

Here is the answer in a nutshell; people use an inappropriate approach and test problems to characterize their methods.

The reason I started doing work in verification was directly related to my work in developing better numerical methods.  In the early 90’s I was developing an improved implementation of a volume tracking method (or VOF where an interface is tracked through volumes, and the interface is reconstructed geometrically).   The standard implementation of the method resulted in horrific spaghetti code, and made subsequent development and debugging a nightmare.  I had developed a better, more object-oriented implementation and was eager to share it.  In the course of doing this implementation work, I engaged in extensive testing to put the method through its paces.  I felt that the standard tests were insufficiently taxing and provided poor code coverage, so I came up with several alternative test problems.  Existing tests involved translating objects on a grid, or engaging in solid body rotation.  Difficulty was defined by the complexity of the shape being moved.  My new problems used time dependent flowfields that had non-zero vorticity and could be reversed in time allowing exact error assessment.  These new problems were a hit and have largely replaced the earlier (too) simple tests.

Now fifteen years on the paper is very highly cited, but mostly because of the better tests, not because of the reason the paper was actually written.  I’d say about 75-90% of the citations are primarily for the tests, not the methodology.  There is a lesson in this that is positive; people want to test their methods rigorously.  For myself, I was a verification devotee thereafter largely because of the experience.

In terms of numerical methods and physics my greatest interest is the solution of hyperbolic PDEs.  I find the mathematics and physics of these equations both engaging on multiple levels, and the numerical methods to solve these equations spell-bindingly interesting.  It is also an area of numerical methods where verification is not the standard practice; at least for the application of the equations to full nonlinear PDEs that characterize the application of the method.  This isn’t entirely fair; for simple linear equations with smooth solutions or nonlinear equations with discontinuities verification is commonplace and expected.  Under these limited conditions authors regularly verify their methods and present results in virtually every paper.  When a discontinuity forms accuracy in the sense of high-order convergence is lost; solutions are limited to first-order convergence or lower.  Under these conditions verification is not done as a matter of course, in fact, it is exceedingly rare to the point of almost being unheard of.

This is extremely unfortunate.  Verification is not only about order of accuracy; it is also about estimating the magnitude of numerical error.

The standard approach when smoothness is not present is to plot results at some resolution against an exact solution and show these results graphically.  The main reason to show the results is to demonstrate a lack of oscillatory wiggles near the discontinuity.  The error itself is easily (almost trivial) computable, but almost never presented. The basis of this reasoning is that all results are basically first-order accurate, and the error isn’t important.  Implicit in this judgment is the belief that order of accuracy matter, and by virtue of this numerical error magnitude is unimportant.   Unfortunately, this point of view is not entirely correct, and misses a key aspect of method character.

When all solutions are first-order accurate there are actually significant differences in the level of numerical error.  Under mesh refinement these differences can become quite significant in terms of the quality of solution.   Consider the following example with regard to the quality of solution, for first-order a factor of two increases in mesh resolution results in a halving of numerical error.  If instead you changed the numerical method to halve the error on the original grid, the savings in compute time could be large.  A halving of the mesh results in the computational work increasing by a factor of four in one dimension (assuming the Courant number is held constant).  In two dimensions the increase in effort is a factor of eight and a factor of sixteen in three dimensions.  If the more accurate numerical method does not require four or eight or sixteen times the effort, it will be a win.    More accurate methods are most computationally intensive, but rarely so much that they aren’t more efficient than lower order methods. The cases where these dynamics play out are the closest to actual applications where the problems are discontinuous and never well behaved mathematically. Indeed it is this character that explains the rapid adoption of the second-order MUSCL (Van Leer differencing for you weapons’  lab folks) over the first-order methods.

The differences are not geometric as they would be with high-order accuracy and smooth solutions, but quite frankly no one really gives a damn about smooth solutions where high-order accuracy is achievable.  They are literally only of academic interest.   Seriously.  So why, isn’t more rigorous error estimation on more difficult problems the status quo?  Fundamentally people simply haven’t come to terms with the inevitable loss of accuracy for real problems, and the consequences this has on how methods should be designed and evaluated.

Despite this, the community solving hyperbolic PDEs believes that verification is being routinely done.  It is.  It is being done on cases that matter little, and only reflect on the order of accuracy of the method in cases no one cares about.  For people doing applications work, it makes verification seem like a pitiful and useless activity.  My suggestions that verification is done for error characterization and estimation is not considered useful.  I looked back through three and a half decades of the literature at results for the venerable Sod’s shock tube problem (en.wikipedia.org/wiki/Sod_shock_tube), and could find no examples of accuracy being quoted with computed results.  Sod showed runtime in his 1978 paper.  This implies that the accuracy of the results is comparable and the computational cost at fixed resolution only matters.  This seems to be an article of faith by the community, and it is wrong!

The fact is that both speed and accuracy matter, and results should be presented thusly.

There are large differences in the accuracy between methods.  If one takes the measure of accuracy of computational effort required to achieve constant accuracy one can find a factor of 30 difference in the efficiency of different approaches (http://www.sciencedirect.com/science/article/pii/S0021999107000897).  This difference in efficiency is in one dimension with the potential for dramatically larger differences in two or three dimensions.  Yet this community almost systematically ignores this issue, and verification of methods for practical problems.

This is a long-winded way of saying that there are a lot of cases where people prefer to use methods that are worse in performance.  Part of this preference is driven by the acceptance of the sort of verification practice discussed above.  An example would be WENO (http://www.sciencedirect.com/science/article/pii/S0021999196901308) where elegance and the promise of high-order would seem to drive people, despite its low resolution.  WENO stands for weighted essentially non-oscillatory, which blends order of accuracy preservation with lack of Gibbs oscillations in an elegant almost algebraic algorithm.  Most of the development of WENO since its inception has revolved around accuracy, which is compounded by computing results for these linear problems.   The focus of order-of-accuracy results in the method being quite poor at resolving discontinuities with performance at those points of the solution being on par with the minmod second-order method (the worst and most dissipative of the second-order TVD methods!).  Instead of improving WENO for practical problems and focusing on its efficiency, the mathematical community has focused on its ability to achieve formally high-order accuracy in situations no one really cares about.

This might explain the lack of penetration of this class of method into practical computations in spite of thousands of citations. It is an utterly absurd state of affairs.

MUSCL (http://en.wikipedia.org/wiki/MUSCL_scheme) is an example of much more successful method, and as I showed with Jeff Greenough a well-written MUSCL code kills a WENO code in actual efficiency (http://www.sciencedirect.com/science/article/pii/S0021999103005965).  This was just for one dimension and the gains for MUSCL over WENO in multiple dimensions are as great as expected.  It isn’t a surprise that WENO has not been as successful for applications as MUSCL.  A change in focus by the community doing WENO development might serve the method well.

PPM (http://crd.lbl.gov/assets/pubs_presos/AMCS/ANAG/A141984.pdf) is much better than either WENO or MUSCL.  The gains in efficiency are real (about a factor of two over MUSCL in 1-D).  Part of this resolution is due to the difference between a linear and parabolic local representation of the solution, and the parabolic profile’s capacity to represent local extrema.  PPM can also exhibit bona fide high-order accuracy through the selection of high-order values for the edge values used in determining the parabola.  The bottom line is that the PPM method has some intrinsic flexibility that can be ruthlessly exploited.  PPM is widely used by astrophysicists for many applications.  Beyond astrophysics it has been less successful and perhaps that should be studied.

WENO is elegant.  It is a beautiful method, and I loved coding it up.  I would have to say that my WENO code is extremely attractive, just as the mathematics underpinning these methods are appealing.  This appealing veneer can be superficial and hides the true performance of the method.  It is sort of like a beautiful person with a horrible personality or weak intellect; the attractive package hides the less than attractive interior.  This isn’t to say that the method can’t be improved in terms of efficiency. Indeed through taking various lessons learned from MUSCL and PPM and applying them systematically to WENO, the method could be dramatically improved.  In doing this some of the properties of WENO for smooth hyperbolic PDEs are undermined, while the properties for discontinuous problems are improved.  It could be done quite easily.

Ultimately the community has to decide where it wants impact.  Are hyperbolic PDEs important for applications?

Yes, and completely beyond a shadow of doubt.

Why does the published literature act the way it does? How has the community evolved to where the actual performance on more application-relevant testing matters less than beauty and elegance?

I think this whole issue says a great deal about how the applied mathematics community has drifted away from relevance.  That is a topic for another day, but keenly associated with everything discussed above.

Thanks for listening, happy New Year.

 One of the big problems that the entire V&V enterprise has is the sense of imposition on others.  Every simulation worth discussing does “V&V” at some level, and almost without exception they have weaknesses.  Doing V&V “right” or “well” is not easy or simple.  Usually, the proper conduct of V&V will expose numerous problems with a code, and/or simulation.  It’s kind of like exposing yourself to an annual physical; its good for you, but you might have to face some unpleasant realities.  In addition, the activity of V&V is quite broad and something almost always slips between the cracks (or chasms in many cases). 

To deal with this breadth, the V&V community has developed some frameworks to hold all the details together.  Sometimes these frameworks are approached as prescriptions for all the things you must do.  Instead I’ll suggest that these frameworks are not recipes, nor should they be thought of as prescriptions.  They are “thou should,” not “thou shalt,” or even “you might.“

 Several frameworks exist today and none of them is fit for all purposes, but all of them are instructive on the full range of activities that should be at least considered, if not engaged in.

 CSAU – Code Scaling Assessment and Uncertainty developed by the Nuclear Regulatory Committee to manage the quality of analyses done for power plant accidents.  It is principally applied to thermal-fluid (i.e. thermal-hydraulic) phenomena that could potentially threaten the ability of nuclear fuel to contain radioactive products.  This process led the way, but has failed in many respects to keep up to date.  Nonetheless it includes processes and perspectives that have not been fully replicated in subsequent work.  PCMM is attempting to utilize these lessons in improving its completeness.

 PCMM – Predictive Capability Maturity Model developed at Sandia National Laboratories for the stockpile stewardship program in the last 10 years.  As such it reflects the goals and objectives of this program and Sandia’s particular mission space.  It was inspired by the CMMI developed by Carnegie Mellon University to measure software process maturity.    PCMM was Sandia’s response to calls for greater attention to detail in defining the computational input into quantitative margins and uncertainty (QMU), the process for nuclear weapons’ certification completed annually.

 CAS – Credibility Assessment Scale developed by NASA.  They created a similar framework to PCMM for simulation quality in the wake of the shuttle accidents and specifically after Columbia where simulation quality played an unfortunate role.  In the process that unfolded with that accident, the practices and approach to modeling and simulation was found to be unsatisfactory.  The NASA approach has been adopted by the agency, but does not seem to be enforced.  This is a clear problem and potentially important lesson.  There is a difference between an enforced standard (i.e., CSAU) and one that comes across as well intentioned, but powerless directives.  Analysis should be done with substantial rigor when lives are on the line.  Ironically, formally demanding this rigor may not be the most productive way to achieve this end.

 PMI, Predictive Maturity Index developed at Los Alamos.  This framework is substantially more focused upon validation and uncertainty, and IMHO it gives a bit lax with respect to the code’s software and numerical issues.  In my view, these aspects are necessary to focus upon given advances in the past 25 years since CSAU came into us in the nuclear industry.

Computational simulations are increasingly used in our modern society to replace some degree of expensive or dangerous experiments and tests.  Computational fluid and solid mechanics are ever more commonplace in modern engineering practice.  The challenge of climate change may be another avenue where simulation quality is scrutinized and could benefit from a structured, disciplined approach to quality. Ultimately, these frameworks serve the role of providing greater confidence (faith) in the simulation results and their place in decision-making.   Climate modeling is a place where simulation and modeling plays a large role, and the decisions being made are huge.

The question lingers in the mind, “what can these frameworks do for me?”  My answer follows:

1. V&V and UQ are both deep fields with numerous deep subfields.  Keeping all of this straight is a massive undertaking beyond the capacity of most professional scientists or engineers.
2. Everyone will default to focusing on where they are strong and comfortable, or interested.  For some people it is mesh generation, for others it is modeling, and for yet others it is analysis of results.  Such deep focus may not lead (or is not likely to lead) to the right sort of quality.  Where quality is needed is dependent upon the problem itself and how the problem’s solution is used.
3. These are useful outlines for all of the activities that a modeling and simulation project might consider.  Project planning can use the frameworks to develop objectives and subtasks, prioritize and review.
4. These are menus of all the sort of things you might do, not all the things you must do. 
5. They provide a sequenced set of activities, prepared in a sequenced rational manner with an eye toward what the modeling and simulation is used for.
6. They help keep your activities in balance.  They will help keep you honest.
7. You will understand what is fit for purpose, when you have put too much effort into a single aspect of quality.
8. V&V and UQ are developing quickly and the frameworks provide a “cheat sheet” for all of the different aspects.
9. The frameworks flexibility is key, not every application necessarily should focus on every quality aspect, or apply every quality approach in equal measure.

10. Validation itself is incredibly hard in both breadth and depth.  It should be engaged in a structured, thoughtful manner with a strong focus on the end application.  Validation is easy to do poorly.

11. The computational science community largely ignores verification of code and calculations.  Even when it is done, it is usually done poorly.

12. Error estimation and uncertainty too rarely include the impact of numerical error, and estimate uncertainty primarily through parametric changes in models.

13. Numerical error is usually much larger than acknowledged.  Lots of calibration is actually accounting for the numerical error, or providing numerical stability rather than physical modeling.

The thoughts associuated with last week’s post continued to haunt me.  It hung over my thoughts as I grappled with the whole concept of thankfulness for last week’s holiday.  I know implicitly that I have a tremendous amont to be thankful for at both a personal and professional level.  By all but the most generous standards, I am very lucky, certainly far better off than the vast, vast majority of humanity.  Nonetheless, it is hard to shake the sense of missed opportunity and squandered potential.  The USA is not a healthy country right now, and that fills me with a sadness.

With a system that is so dysfunctional most of what we can be thankful for is close to home.  Things we used to take for granted, like freedom, and that your children had a better chance at a good life than you do are not secure any more.  We have transformed into a society where corporate rights exceed personal or human rights, and there is little trust in any institution public or private.   I wrote about the lack of trust in science last week and how it makes a scientists work both overly expensive and underly effective.  It is a tragic situation.

Of course the Internet has a lot to do with it.  Or at the very least the Internet has amplified many of the trends that were already apparent preceding its rise to societal prominence.  In a sense the Internet is a giant communication magnifier, but also allows anonymous communication at a scale unimaginable.  I am reminded of what Clay Shirky noted that we may be in the midst of huge reorganization of society similar to what happened after Gutenberg invented the printing press.  Its a big deal, but not much fun to be part of.  Anonymity can be a horrible thing if misused.  We are seeing this in spades.  You really can have too much information, or have it too unfiltered.  Worse yet than a filter is the propaganda that spins almost everything we read toward some world-view.  The money and talent is largely in the corporate camp, and we are being sold ideas they favor with a marketers talent for shaping our views.

Part of my inability to shake these ideas came in the form of a “longread” recommendation about the 40 year decline in the prospects of the American worker (http://prospect.org/article/40-year-slump) starting in 1974.  After massive growth in equality in the years following World War II, it ended in 1974, and began the steady march toward today’s perverse levels of inequality.  This was the same year as I had posited the beginning of the decline in trust for public institutions such as science.  While some institutions such as science, research and government have lost the public’s trust, the corporation has become the centerpiece for society. 

Stockholder return has become the benchmark for success.  This has become a stark contrast to the actual health or long-term prospects for a company.  Likewise, the government-funded research has become starkly risk adverse and commenserately short term focused.  Society as a whole will suffer the effects of these twin pathologies.  Neither public, nor private interests are investing in the future.  Our infrastructure crumbles and no one even thinks of creating a 21^st Century infrastructure because we can’t keep our 20^th Century infrastructure healthy.  R&D has become all development, and has to be attached to the bottom line preferably the next quarter.   This progress adverse corporate principle is adopted whole-cloth by the government because of a faith-driven belief that the “market knows best” and business practice is inherently superior to other approaches.  One might consider that such research would be application-mission oriented, but no it simply risk adverse and pursued because “success,” such as it is defined, is almost a sure thing.

In the process, the “1%” has risen to dizzying heights of wealth, largely through the decision making process where corporations invest far less capital in their futures and instead to pay massive dividends to their stockholders.  The implications for science, and society are far reaching.  Is there a connection?  I think it is all part of the same thing.  Any science that makes life difficult or complicated for a corporation is attacked because the profit motive and margin has become the sole measure of societal success.  The human toll is massive and our society shows no mercy or thought for the suffering all this wealth accumulation is unleashing.

I am reminded about the problems of correlation being linked to causation, but the seeming coincidence in timing might be more meaningful.  How are these two issues connected?  I’m not sure, but I do think there is one.  Perhaps science being an endeavour for the common good has lost favor because its benefits can be shared by all rather than a few.  Everything that produces a shared benefit seems to be in decline and the entire society is being structured to serve the very top of the food chain.  The wealthy have become apex predators in the human ecosystem, and seem have no qualm about “feeding” on the ever-expanding masses in poverty.  The loss of trust powers the problem because of the unique nature of the American phyche and its devotion to the individual above all.  Now we are transitioning to a view where the devotion is to the corporation (but really the rich who profit from the corporate “success”).

So these thems stretch across the expanse of years that define nearly my entire life, the mystery of how to leave something better for my children is unsolved.  This is what really haunts me, and why I’m not as thankful as I would like to be.