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.

Trust is a big word. 

The whole concept of trust or being trusted is a cornerstone of civilization, and presently our society has a frightfully short supply of it.  The crisis in trust has been forty years in the making and its side effects are profound and wide reaching.  I’m going to talk about one of these impacts as it pertains to the conduct of science.  To say that the public doesn’t trust science or scientists is an understatement even though polls would count scientists as one of the more trustworthy professions.  The cost to our society is immense with greater expense, less achievement, and ultimately horrible wastes of money, lives and opportunity.  All of this tends to create a viscous cycle that simply undermines trust further, and reinforces the attitudes that caused the problems in the first place.

Let us be clear, the cost of the lack of trust we have is massive.  It eats away at the very fabric of society like a corrosive substance.  Instead of applying trust to the conduct of activities, we demand checks and rechecks and accounting and progress reports all to provide the proof that business is being conducted in a trustworthy manner.  The lack of trust itself acts to corrode the environment and lead to an even greater degree of double-checks.  It is a classic death-spiral.  If the flow of good faith isn’t restored, when will this end?

As we look backwards in time, the early to mid 70’s seem to be the origin of this wholesale change in society’s attitudes.  Perhaps earlier during the 60’s the movement against the “establishment” laid the groundwork, with a general sense of widespread dishonesty and distortion of facts by the government in the conduct of the Vietnam War (a concomitant conflict as part of the Cold War).  The bellwether event of the 70’s was the Watergate scandal on the systematic, criminal activity in the White House ending with President Nixon’s resignation.  The unwinding of trust continued with the energy shock, Love Canal, Three Mile Island all etched on the National Psyche.  Science looms large in each of these areas and became part of the American experience of disappointment and mistrust.  People wanted accountability from their government and the science it funded.  These failures were viewed as a waste and embarrassment, and the system had to be changed.  So, driven by this the public and by proxy Congress demanded change.  Trust in our institutions and science as one of them had been revoked.

Where does this leave use today?  We have put numerous systems into place that enforce accountability.  The problem is that the accountability itself is not accountable and our laws demand that we literally spend $10 to save $1.  Because of all the issues with trust, I probably cost twice as much as I should to the taxpayers, and this isn’t the worst of it.  The work I do isn’t daring enough, and I don’t have nearly as much freedom as I should.  Ironically not enough responsibility is required of me either.   This undermines the value of what I do even more.  All this accountability and bean counting and progress report writing, and conduct of operations and training I do is a terrible return on investment for taxpayers.  In the end, all these things are their fault for their systematic lack of trust in the system and the cost of making sure I’m not wasting money by wasting a lot of money.

Scientists are terrified of failure and do not take risks.  Without the risk, much of the reward is gone.  In a recent address Bill Press noted the massive return on the investment in research associated with the Human Genome Project (on the order of 200:1).  This is true enough, but the government, and business can’t pick the winners that well.  We have to fund a lot of research that never pans out to get one of these massive payouts.  The reality is that we might have had to fund 30-100 times as much work to get the payout of the Human Genome Project.  This undermines the return on investment, but if you don’t fund all the research you never get the winner.  It is much like the rule of venture capital; you have to fund a lot of dogs to get that one winner.  The same applies to science.

Americans seem to be convinced we can manage ourselves into a sure thing.  We can’t, but no one, especially a Congressman likes to be told this simple truth.  Sometimes the best things you can do is put your trust in others and simply support good work done by good people.  Sometimes it works out, sometimes it doesn’t.  When it doesn’t, it doesn’t mean the people are bad, or the work is bad, it means they weren’t lucky enough to choose the thing that wins.  It isn’t fraud or incompetence either; its just bad luck.   

Simply put, success, learning and achievement depends completely on failures.  We must learn to accept outright failure as the glorious foundation of upon which success is built.  Ironic yes, but it’s the trust.  We must allow ourselves to fail in order to have the chance of success.

The people who win Nobel prizes are not always the best; they are just the luckiest.  Most of them are really good scientists, but lots of equally good or better scientists never get the fame, mostly because they weren’t lucky enough to be at the right place at the right time.  The problem is that won’t do that Nobel Prize-Winning work without risk and without funding a lot of dogs.  Realize that the Nobel Prize is a deeply lagging indicator, and the United States should start to see a deep falloff in our accumulation of this prize in the decades to come.  This future failure as a society has its origin in trust, or more properly the lack of it.

