ACDL Logo Research : People : Publications: Seminars MIT Logo

Functional Outputs and Polynomial Certificates
for Partial Differential Equations
 

Students: A.M. Budge, H. Ciria, N. Pares, and J. Wong

Faculty: J. Peraire

Collaborators: J. Bonet (Univ. of Wales, Swansea) and A. Huerta (UPC, Barcelona)

With the availability of commodity computer hardware and software, the computation of solutions to, at least the simplest, partial differential equations has become a seemingly effortless task. Yet, this feeling of overconfidence is easily shattered when we are faced with a new problem and its corresponding computer solution. Indeed, there are three essential questions that must be answered before a simulation result can be trusted: Does the mathematical model represent the relevant phenomena? Do we have an algorithm that produces a suitable numerical approximation to the solution of the mathematical model? Does the software actually implement the solution algorithm?

These questions are certainly not new and over the years much effort has been spent in trying to provide satisfactory answers. Sophisticated mathematical models incorporating deep physical understanding, adaptive algorithms using state of the art a-posteriori error estimation, and suites of benchmark tests with known and trusted solutions are only a few examples. We claim that despite all these efforts the real situation, even for the simplest problems, is inadequate to meet many of todayís needs.

In addition to the questions posed above there is an additional question which surfaces in real world applications. Even if you believe that the result of your simulation is correct, how do you guarantee it? That is, how do you prove the correctness of your claim to the decision maker, the customer, or even in a court of law?

If simulation results are to be useful to support important decisions, a higher degree of confidence is required. Our observations of engineering practice indicate that integrated quantities such as forces and total fluxes are frequently queried quantitative outputs from field simulations and that design and analysis does not always require the full precision available.

Our work in recent years has lead us to the idea of computational certificates for partial differential equations. The use of certificates in numerical analysis is not new. In convex optimization feasible solutions for the primal and dual problems are guaranteed to be bound the actual optimum. In dynamics systems the existence of a Lyapunov function guarantees the stability of the trajectories, and in polynomial minimization, the existence of a sum of squares decomposition guarantees the positivity of a given polynomial. We say that the actual feasible solutions of the primal and dual problem, the Lyapunov function (typically polynomial), or the coefficients of the sum of squares decomposition of a given polynomial, are certificates that guarantee the correctness of the claim being made. All these certificates on the other hand share some common features that make them very attractive in practice. First, they can be used to prove correctness in an unambiguous manner. Second, exercising the certificate is simpler and in any case, much simpler than finding it. Third, the certificate stands alone and it usefulness does not depend on the details of the algorithm used to determine it. Fourth, and last, the stronger the claim the longer the certificate. This last feature is not universally true but generally so. For instance, a very tight Lyapunov function will often have a longer description than a very conservative one.

To our knowledge, the use of computational certificates for partial differential equations is far less common. In this context, a certificate would be required to proof the correctness of a given claim, given that the solution of the PDE may not be well behaved, there may not be similar solutions available to compare, access to the computer code used to generate the solution is not generally available and in fact may not exist.

The goal of this project is to develop the necessary methodology to produce certificates for linear functional outputs of partial differential equations. Work to date includes the linear elasticity equations, the convection-diffusion-reaction equation, the non-linear equations of limit state analysis and the Stokes flow equations.

The starting point for our methodology is typically a finite element solution which is suitably post-processed to yield the appropriate certificate. However, alternative formulations based directly on optimization which bypass the finite element solution are also used.

Selected Presentations:

Selected References: