Recently, I wrote about the priorities in code development putting accuracy and efficiency last in the list of priorities (https://williamjrider.wordpress.com/2014/11/21/robust-physical-flexible-accurate-and-efficient/). Part of the not very implied critique associated with this is that the relative emphasis in development is very close to the opposite of my list. High performance computing and applied mathematics today is mostly concerned with efficiency (first) and accuracy (second). I believe these priorities do us a disservice, represent a surplus of hubris and fail to recognize some rather bold unfinished business with respect to stability theory.

All that it is reasonable to ask for in a scientific calculation is stability, not accuracy.

–Nick Trefethen

I thought about what I wrote a few weeks ago, and realized that when I state robust, I mean almost the same thing as stable. Well almost the same is not the same. Robust is actually a stronger statement since it implies that the answer is useful in a sense. A stable calculation can certainly produce utter and complete gibberish (it may be even more dangerous to produce realistic-looking, but qualitatively/quantitatively useless results). I might posit that robustness could be viewed as a stronger form of stability that provides a guarantee that the result should not be regarded as bullshit.

Perhaps this is the path forward I’m suggesting. The theory of PDE stability is rather sparse and barren compared to ODE theory. PDE stability is really quite simple conceptually, while ODE stability theory is rich with detail and nuance. One has useful and important concepts such as A-stability, L-stability and so on. There are appealing concepts such as relative-stability and order stars, which have no parallel in PDE stability. I might be so bold as to suggest that PDE stability theory is incomplete and unfinished. We have moved toward accuracy and efficiency and never returned to finish the foundation they should be built upon. We are left with a field that has serious problems with determining quality and correctness of solutions (https://williamjrider.wordpress.com/2014/10/15/make-methods-better-by-breaking-them/, https://williamjrider.wordpress.com/2014/10/22/821/).

Maybe a useful concept would be robust stability. What are the conditions where we can expect the results to be physical and nonlinearly stable? Instead the concept of robustness often gets a bad name because it implies tricks and artifices used to produce results securely. A key point is that robustness is necessary for codes to do useful work, yet doing the work of making methods robust is looked down upon. Doing this sort of work successfully resulted in the backhanded compliment/slight being thrown my way:

you’re really good at engineering methods.

Thanks, I think. It sounds a lot like,

you’re a really good liar

In thinking about numerical methods perhaps the preeminent consideration is stability. As I stated, it is foundational for everything. Despite its centrality to the discussion today, stability is a rather later comer to the basic repertoire of the numerical analyst only being invented in 1947 while many basic concepts and methods precede it. Moreover its invention in numerical analysis is extremely revealing about the fundamental nature of computational methods. Having computers and problems to solve with them drives the development of methods.

Recently I gave a talk on the early history of CFD (https://williamjrider.wordpress.com/2014/05/30/lessons-from-the-history-of-cfd-computational-fluid-dynamics/) and did a bit of research on the origin of some basic concepts. One of my suppositions was that numerical stability theory for ODEs must have preceded that for PDEs. Instead this was not true! PDEs came first. The reason for this is the availability and use of automatic computation (i.e., computers). Because of the applications of PDEs to important defense work during and after World War 2, the problem of stability was confronted. Large-scale use of computers for integrating ODEs didn’t come along until a few years later. The origins of stability theory and its recognition are related in a marvelous paper by Dahlquist [Dahlquist], which I wrote about earlier (https://williamjrider.wordpress.com/2014/08/08/what-came-first-the-method-or-the-math/). There I expressed my annoyance at the style of mathematics papers that obscures the necessary human element in science in what I believe to be a harmful manner. The lack of proper narrative allows the history and impact of applied math to be lost in the sands of time.

The PDE stability theory was first, and clearly articulated by John Von Neumann and first communicated during lectures in February 1947, and in a report that same year [VNR47]. These same concepts appeared in print albeit obliquely in Von Neumann and Goldstine [VNG47], and Crank-Nicholson’s classic [CN47]. Joe Grcar gives a stunning and full accounting of the work of Von Neumann and Goldstine and its impact on applied mathematics and computing in SIAM Review [Grcar]. Since Von Neumann had access to and saw the power of computing, he saw stability issues first hand, and tackled them. He had to, it bit him hard in 1944 [MR14]. His stability analysis methodology is still the gold standard for PDEs (https://williamjrider.wordpress.com/2014/07/15/conducting-von-neumann-stability-analysis/).

Another theme worth restating is the roll of (mis-)classification of the early reports had on muddying the history. LA-657, which was the report on the first mention of stability in numerical analysis was classified until 1993 even though the report is clearly unclassified (https://williamjrider.wordpress.com/2014/11/20/the-seven-deadly-sins-of-secrecy/). As it turned out the official unveiling of the ideas regarding stability of PDEs came out in two papers in 1950 [VNR50,CFVN50].

As Dahlquist relays the PDE world had a head start, and other important work was conducted perhaps most significantly the equivalence theorem of Lax [LaxEquiv]. This theorem was largely recreated independently by Dahlquist two or three years later (he reports that Lax gave the theory in a seminar in 1953). The equivalence theorem states that the combination of stability and consistency is equivalent to convergence. Being rather flip about this stability means getting an answer and consistency means solving the right problem.

 

From there the ODE theory flowered and grew to the impressive tapestry we have today. A meaningful observation is that we have a grasp of the analytical theory for the solution of ODEs that eludes us today with PDEs. Perhaps the PDE theory would flow like water from a breaking dam were such an analytical theory available. I’m not so sure. Maybe the ODE theory is more of the consequence of the efforts a few people or a culture that was different from the culture responsible for PDEs. Its worth thought and discussion.

The investigator should have a robust faith – and yet not believe.

 Claude Bernard

[LaxEquiv] Lax, Peter D., and Robert D. Richtmyer. “Survey of the stability of linear finite difference equations.” Communications on Pure and Applied Mathematics 9, no. 2 (1956): 267-293.

[VNG] Von Neumann, John, and Herman H. Goldstine. “Numerical inverting of matrices of high order.” Bulletin of the American Mathematical Society 53, no. 11 (1947): 1021-1099.

[Dahlquist] Dahlquist, Germund. “33 years of numerical instability, Part I.” BIT Numerical Mathematics 25, no. 1 (1985): 188-204.

[CN47] Crank, John, and Phyllis Nicolson. “A practical method for numerical evaluation of solutions of partial differential equations of the heat-conduction type.” In Mathematical Proceedings of the Cambridge Philosophical Society, vol. 43, no. 01, pp. 50-67. Cambridge University Press, 1947.

[CFVN50] Charney, Jules G., Ragnar Fjörtoft, and J. von Neumann. “Numerical integration of the barotropic vorticity equation.” Tellus 2, no. 4 (1950): 237-254.

[VNR50] VonNeumann, John, and Robert D. Richtmyer. “A method for the numerical calculation of hydrodynamic shocks.” Journal of applied physics 21, no. 3 (1950): 232-237.

[VNR47] VonNeumann, John, and Robert D. Richtmyer. “On the numerical solution of partial differential equations of parabolic type.” Los Alamos Scientific Laboratory Report, LA-657, December 1947.

[Grcar] Grcar, Joseph F. “John von Neumann’s analysis of Gaussian elimination and the origins of modern Numerical Analysis.” SIAM review 53, no. 4 (2011): 607-682.

[MR14] Mattsson, Ann E., and William J. Rider. “Artificial viscosity: back to the basics.” International Journal for Numerical Methods in Fluids (2014). DOI 10.1002/fld.3981

We are our choices.

― Jean-Paul Sartre

Life comes with many choices regarding what to do, what to eat, buy, watch, listen to and so on. Depending on your personal tastes these choices are wonderful or a burden. If you really care about something quite often you demand choices to be happy. You won’t be pleased with limited options when you know something better isn’t even being offered. In other cases where you aren’t emotionally invested, too many choices can be a burden, and unwelcome. You just need something functional and aren’t willing to expend the effort to sift through a bunch of alternatives. This distinction happens over and over across our lives both personal and professional.

What one person demands as a phalanx of options is a crushing affront to another. The demands of choice come from the aficionado who sees the texture and variation among the choices. When no options are available it can be greeted as the acceptance of something awful. This could even be true for the single option, which is acknowledged as the best and would be chosen from many options. On the other hand for someone who doesn’t care about the details, the mediocre is just fine. It isn’t that they wouldn’t like something better; it is that they can’t tell the difference or don’t care. This sort of dichotomy exists with everyone and varies topic to topic. It plays a huge role in science and engineering. I am certainly guilty of this, and I suspect all of you are too.

In any moment of decision, the best thing you can do is the right thing. The worst thing you can do is nothing.
― Theodore Roosevelt

A while back I wrote about what I don’t like about the finite element method (FEM) (https://williamjrider.wordpress.com/2014/08/01/what-do-i-have-against-the-finite-element-method/). Over the long weekend I was thinking about adaptivity and robustness in numerical methods. Some of my thoughts were extensions of the Riemann solver work discussed last week. When my thoughts turned to finite element powered methods, it dawned on me that I didn’t have many options, or more properly the extensive choices offered by other frameworks. The choices I did have were limited in scope and flexibility. Some approaches to method adaptation were simply absent.

I realized that this was what really deeply bothered me about finite elements. It isn’t the method at all; it’s the lack of options available to engineer the method. For a lot of engineers the FEM is a “turn the crank” exercise. You get a mesh, and pick the degrees of freedom, put the governing equations into the weak form and integrate. You have a numerical method and you are done. For complex physics this approach can be woefully inadequate and with the FEM you aren’t left with much to do about it.

Working at Sandia one thing is always true; the code you write will implement the FEM. With a new project and generally it would be very beneficial to have multiple valid discretizations on the same mesh. This would enable a number of things such as error estimation, resilience against hardware errors, and more robust overall algorithms. The problem is that the FEM generally offers a single preferred discretization once the mesh and associated elements are chosen.

To some extent this is overstated. Some FEM methods offer a bit more in the way of options such as discontinuous Galerkin. Additionally, one could chose to over- or under-integrate, lump the mass matrix or apply a stabilization method. Even then, the available options for discretizing are rather barren compared with finite volume or finite difference methods. It feels like a straightjacket by contrast to relative unconstrained freedom. Even the options I once worked with were too constrained compared with the universe of possibilities offered as I discovered in my most recent paper (“Revisiting Remap Methods” DOI 10.1002/fld.3950).

The hardest choices in life aren’t between what’s right and what’s wrong but between what’s right and what’s best.
― Jamie Ford

For people whose job is doing analysis of physical or engineered systems with codes, the options are a burden. They just want something that works and don’t care much about the detail. They graciously accept something better or something improved even if they couldn’t express the reasons for the improvement. With commercial CFD codes this situation has become critical. These codes reflect a relatively stagnant state of affairs with CFD methods.

For me this is a particular issue in the area of shock physics. Most of the users of shock physics codes are completely happy with their options. For some, the code simply needs to run to completion and produce something that looks plausibly realistic. For me this seems like a god-awfully low standard, and I see methods that are antiquated and backwards. The code users usually only notice new methods when something bad happens, the code runs slower, the answer changes from the ones they’ve grown accustomed to, or the code crashes. It is a rarity for the new method to be greeted as a benefit. The result is stagnation and a dearth of progress.

Sometimes you have to choose between a bunch of wrong choices and no right ones. You just have to choose which wrong choices feels the least wrong.
― Colleen Hoover

This trend is fairly broad. As numerical methods have matured, the codes based upon them have stabilized because the users are generally satisfied with the options offered. Improvements in the methodology are not high on their wish list. Moreover, they have a general understanding of the options the codes are based on, and have little interest in the methods that might be developed to improve upon them. As such the bar for improving codes has been raised to a very high level. With the cost of implementing codes on new computer architectures growing, the tide has turned to a focus on legacy methodology on modern computers sapping the impetus to improve.

We have become a community that sees options as a burden. Other burdens such as changes in computers are swallowing the appetite for the options that exist. As time goes by, the blessings seem more and more distant and foreign to the thought process. Moreover the users of codes don’t see the effort put into better methods as a virtue and want to see focus on improving the capacity to model the physical systems they are interested with. Part of this relates strongly to the missing elements in the education of people engaged in modeling and simulation. The impact of numerical methods on the modeling of physical systems is grossly under-appreciated, and leads to a loss of perspective. Methods in codes are extremely important and impactful (artificial, numerical and shock dissipation anyone?). Users tend to come close to completely ignoring this aspect of their modeling due to the esoteric nature of its impact.

When faced with two equally tough choices, most people choose the third choice: to not choose.

― Jarod Kintz

A

Time is an illusion.

― Albert Einstein

 Time is relentless. As an opponent it is unbeatable and can only be temporarily held at bay. We all lose to it, with death being the inevitable outcome. Science uses the second law of Thermodynamics as the lord of time. It establishes a direction defined by the creation of greater disorder. In many ways the second law stands apart from other physical laws in its fundamental nature. It describes the basic character of change, but not its details.

But if your theory is found to be against the second law of thermodynamics I can give you no hope; there is nothing for it but to collapse in deepest humiliation.

— Sir Arthur Stanley Eddington

 Change is constant and must be responded to. The challenge of the continual flow of
events provides the key distinguishing character of response. On the one hand conservatives resist the flow and attempt to retain the shape of the World. Liberals and progressives work to shape the change to so that the World changes for the better. Where the conservative sees the best future in the past, the progressive sees the best future as being a new beginning.

Change isn’t made by asking permission. Change is made by asking forgiveness, later.

― Seth Godin

These tendencies are seen in differing taste for the arts. Take music where oldies are the staple of conservatives who don’t warm to the newer ideas. The old standards of their childhood and teen years make for a calming influence and sentimental listening. The progressive ear looks for new combinations rather than the familiar. Invention and improvisation are greeted warmly as a new challenge to one’s tastes. For example rap is viewed as not being music of any sort by the conservative ear, and greeted as stunningly original by the liberal ear. On the one hand the past is viewed as a template for the future, and on the other changes are seen as the opportunity for improvement. This tension is at the core of humanity’s struggle for mastery over time.

Our time is marked by certain emblematic moments such as 9/11, Nixon’s resignation or the fall of the Berlin Wall. Each of these moments clearly defines a transition from everything before it, to everything after it. Some of these moments are simply climaxes to events preceding them. The horror of 9/11 started with the rise of Islam 1400 years ago, continuing with the Crusades, European colonialism, the oil crisis of the 70’s, American support for the Shah and his fall with rise of Islamic fundamentalism, the Soviet invasion of
Afghanistan, the American invasion of Iraq and the constancy of Arab tension over Israel. Our response has assured that the war will continue and has only enflamed more terrorism. Rather than short-circuit the cycle of violence we have amplified it, and assured its continuation for another generation. We have learned nothing from the history leading up to the event of September 11, 2001.

Tradition becomes our security, and when the mind is secure it is in decay.

― Jiddu Krishnamurti

These developments highlight some of the key differences with conservative and liberal responses to crisis. The conservative response usually takes little note of history, and applies power as the strategy. Power usually suits the powerful being arguably simple and usually effective. Liberals and progressives on the other hand are eager to take a different path, try something new and different, but often encounter paralysis from the analysis of the past. The different approach is often a failure, but when it succeeds the results are transformative. Power’s success only reinforces the power applying it. Ultimately when power encounters the right challenge, it fails and upsets the balance. In the end the power is reset and eventually the balance will be restored with a new structure at the helm.

Societies in decline have no use for visionaries.

― Anaïs Nin

In science, the same holds conventional theories and approaches work almost all the time, but when they are overturned it is monumental. Even there conservative approaches are the workhorse and the obvious choice. Every so often they are exposed by something progressive and new that produces results the old approaches could not. This is the sort of thing that Kuhn wrote about with revolutions in science. As with other human endeavors the liberal and progressive wing leads science’s advance. The day-in, day-out work of science is left to the conservative side of things.

 “Normal science” means research firmly based upon one or more past scientific achievements, achievements that some particular scientific community acknowledges for a time as supplying the foundation for its further practice.

— Thomas Kuhn

So we are left with a balance to achieve. How do we handle the inevitability of change from the remorseless march of time? Are we interested in the conservative approach leading to uninspired productivity? Or progressive breakthroughs that push us forward, but most often end in failure?

All the effort in the world won’t matter if you’re not inspired.

― Chuck Palahniuk

The measure of intelligence is the ability to change.

― Albert Einstein

In looking at the codes we work with today one thing stands out. The methods used in production software are generally much simpler than it should be. Advances that should have been commonplace by now aren’t present. There seems to be a good reason for this; the complexity of implementing algorithms on modern computers biases choices toward the simple. The result is a relative stagnation in algorithms with telltale sign of utilizing adaptive concepts far less than one would have imagined.

Extraordinary benefits also accrue to the tiny majority with the guts to quit early and refocus their efforts on something new.

― Seth Godin

The types of adaptivity most commonly seen are associated with adaptive grids (or “h” refinement). Grids lend themselves to straightforward understanding and impressive visualization. Even with its common presence, even this form of adaptivity is seen far less than one might have thought looking forward twenty years ago. Adaptivity takes other forms far less common than h-refinement such as p-adaptivity where the order of an algorithm is adjusted locally. A third classical form is r-adaptivity where the mesh is moved locally to improve solutions. This is the second most common approach in the guise of remesh-remap methods (or ALE codes). I’d like to chat about a handful of other approaches that could be big winners in the future especially if combined with the classical approaches.

To improve is to change; to be perfect is to change often.

― Winston S. Churchill

One of the really big options to exercise with adaptivity are algorithms. Simply changing the algorithm based on local solution characteristics should yield great enhancement in accuracy, and robustness. Taken broadly the concept has been around a long time even if it isn’t recognized as such. Right from the beginning with Von Neumann and Richtmyer’s artificial viscosity the addition of nonlinear dissipation renders the method adaptive. The dissipation is effectively zero if the flow is smooth, and dominant if the flow is discontinuous. Upwinding is another such approach where the support (or stencil) for a method is biased by the physics for better (less accurate, but physical) results.

These are relatively simple ideas. More complex adaptation in algorithms can be associated with methods that use nonlinear stencils usually defined by limiters. These methods use a solution quality principle (typically monotonicity or positivity) to define how a computational stencil is chosen (FCT, MUSCL, and TVD are good examples). More advanced methods such as essentially non-oscillatory (ENO) or the elegant Weighted ENO (WENO) method take this adaptivity up a notch. While algorithms like FCT and TVD are common in codes, ENO hasn’t caught on in serious codes largely due to complexity and lack of overall robustness. The robustness problems are probably due to the overall focus on accuracy over robustness as the key principle in stencil selection.

One area where the adaptivity may be extremely useful is the construction of composite algorithms. The stencil selection in ENO or TVD is a good example as each individual stencil is a consistent discretization itself. It is made more effective and higher quality through the nonlinear procedure used for selecting. Another good example of this principle is the compositing of multigrid methods with Krylov iterations. Neither method is as effective on its own. They either suffer from robustness (multigrid) or suboptimal scaling (Krylov). Together the methods have become the standard. Part of the key to a good composite is the complementarity of the properties. In the above case multigrid can provide optimal scaling and Krylov offers stability. This isn’t entirely unlike TVD methods where upwinding offers the stability, and one of the candidate stencils offers optimal accuracy.

A third area to consider is adaptive modeling approaches. One example can be found with multiscale methods where a detailed (assumed more accurate) model is used for the physics to make up for the crude baseline model. In many cases multiple models might be considered to be valid or applicable such as turbulence, failure or fracture modeling. In other cases none of the available models might be applicable. It might make sense to solve all the models and establish conditions for choosing or compositing their effect on the solution. If done correctly the limitations of a single method might be overcome through the selection procedure. In each of the cases mentioned above the current approaches are woefully inadequate.

A general issue with adaptivity that in estimation is holding it back is the relative balance of focus on accuracy over robustness. I believe great tipping the balance toward robustness demanded for applications could make progress. In academic research accuracy is almost always the focal point often at the cost of robustness. Efficiency would be the second focal point that undermines adaptivity’s adoption by codes.
As I noted in an earlier post, https://williamjrider.wordpress.com/2014/11/21/robust-physical-flexible-accurate-and-efficient/, the emphasis is often opposite to what applications demand. The combination of robustness-physicality-flexibility might do well to replace the typical accurate-efficient focus. The efficiency focus has hamstrung methods development for the whole of the MPP era, and the next generation of computers promises to make this worse. Combined with the research focus on accuracy this produces a combined impact of spurring outright stagnation in deployment of the adaptive approaches that ought to be dominating computation today.

The world as we have created it is a process of our thinking. It cannot be changed without changing our thinking.

― Albert Einstein

Despite our massive advances with the raw power of computers, we have missed immense opportunities to unleash their full potential. The mindset that has created this environment is still dominant; more emphasis is placed on running old methodology on new computers than inventing new (better) methodologies optimal to the new computers. The result of this pervasive mismanagement is a loss of opportunity, and a loss potential. The end result is also a lack of true capability and problem solving capacity on these computers. Over time this stagnation has cost us more problem solving capability than we have gained over the same period of time with faster computers.

It’s never too late

…to start heading in the right direction.

― Seth Godin

Gratitude makes blessings permanent.

― Raheel Farooq

It is the uniquely wonderful holiday of Thanksgiving in the United States. It’s one of the few holidays that haven’t been completely sullied by commercialism although “Black Friday” is making a run at it. I’m thankful that my employer honors the Holiday unlike too many. It might be nice to list things to be thankful about in science and technology.

As we express our gratitude, we must never forget that the highest appreciation is not to utter words, but to live by them.

―John F. Kennedy

My job. All in all I’m pretty lucky. Beyond having enough money to have a comfortable life with food to eat, comfortable shelter and a few luxuries, I get to do what I love a little bit each week. I’ll save my concerns that the Labs where I work are a shadow of their former selves compared to the rest of the World, I’m doing great.

What a computer is to me is the most remarkable tool that we have ever come up with. It’s the equivalent of a bicycle for our minds.

― Steve Jobs

Modeling and simulation. The use of computers to solve problems in physics and engineering has become commonplace. Its common nature shouldn’t detract from the wonder we should feel. Our ability to construct virtual versions of reality is both wonderful for exploration, discovery and utility. The only thing that gives me pause is a bit of hubris regarding the scope of our mastery.

Algorithms. Systematic ways of solving problems that are amenable to computing fill me with wonder. The only regret is that we don’t rely upon this approach enough. An accurate, elegant and efficient algorithm is a thing of beauty. Couple the algorithm with mathematical theory and it is breathtaking.

Useful applied math. Mathematics is a wonderful tool if used properly. So much useful theory has been developed for so many aspects of science. Whenever mathematics is applied to bring order to an area of science I celebrate. It should be happening a lot more than it does, but when it does it’s great.

Technology is anything invented after you were born.

― Alan Kay

The end of Moore’s law. This is a great opportunity for science to quit being lazy. If we had relied upon more than raw power for improving computing, our ability to use computers today would be so much more awesome. Perhaps now, we will focus on thinking about how we use computers rather than simply focus on building bigger ones.

Innovative software. Is what makes the current computing revolution interesting. Perhaps science will start to understand how the key is software and not raw computing power. Software is evolving computing even with Moore’s law being on life support because it changes how we use computers constantly.

When we change the way we communicate, we change society

― Clay Shirky

The Internet and the World Wide Web. We are living through a great transformation in human society. The Internet is changing our society, our governance, our entertainment, and almost anything else you can imagine. The core is it changes the way we talk, and the way we get and share information. It makes each day interesting and is the spoon that stirs the proverbial pot.

Nuclear weapons. We owe the relative piece that the World has experienced since World War II to this horrible weapon. As long as they aren’t used they save lives and keep the great powers in check.

Turbulence. This is the gift that keeps giving. Turbulence is basically unsolved. It is also beautiful, important and pervasive. A breakthrough in understanding this bit of physics would be transformative.

Shock physics. Shocks are super cool. Energetic and destructive the drive to understand them drove early computing during World War II, and few realize the debt we owe to them. We understand far less about shock physics than we might admit, and it would be great to get back to focusing on discovery again.

Big data and statistics. Computers, sensors, drones and the internet of things is helping to drive the acquisition of data at levels unimaginable only a few years ago. With computers and software that can do something with it, we have a revolution in science. Statistics has become sexy and add statistics to sports and you combine two things that I love.

Genetics. The wonders of our knowledge of the genome seem boundless and shape knowledge gathering across many fields. Its impact on social science, archeology, paleontology to name a few is stunning. We have made incredible discoveries that expand the knowledge of humanity and provide wonder for all.

Our technology forces us to live mythically

― Marshall McLuhan

Modern medicine. Today we have all sorts of medicines and treatments that allow us to live and be productive with ailments that would have destroyed our lives a few generations ago.

Albuquerque sunsets. The coming together of optics, meteorology, and astronomy, the sunsets here are epically good. Add the color other the mountains opposite the setting sun and inspiration is never more than the end of the day away.

Sandia Mountain. A tribute to geology, the great shield, or half of a watermelon at sunset, it looks like home.

No duty is more urgent than that of returning thanks.

―James Allen

 

Better never means better for everyone… It always means worse, for some.

― Margaret Atwood

A couple of days ago I went through the HLL flux function –Riemann solver, and a small improvement (https://williamjrider.wordpress.com/2014/11/24/the-power-of-simple-questions-the-hll-flux/). Today I’ll report on another improvement, that doesn’t appear to improve much at all, but its worth considering. This is work in progress and right now its not yielding anything too exciting.

Never confuse movement with action.

― Ernest Hemingway

Again, I’ll focus on the HLL flux and attack the issue of the final flux function’s sign preservation. The first thing to address is the propriety of the entire idea. There is a nice (short) paper on a closely related topic [Linde]. The bottom line is that the initial data may have a certain sign convention, and the dynamics induced in the Riemann problem can change that. So before deciding how to apply the Riemann solver and whether that application is appropriate one needs to realize the impact of the internal structure.

The problem I noted that under some conditions the dissipation in the flux can change the sign of the computed flux (when the velocity is much less than the sound speed, and the change in the equations variables is large enough). If you look at the fluxes in the mass or energy equation, they are the product of the velocity multiplying a positive definite quantity. The mass flux is the velocity multiplying the density, and the energy flux is where , and are the density, total energy and the pressure. If the velocity always has a sign in the Riemann solution, the resulting flux inherits that sign convention.

The HLL flux is ;  –;  ;  where and . If we can have problems. This is particularly true is – is large.

Without deviation from the norm, progress is not possible.

― Frank Zappa

To attack the issue of whether the sign change is a problem and might be unphysical, I look at the dynamics within the Riemann solution. This can be easily computed using the linearized solution to the Lagrangian Riemann solution, where and are the Lagrangian wave speeds. If , and all have the same sign, the flux will have that sign. Given this background I test the HLL flux for compatibility with the established sign convention. If the sign convention is violated I do one of a couple of things: set or if and if . Then I test it.

Restlessness is discontent — and discontent is the first necessity of progress. Show me a thoroughly satisfied man — and I will show you a failure.

― Thomas A. Edison

The issue definitely shows up a lot in computations. I set up a challenging problem where the density is constant in the initial data, and there is a million-to-one pressure jump. This produces a shock and contact discontinuity moving to the right. The density jump is nearly six because the shock is so strong (). The HLL tends to smear the contact very strongly, and this is where the flux sign convention is violated.

We can see that an exact Riemann solver gives a sharp contact (the structure on the left side of the density peak). We also show the energy profile, which is also impacted by the idiosyncrasy discussed today.

With HLL we get a smeared out contact, especially to the left. None of the changes to HLL flux discussed above really make much of a difference either.

But knowing that things could be worse should not stop us from trying to make them better.

― Sheryl Sandberg

To do better is better than to be perfect.

― Toba Beta

[Linde] Linde, Timur, and Philip Roe. “On a mistaken notion of “proper upwinding”.” Journal of Computational Physics 142, no. 2 (1998): 611-614.

There’s no limit to how complicated things can get, on account of one thing always leading to another.

Yesterday I looked at a simple question regarding Riemann solvers. The conclusion of this brief investigation was that more examination is warranted. A large part of the impetus for the question comes from a recent research emphasis on positivity preserving discretizations. This means that quantities that are physically positive like density and energy are garuanteed to be positive in numerical solutions.

These have always focused on the variables being solved for. The fluxes used to build the solution procedure have been examined as producing physically-admissible solutions. I noticed that in least one case, the momentum flux, the flux should be positive-definite and its numerical approximation might not be. I’ll provide a little background on the thought process that got me to the question. The point I’ll make is much more exotic and esoteric in nature.

Back when I was in Los Alamos I did work on the nature of the truncation error using a technique called “modified equations”. This technique uses the venerated Taylor series expansion to describe the order of the approximation error in a numerical method. Unlike many analysis methods, which are limited to linear equations, the modified equation method gives results for nonlinear equations. One of things I noticed in the process of analysis explains a common problem with upwind differencing: entropy violating solutions to expansion waves often called rarefaction shocks.

For normal fluid dynamics shocks occur upon compression, and rarefactions occur upon expansion. If an expanding flow has a shock wave it is unphysical. In cases where wave speed used in upwinding goes through zero, the dissipation in upwinding goes to zero as the dissipation is directly proportional to the wave speed. This happens at “sonic points” where the velocity is equal to the sound speed, .

We can see what happens using the modified equation approach for upwinding. Take a general discretization for upwind differing in conservation form, . We use the upwind approximation . We plug all of this into the equations and expand in a Taylor series, .

When we plunge into the math, and simplify we get some really interesting results, . Here is the key to rarefaction shocks; when the wavespeed, is near zero, the dissipation is actually governed by a higher order term, .It is also notable that the dissipation aids the upwind dissipation for compressions, and thus shock waves. Anti-dissipation is a shock wave would be utterly catastrophic.

Usually fluids are convex, thus when the term in question is anti-dissipative. This is intrinsically unphysical. The dissipation from upwinding from the lower order term proportional to is not large enough to offset the anti-dissipation. This produces the conditions needed for a rarefactions shock wave. I’ve worried that these effects can consistently cause problems in solutions and undermine the entropy satisfying solutions. These terms were not considered in the basic theory of upwinding introduced by Harten, Hyman and Lax using modified equation analysis [HHL]. What makes matters worse is that the anti-dissipative terms will dominate in expansions when we take the upwind approximation to second-order.

The most complicated skill is to be simple.

[HLL] Harten, Amiram, James M. Hyman, Peter D. Lax, and Barbara Keyfitz. “On finite‐difference approximations and entropy conditions for shocks.” Communications on Pure and Applied Mathematics 29, no. 3 (1976): 297-322.

Questions are infinitely superior to answers.

― Dan Sullivan

The quality of research hinges upon questions and their quality. Surprisingly simple questions can lead to discovery. I’m not claiming discovery here, but I’ll start with what seems like a simple question and attack it.

There are some questions that shouldn’t be asked until a person is mature enough to appreciate the answers.

― Anne Bishop

Should the flux from a Riemann solver obey certain sign preserving qualities? By this I mean that under some conditions the numerical flux used to integrate hyperbolic conservation laws should obey a sign convention. I decided that it was a reasonable question, but it need to be bounded. I found a good starting point.

What’s a Riemann solver? If you know already go ahead and skip to the next paragraph. If you don’t here is a simple explanation: if you bring two slabs of material together at different conditions and then let them interact, the resulting solution can be idealized as a Riemann solution. For example if I have two blocks of gas separated by a thin diaphragm then remove it, the resulting structures are described by the Riemann solution. This is also known as a “shock tube”. Godunov showed us how to use the Riemann solution to construct a numerical method [Godunov].

For the Euler equations the momentum flux should be positive definite always (at least for gas dynamics). The density, and the pressure, are both positive. The remaining term is quadratic, thus the entire thing is positive. I reasoned that a negative flux would be unphysical. I worried that dissipative terms when added to the computation of the flux could make it negative.

Doing this generally is a challenge, but there is one Riemann solver that is simple and has a compact closed form, the HLL (for Harten-Lax-Van Leer) flux [HLL, HLLE]. This flux function is incredibly important because of its robustness and use as a “go to” flux for difficult problems [Quirk]. Its simplicity makes it a synch to implement. Its form is also so simple that it almost begs to be analyzed.

The basic form is  where  – , ,  is negative definite, and is positive definite bounding wave speeds. The subscripts and refer to the states to the left and right of the interface where the Riemann solution is sought. For the Euler equations these are always the acoustic eigenvalues associated with shocks and rarefactions in the solution. We can choose these so that and are as large as possible for the initial data. If all the wave speeds are moving to the left or right, the HLL formula simplifies quite readily to the “proper” upwinding, which is the selection of for rightward waves, and for leftward. Care must be taken to assure that any internal waves aren’t created in the Riemann solution that changes the directionality of the waves. If this is true, these changes must be incorporated in the estimates for and .

If we have a flux that will be positive definite, it isn’t too hard to see where we will have problems. If the combination of the wave speed sizes and the jump in the variable, is too large it may overwhelm the fluxes resulting in a negative value. For the case of the momentum flux this will happen in strong rarefactions where the velocities are opposite in sign. There is a common problem to solve that test this known colloquially as the “1-1-1” problem. Here the density and energy are set to one and the velocities are equal and opposite. This creates a strong rarefaction that nearly creates a vacuum.

With the HLL flux the computed momentum flux is negative at the center of the domain. I believe this has some negative impacts on the solution. The manifests itself as the “heating” at the center of the expansion in the energy solution, and the “soft” profile at the center of the velocity profile. Both are indicative of significantly too diffuse solution.

To counter this potentially “unphysical” response I detect the negative momentum flux and set the flux to zero overwriting the negative value. This changes the solution significantly by most notably removing the overheating from the center of the region, but leaving behind a small oscillation. The velocity field is now flat near the center of the domain while the changes in the density and pressure are subtler. With the original flux the density is slightly depressed near the center, with the modification the density is slightly elevated.

The scientist is not a person who gives the right answers, he’s one who asks the right questions.

― Claude Lévi-Strauss

I view these results are purely preliminary and promising. They need much more investigation to sort out their validity, and the appropriate means of modifying the flux. I believe that the present modification still yields an entropy-satisfying scheme. A couple of questions are worth thinking about moving forward. There are other cases where the sign of the HLL flux is demonstrably wrong, but not where the flux itself is signed in a definite way. This certainly happens with contract discontinuities, but existing methods exist to modify HLL to preserve contacts better [HLLEM]. Does this problem go beyond the case of contacts? Higher order truncation error terms produce both dissipative and anti-dissipative effect. How do these effects influence solution? In artificial viscosity, the method turns off dissipation in expansion. How would this type of approach work with Riemann solvers?

Judge a man by his questions rather than by his answers.

― Voltaire

[Godunov] Godunov, Sergei Konstantinovich. “A difference method for numerical calculation of discontinuous solutions of the equations of hydrodynamics.” Matematicheskii Sbornik 89, no. 3 (1959): 271-306.

[HLL] Harten, Amiram, Peter D. Lax, and Bram van Leer. “On upstream differencing and Godunov-type schemes for hyperbolic conservation laws.” SIAM review 25, no. 1 (1983): 35-61.

[HLLE] Einfeldt, Bernd. “On Godunov-type methods for gas dynamics.” SIAM Journal on Numerical Analysis 25, no. 2 (1988): 294-318.

[HLLEM] Einfeldt, Bernd, Claus-Dieter Munz, Philip L. Roe, and Björn Sjögreen. “On Godunov-type methods near low densities.” Journal of computational physics 92, no. 2 (1991): 273-295.

[Quirk] Quirk, James J. “A contribution to the great Riemann solver debate.” International Journal for Numerical Methods in Fluids 18, no. 6 (1994): 555-574.

Computers get better faster than anything else ever. A child’s PlayStation today is more powerful than a military supercomputer from 1996.

— Erik Brynjolfsson

For supercomputing to provide the value it promises for simulating phenomena, the methods in the codes must be convergent. The metric of weak scaling is utterly predicated on this being true. Despite its intrinsic importance to the actual relevance of high performance computing relatively little effort has been applied to making sure convergence is being achieved by codes. As such the work on supercomputing simply assumes that it happens, but does little to assure it. Actual convergence is largely an afterthought and receives little attention or work.

Don’t confuse symmetry with balance.

― Tom Robbins

Thus the necessary and sufficient conditions are basically ignored. This is one of the simplest examples of the lack of balance I experience every day. In modern computational science the belief that faster supercomputers are better and valuable has become closer to an article of religious faith than a well-crafted scientific endeavor. The sort of balanced, well-rounded efforts that brought scientific computing to maturity have been sacrificed for an orgy of self-importance. China has the world’s fastest computer and reflexively we think there is a problem.

I am not saying it is utterly useless. It can play video games.

—Unnamed Chinese Academy of Sciences Professor

At least the Chinese have someone who is smart enough to come to an honest conclusion about their computer! It could be a problem, or it might not be a problem at all. Everything that determines whether it’s a problem has little or nothing to do with the actual computer. The important thing is whether we, or they do the things necessary to assure that the computer is useful.

There is nothing quite so useless, as doing with great efficiency, something that should not be done at all.

― Peter F. Drucker

I know we are doing a generally terrible job of it. I worry a lot more about how much the Chinese are investing in the science going into the computer relative to us. The quote above probably means that they understand how bullshit the “fastest supercomputer” metric actually is. The signs are that they are taking action to fix this. This means much more than the actual computer.

Once upon a time applied mathematics was used to support the practical and effective use of computing. During the period of time from World War 2 to the early 1990’s applied math helped making scientific computing effective. It planted the seeds of the faith in faster computers we take for granted today. Over the past twenty or so years, this has waned and applied math has shrunk from impact. More and more computing simply works on autopilot to produce more computing power without doing what is important for utilizing this power effectively. Applied math is one of the fields necessary to do this.

Computer science is one of the worst things that ever happened to either computers or to science.

— Neil Gershenfeld

While necessary applied math isn’t sufficient. Sufficiency is achieved when the elements are applied together with science. The science of computing cannot remain fixed because computing is changing the physical scales we can access, and the fundamental nature of the questions we ask. The codes of twenty years ago can’t simply be used in the same way. It is much more than rewriting them or just refining a mesh. The physics in the codes needs to change to reflect the differences.

a huge simulation of the ‘exact’ equations…may be no more enlightening than the experiments that led to those equations…Solving the equations leads to a deeper understanding of the model itself. Solving is not the same as simulating.

—Philip Holmes

For example we ought to be getting ensembles of calculations from different initial conditions instead of single well-posed initial value problems. This is just like experiments, no two are really identical, and computations should be the same. In some cases this can lead to huge systematic changes in solutions. Reality produces vastly different outcomes from ostensibly identical initial conditions. This makes people really uncomfortable, but science and simulations could provide immense insight into this. Our current attitudes are holding us back from realizing this.

Single calculations will never be “the right answer” for hard problems.

—Tim Trucano

Right now this makes scientists immensely uncomfortable because the necessary science isn’t in place. Developing understanding of this physically and mathematically is needed for confidence. It is also needed to get the most out of the computers we are buying. Instead we simply value the mere existence of these computers and demonstrate their utility through a sequence of computing stunts of virtually no scientific value.

To me, this is not an information age. It’s an age of networked intelligence, it’s an age of vast promise.

—Don Tapscott

Beyond the science, the whole basis of computing is still grounded in models of computing from twenty or thirty years ago (i.e., mainframes). While computing has undergone a massive transformation and become a transformational social technology scientific computing has remained stuck in the past. Science is only beginning to touch the possibilities of computing. In many ways the high performance computing world is even further behind than much of the rest of the scientific world in utilizing of the potential computing as it exists today. 

All these computers, all these handhelds, all these cell phones, all these laptops, all these servers — what we’re getting out of all these connections is we’re getting one machine. … We’re constructing a single, global machine.

—Kevin Kelly

A chief culprit is the combination of the industry and its government partners who remain tied to the same stale model for two or three decades. At the core the cost has been intellectual vitality. The implicit assumption of convergence, and the lack of deeper intellectual investment in new ideas has conspired to strand the community in the past. The annual Supercomputing conference is a monument to this self-imposed mediocrity. It’s a trade show through and through, and in terms of technical content a truly terrible meeting (I remember pissing the Livermore CTO off when pointing this out).

You can’t solve a problem with the management of technology with more technology.

—Bill Joy

The opportunities provided by the modern world of computing are immense. Scientific computing should be at the cutting edge, and instead remains stranded in the past. The reason is the lack of intellectual vitality that a balanced effort would provide. The starting point was a failure to attend to the necessary and sufficient efforts to assure success. Too much effort is put toward making “big iron” function, and too little effort in making it useful.

We’ve got 21st century technology and speed colliding head-on with 20th and 19th century institutions, rules and cultures.

— Amory Lovins

 Mathematics is the art of explanation.

― Paul Lockhart

In projects I work on mathematics plays a key role. Too often the math doesn’t provide nearly enough impact because it can’t handle the complexity of applications. One of the big issues is the proper role of math in the computational projects. The more applied the project gets, the less capacity math has to impact it. Things simply shouldn’t be this way. Math should always be able to compliment a project.

This begs a set of questions to consider. For example what sort of proofs are useful? My contention is that proofs need to show explanatory or constructive power.  What do I mean by this?

 

[…] provability is a weaker notion than truth

― Douglas R. Hofstadter

A proof that is explanatory gives conditions that describe the results achieved in computation. Convergence rates observed in computations are often well described by mathematical theory. When a code gives results of a certain convergence rate, a mathematical proof that explains why is welcome and beneficial. It is even better if it gives conditions where things break down, or get better. The key is we see something in actual computations, and math provides a structured, logical and defensible explanation of what we see.

How is it that there are so many minds that are incapable of understanding mathematics? … the skeleton of our understanding, …

― Henri Poincaré

Constructive power is similar, but even better. Here the mathematics gives us the power to build new methods, improved algorithms or better performance. It provides concrete direction to the code and the capacity to make well-structured decisions. With theory behind us we can define methods that can successfully improve our solutions. With mathematics behind us, codes can make huge strides forward. Without mathematics it is often a matter or trial and error.

Too often mathematics is done that simply assumes that others are “smart” enough to squeeze utility from the work. A darker interpretation of this attitude is that people who don’t care if it is useful, or used. I can’t tolerate that attitude. This isn’t to say that math without application shouldn’t be done, but rather it shouldn’t seek support from computational science.