Lack of trust may be one way we can easily capture the malaise we find ourselves in.  To get out of this we need to go out and fail, and fail some more.  We might call it “glorious failure” because in its wake the seed of success are planted, and given the environment that allows you to fail once more success in the truest sense can be achieved.  To get to the point where we can allow this requires courage, faith in humanity and trust.

The core idea here is that adaptive mesh technology in codes seems to encourage a certain level of outright sloppiness because of the adaptivity engendering a false sense of confidence.

An interesting (and generally good) development in computation is the increasingly pervasive availability of mesh adaptivity particularly in computational fluid mechanics.  My comments are not only relevant to CFD although they might be the worst abusers.  Of course, things like verification are most often done in CFD, so it might all work out in the wash.  Hand-in-hand with the use of mesh adaptivity is a seeming laxness in attitudes toward solution quality.  In other words, adaptive meshes seem to fill people with the belief that they are inoculated from worrying about the quality of their calculations.  It is a bit ironic considering that the users of adaptive meshes are exhibiting an implicit commitment to mesh converged solutions, but often avoid doing any of the actions that might confirm this.  There seems to be an innate belief that the solution is sufficiently high quality if the mesh is refined enough.  They seem to be ignoring some of the deeper dangers associated with adaptivity.  In fact, an adaptive mesh is provides a substantially greater risk to solution quality and even greater care is necessary.

The first and most common incarnation of a misbegotten belief in intrinsic quality with adaptivity involves mesh sensitivity, or poor man’s verification.  The common statement is that we refined the mesh and the answer didn’t change, thus the mesh is fine enough.  This might be true, or it might simply indicate a stalled stagnant solution.  Without assessing the actual convergence of the solution towards a mesh independent answer these two situations cannot be distinguished easily from one another.  The adaptivity also add the danger that should the mesh refinement be chosen poorly, the mesh adaptive process may itself be causing the solution to stagnate.  I’ve actually seen this in the case where the problem is focused on a single region in the flow, and we bias the mesh refinement toward that region while ignoring the rest.   Instead of getting a better answer where we think we care about the result we actually hurt the quality by ignoring important parts of the solution that influence the result we care about.  For some people this may be counter-intuitive, but the honest truth is that the quality of the solution where we care about it is not only a function of the solution in that particular location.  The way to avoid this problem is simple enough, check the results for convergence and make certain that the solution is simply not stagnating.  It also may not be a good idea to de-refine the solution where something important is happening even if we don’t care about the details in that location.

The secondary issue with adaptivity relates to the overall attitude towards solution quality.   It has been said that adaptivity actually makes all verification unnecessary.  This is simply wrong-headed; adaptivity actually makes verification more necessary because the mesh selection procedure can be thought of as an additional approximation.  One is using the mesh selection to approximate the effect of having a fine mesh everywhere.  Adaptive code users often seem to implicitly expect that they are getting the fine grid everywhere solution at a discount by using adaptivity.  This might be approximately true under ideal circumstances, but when part of the mesh is selected to not be refined, one expects the solution to suffer.  One must also remember that the criteria for selecting the refined mesh (and where it is at lower resolution) is not entirely perfect, often basis on heuristics.  We need to check whether the degradation is significant.  The check for degradation is the verification process.  The faith placed in adaptivity is to do this where the solution is not important.  This faith can be seriously misplaced, and the entire procedure can go off the rails.  A large part of the cure for this is systematic code verification where the adaptivity is tested.

The second issue is the change in the discretization due to the variation in the mesh density.  One needs to make sure that the differencing of the equations in the presence of mesh adaption does not upset the basic properties of the original solution procedure.  Generally, one expects that the accuracy of the solution will be equal to the unadapted case AT BEST.  Usually the differencing in the face of adaption is degraded in terms of accuracy.  Again, the quality of the code and solution needs to be extensively tested.  In fact, the adaption places a greater burden for the testing of quality rather than lessening it as many assume.

Finally, I can speak of the upside of adaptivity.  Computational practitioners should consider adaptivity as providing two chief benefits: you can get refined meshes with less cost (but greater danger), and you can get solutions at multiple resolutions.  If you have done a sufficient job testing the quality of your code, then the refined mesh solutions are a massive benefit.  With solutions on multiple meshes you can test and estimate numerical errors more easily than standard approaches. 

In summary, adaptive meshes are wonderful techniques, but rather than lessen the burden on the computational code and analysts to prove quality, it increases the burden.  This is largely due to the greater complexity of adaptive mesh codes, and the potential to cut corners in the implementation.    As with most things, adaptivity is not a something for nothing technique, with great power comes, great responsibility! 

Use adaptivity, use it wisely and trust, but verify!

There are a lot of numerical methods out there and it might be hard to decide which one is right for your purpose.  A large part of the decision should be determined by the basic properties of the numerical method.  These properties can be determined by some basic analysis techniques.  I highly recommend doing these analyses personally rather than relying on what the authors of papers provide you.  A good place to start is reproducing the analysis found in textbooks, then research papers.  It provides the template to really learn how to do this.  These analyses have a number of benefits that I’ll outline below.

In the writing I will assume you’re pretty well versed in numerical methods, and you’ve had advanced mathematics classes at least an undergraduate level (and this will miss cause most of this is graduate level stuff).  On the other hand, why dumb it down? There is too much of that these days!

The classical starting point for numerical analysis is round-off error, which had importance back in the day when computers were crude.  Round-off error could be a real practical problem and even simple problems could be corrupted by the manner in which numbers were represented.  The analysis of Gaussian elimination is the archetype.  These issues have faded into the woodwork, but are staged to make a return to prominence as computers become less reliable.  This lack of reliability is related to the end of Moore’s law, and the physical limits of our present computing engineering.  As circuits become so small that the size of an atom becomes substantial, the difference between encoding a zero and one becomes fuzzy.  Cosmic rays can cause issues, and the roundoff problems will be back from the grave. 

Another topic you might cover in undergraduate classes is interpolation error.  This is another closely related topic.  In fact many numerical methods are designed via interpolation.  The interpolation problem is multifaceted

The most fundamental aspect of numerical analysis is the stability of an algorithm, and the simplest thing to analyze is the solution of ordinary differential equations.  The analysis is as simple as it gets, and is a good starting point.  Furthermore many algorithms can be split into two pieces, time and space differencing.  The ODE analysis can give results to the temporal part, and introduces the basic concepts. Like many of the basic analysis techniques, the analysis only formally applies to linear methods and models.  Below, a method that can cope with nonlineariy will be given (modified equation analysis).   The basic techniques can be found in many book, but Ascher and Petzold’s SIAM book is my favorite.

For partial differential equations Von Neumann stability analysis is the gold standard.  It was first introduced in the late 40’s at a lecture in Los Alamos, and the report on the topic was classified for decades.  Nevertheless Von Neumann shared his method with others on the outside and it rapidly spread to become the standard.  It was part of the paper published with Von Neumann that introduced artificial viscosity.  It is also called Fourier analysis because the technique involves replacing the spatial variables with a complex Fourier series.  Aside for this the conduct of Von Nuemann’s method is almost identical to ODE analysis, but produces a richer set of outcomes because the space and time aspects are characterized.  Trunctation error estimates, dissipation and dispersion (phase or propagation) aspects come out of the analysis.    Durran’s book on numerical geophysics contains a good introduction or Strikwerda’s numerical analysis book.

Pure dispersion analysis is closely related.  This most clearly can be applied to the pure spatial operator and used similarly to ODE analysis.  Unlike ODE analysis it also involves a Fourier series expansion, but only in space.  It is a simple, but limited alternative to Von Neumann’s method.

Modified equation analysis has less power than any of the methods above, but formally applies to nonlinear equations and importantly to nonlinear methods.  While it is limited in scope, it carries powerful intuitive capability.  One expands the method in terms of Taylor series, and looks at the remainder.  The remainder always involves more complex, higher order differential equations than the original equation.  For example, modified equations provided a very clear picture of implicit numerical diffusion arising from upwind differencing.  One derives the differential equation that you more closely approximate than the original equation, and in the case of upwind differncing you approximate the original advection law plus a diffusion term, and the solution looks like this.  This was important in the theoretical development because it showed how to connect numerical solutions to entropy, which determine what solutions are physical.

