UK Nonlinear News, November 1999

Foundations of Computational Mathematics

Oxford University, 18-28 July 1999

By Chris Budd (Bath) and Andrew Stuart (Warwick)

The 3rd `Foundations of Computational Mathematics' (FoCM) meeting took place at Oxford University between July 18th and July 28th 1999. Previous meetings have been at Park City, Utah (1995) and Rio de Janiero (1997) and there was a special session at MSRI devoted to FoCM related topics at MSRI (Berkeley) in the fall on 1998. The original intention of the FoCM meetings was to provide a forum for the exchange of ideas concerned with foundational issues in real number algorithms; in particular to recognize, and attempt to remedy, the fact that Numerical Analysis as a field does not have the clear underpinnings of theoretical Computer Science. Whilst this issue has remained central to the mission of the meetings, it is true to say that that they are now much broader in scope. Indeed, the FoCM meetings now serve to show the central role played by computational methods in many fields of both pure and applied mathematics.

The success of the meetings, and more generally of the aims of the FoCM Council, can be gauged by the number of participants, which at Oxford exceeded 300, the broad range of topics covered and the diverse range of expertise of the participants, and the introduction of a new FoCM Journal, edited by Mike Shub, of IBM, Yorktown Heights. An attractive feature of the FoCM meetings is their format which mixes plenary talks with many diverse workshops. These workshops are each organised by experts in the specific areas covered, and have both specialist talks describing ground breaking research and semi-plenary talks which are deliberately designed to be accessible and of interest to participants whose expertise lies in different areas. This all encourages a splendid cross-fertilisation of ideas.

The scope of research topics covered can be appreciated by considering the 14 Workshop Themes around which the meeting was organized: Analysis and approximation of infinite-dimensional problems; Approximation theory; Complexity theory, real machines and homotopy; Computational dynamics; Relations to computer science; Computational geometry and topology; Multiresolution; computer vision and PDEs; Optimization; Stochastic computation; Symbolic algebra and analysis; Computational number theory; Geometric integration and computation on manifolds; Information-based complexity and Numerical linear algebra. This range of topics is suggestive of the tension that may be felt underlying FoCM, namely that between the detailed study of complexity, efficiency and accuracy for real number algorithms applied to a few basic model problems at the core of the subject, and the reality of attempting to make objective statements about such issues for algorithms applied to exceedingly complex problems, such as those arising in applications modelled by PDEs. This tension is healthy and undoubtedly one of the major strengths of the FoCM meetings; bringing together a cross-section of computational mathematicians who might not otherwise naturally meet has challenged many, from foundational to applied researchers, to re-evaluate their research in the light of the work of others.

The plenary speakers were chosen to complement the Workshop themes selected by the organizers. In the area of complexity were talks by Jean Pierre Dedieu (Touluse), Jooz Heintz (Cantabria) and Erich Novak (Erlangen). Dedieu analysed Newtons method for nonlinear equations, in particular polynomials, and stated some interesting results, proved by techniques from dynamical systems, on the existence of universal sets of starting points guaranteed to be in the basin of attraction of all (normalized) polynomials of a given degree. Heintz talked about complexity issues in computational algebraic geometry. Novak discussed the tractability (meaning polynomial time in dimension), or otherwise, of algorithms for high dimensional numerical integration, using both worst-case and average case (with respect to Wiener measure) analyses. Leslie Valiant (Harvard) talked about cognitive computation, and aspects of the underlying logical structures. The fields of computational geometry and number theory were represented by David Epstein (Warwick) and Bjorn Poonen (Berkeley). Epstien gave an overview of computational algorithms for decidability questions arising in hyperbolic groups. Poonen discussed the incompletely understood problem of whether an algorithm can be found to determine whether a curve defined by an equation with co-efficients in Q has a point with co-ordinates in Q.

In the areas of dynamical systems and stochastic processes talks were given by Andrew Stuart (Warwick) and Denis Talay (INRIA). Stuart discussed the extent to which long-time averages are accurately reproducible in simulations of ODEs and stochastic differential equations (SDEs) and Talay gave an overview of both pathwise (strong) and weak approximation properties of numerical methods for SDEs. The field of PDEs was addressed by John Ball (Oxford), Robert McLachlan (Massey) and Rolf Rannacher (Heidelberg). Ball discussed the implications of the prevalence of singular solutions and microstructural solutions, in various applications of the calculus of variations such as elasticity, for the design of computational algorithms. McLachlan showed how the analysis of structure-preserving algorithms for conservative PDEs can be used to study stability issues for a variety of problems of importance in applications. Rannacher showed how a posteriori error estimates can be developed for finite element methods applied to fluid flow problems, and used them to design mesh adaptation strategies.

A variety of issues associated with vision and graphics were covered by the talks of Ingrid Daubechies (Princeton), Peter Olver (Minnesota) and Guillermo Sapiro (Minnesota). Daubechies looked at the construction of subdivision schemes, for the generation of curves and surfaces from irregular data sets, and how to construct smooth limit surfaces by this technique. Olver showed how deep ideas in pure mathematics, specifically differential geometry and the Cartan theory of moving frames, could be used in the applied problem of image processing by using differential invariants as a method of recognising objects in the image. Sapiro showed how nonlinear diffusion equations can be usefully used in image processing for problems such as edge detection; they offer an alternative to the usual methods of digital filtering. He surveyed the important theoretical developments in PDEs resulting from this viewpoint and showed some simple examples which elucidated the applicability of the technique.

The fields of numerical linear algebra and optimization were addressed in talks by Alan Edelman (MIT), Nick Higham (Manchester) and Jorge Nocedal (Argonne). Edelman gave a geometrical interpretation of the surfaces in four dimensional space which correspond to different types of 2 x 2 matrices (for example matrices with multiple eigenvalues) and argued that this sort of information would be needed for the next generation of software for finding eigenvalues. Higham looked at the existence of solutions of nonlinear matrix equations and the associated quadratic eigenvalue problem. Nocedal surveyed the field of nonlinear optimization and, in particular, the use of interior point methods.

There were two evening forums which were meant to provoke discussion. The first questioned the future of numerical analysis as a subject and came to the conclusion that it would continue to thrive and to surprise us. The second, chaired by Nick Trefethen (Oxford) looked at issues related to Computation, Complexity Theory and Artificial intelligence and was a very wide ranging discussion with presentations (and comment) from Roger Penrose (Oxford), Steve Smale (Hong Kong) and Richard Brent (Oxford).

Overall the meeting was a great success and firmly established many links between the various areas where computational mathematics is used, hopefully surprising many by the breadth of its applications and the depth of its underlying theory. Many thanks are due to Arieh Iserles, Endre Suli and Bette Byrne and all the staff at OUCL for working so hard to make the FoCM meeting so intellectually stimulating and smoothly run. We look forward to the next meeting.

<< Move to UK Nonlinear News Issue Eighteen Index Page (November 1999).
Last Updated: 29th October 1999.