Energy methods are a form of analysis that I have little experience with.  I know there are some tests and conditions that exist with the finite element community, but I can’t personally vouch for the utility of them.

Symbolic arithmetic makes it easy to do the analysis.  The course I took was to look at a very simple method (e.g., upwind differencing), and analyze it by hand.  I then took on a more complex method, but rapidly discovered that the analysis is terribly tedious and error prone.  For me, Mathematica came to the rescue!  I could do simple methods easily, and extend to more complicated methods, and still more complicated methods.  You can start to analyze systems of equations or solutions in multiple dimensions, or multi-level methods.  At some point you can push current symbolic capabilities to the breaking point, but by then you’re examining quite exotic methods.  The point is that you can do a great deal with relative ease.  It also really makes you appreciate the skill and patience of those that successfully analyzed complex schemes by hand!

Here are the reasons in no particular order:

1. You can do it easily, so there really isn’t an excuse for not.  If you have the basic analysis at hand, it can be reused to understand a particular case you’re interested in.
2. You learn by actually doing, not simply reading, not by simply coding and implementing (although that part of it is recommended too).  Holistically speaking one really knows their topic when you’ve read about, thought about, analyzed personally and implemented personally.  At this point you’ve successfully learned.  Learning is the heart of excellence.  Learning is the heart of expertise.
3. You’ll understand your calculations behave in ways you never antisipated.
4. You’ll start to see how to improve things and you’ll be equiped to test, understand and prove that your improvements are better.
5. Your view of numerical methods will become nuanced, and you’ll be a better user of them.
6. The difficulty of solving differential equations will become clear, and your appreciation for progress in the field will be more complete.
7. You will get a feel for numerical stability, dispersion, dissipation and accuracy.  This understanding will allow you to diagnose the nature of your simulations like a boss.
8. Your simulations will start to tell you new things that you never appreciated or even saw before.
9. You will learn something new almost every time you analyze a new method, or analyze an old method in a new way.

10. It will push you to learn new math, and expand your knowledge to areas you might not have thought you needed.

11. Your curiousity will be piqued.

12. You won’t rely on the published literature for knowledge.  It’s the give a man a fish and you feed him, teach him to fish and you feed him for life…

The greatest thing about the human mind is the ability to detect patterns.  This pattern detection and connection capability is in essence the holy grail of artificial intelligence.  I’ve noticed such a pattern across a broad spectrum of technical endeavors associated with the 1-norm.  The 1-norms latest foray into my consciousness comes from “compressed sensing,” but it resonates with a bunch of other things.  These patterns are always trying to tell us, “there is something here worth paying attention to”.

This is all the more amazing since the pattern detection capability that humans have is probably more related to our staying alive as nomadic hunters, 10’s of thousands of years ago.  In those days the pattern would say, “there’s something to eat” or “something is over there that might kill me” or “here is a good place to sleep” and so on.  Now the same wiring is providing increased acuity applied toward abstract constructs like functional spaces. Go figure.

I’m trying to write something up about compressed sensing and related fields, but don’t feel up to the task quite yet.  So instead of nursing that as a bonus this week I’ll just give my brain dump of what is intriguing me, and what tendrils are connected to other areas of science that are perhaps far from compressed sensing at first blush.

1. L1 is the sharpest and least convex norm.
2. “When a traveler reaches a fork in the road, the ℓ1 -norm tells him to take either one way or the other, but the ℓ2 -norm instructs him to head off into the bushes. ” – John F. Claerbout and Francis Muir, 1973. I If you think about the rest of the post, it might be clear what this means.
3. Error and convergence for discontinuous (hyperbolic) problems should be measured in the L1 norm.  The L1 norm is very closely related to compactness arguments and the total variation norm.  Total variation concepts have been essential in numerical approximations to hyperbolic conservation equations, and image processing.  At the close of this post it might be worth keeping this firmly in mind.
4. The least squares problem is ubiquitous in mathematics, physics and engineering largely because it is so easy to compute.  L2 is related to energy, which adds to the appeal.  People apply L2 almost without thought as it is built into numerous computing packages and it is an introductory topic.  This ubiquity is unfortunate because of all the bad things about L2 minimization framework.  Among these bad things are the numerous unstated assumptions that come along for the ride and aren’t even known (or acknowledged) by those that use it. In many applications L1 is more appropriate and useful, but computing solutions to the L1 minimization is inherently nonlinear and there aren’t any non-trivial algorithms.  Trivial introductory algorithms exist for L2.  Some minimization is better than none, but too much begins and ends with least squares.
5. Until recently I pondered what sort of math takes place in fractional “norms”.  I’ve received a partial answer with the compressed sensing work.  Little “L” norms aren’t norms because of lack of convexity, but can be computed.  L0 tells one how sparse a set is, that is it measures all the non-zero entries.  Because of the lack of convexity it isn’t very computable (NP-hard!).  The cool thing is that with “high probability” minimizing in L1 can give the answer to the same question.  This is the key to the utility of compressed sensing.
6. The L1 norm is related to robust statistics.  In other words, if you construct estimates using L1 minimization you are not susceptible to outliers in the data.  If instead you do the standard least squares estimator (L2), you are very susceptible to outliers in the data, that is if you have a corrupt data point and do a L2 fit, your result can be influenced greatly, L1 will cope by ignoring the outlier.  It turns out that most of the outlier detection schemes are predicated on assumptions from least squares, and assumptions associated with Gaussian statistics.
7. I found that a L1 fit to local data was a nice way of differencing hyperbolic PDEs.  It gave a much-improved solution compared to L2.  When in doubt my suggestion is solve the problem using L1 minimization first.  You’ll probably have to do it outside of MS Excel!
8. In analyzing the convergence of numerical approximations to PDE (i.e., solution verification), the L1 norm gives by far the best solutions.  If you were to use on norm to fit your data I believe L1 is the best.
9. Moving onto the ideas in the frame of compressed sensing, I came across the LASSO, which is a way of regularizing least squares minimization (which you might want or need to do if your system is under-determined or terribly conditioned).  The classical regularization is Tikhonov’s where a L2 penalty term is added to the matrix you solve (basically adding a term to the diagonal).  LASSO is instead a L1 based penalty.  Like most L1 things it works better once you solve the system.  There is more, and this is where things start to get really really cool.
10. LASSO is really a way to select models.  Usually the regularization as discussed in the previous point uses a small penalty, because you want the problem you solve to be very close to the original problem.  What if instead you make the penalty large?  With the L1 regularization you start to find that the minimized solution starts to set most of the solution to zero.  Ultimately as the penalty becomes large enough everything is zero except a single value.  This usually happens in a well-defined sequence and the ordering compared to penalty size tells you what variables are most important to the data.  You can then choose how complex you want to your model to be and which variables to keep and which to throw away.  I’m playing around with this concept right now.
11. Compressed sensing arose from signal processing work using wavelets.  A couple of techniques arose “matching pursuit” basically a greedy algorithm to find out what basis was the best representation of an image, and “basis pursuit” which is an all-at-once algorithm that finds the sparsest representation.  A certain version of basis pursuit that applies to noisy data, “basis pursuit denoising (BPDN)” is basically identical to LASSO.  The big difference is that LASSO is generally applied to over-determined problems and BPDN is applied to under-determined problems.  Both methods apply the magic of the L1 norm to do the selections.  These pursuits are just another model selection problem.
12. Finally compressed sensing can be discussed albeit briefly.    This concept arose from basis pursuit and has a phenomenal mathematical basis from the assurances associated with using L1 to get the L0 solution of the sparsest basis.  Much is made of the RIP, the restricted isometry property, which characterizes systems that compressed sensing can tackle although it has been noted that the theory is a bit pessimistic compared to what can be achieved in practice.  It looks like an awesome bit of math that has massive implications on signal processing, graphics, and data analysis.

I came across the area from a blog post on the most influential papers in statistics in the last decade.  David Donoho’s paper introducing the concept has about 8000 citations in less than 10 years!  I met David last year at a workshop, and had no idea about why he was so well known, he just gave a really nice talk on reproducible software in an educational setting.

If you really want an introduction to compressed sensing read Terry Tao’s wonderful, wonderful post (http://terrytao.wordpress.com/2007/04/13/compressed-sensing-and-single-pixel-cameras/) on the single pixel camera.  His math papers on related topics are pretty great too!

I hope this was interesting and perhaps inspiring.  There is cool new math out there, and better yet it is powerful and useful.