Main navigation | Main content

HOME » PROGRAMS/ACTIVITIES » Annual Thematic Program

PROGRAMS/ACTIVITIES

Annual Thematic Program »Postdoctoral Fellowships »Hot Topics and Special »Public Lectures »New Directions »PI Programs »Industrial Programs »Seminars »Be an Organizer »Annual »Hot Topics »PI Summer »PI Conference »Applying to Participate »

Talk Abstract

Convergence Proofs for Numerical Software

Convergence Proofs for Numerical Software

The study of the running times of algorithms in computer science can
be broken down into two broad types: worst-case analyses and average-case
analyses. For many problems this distinction is very important as
the orders of magnitude (in terms of some measure *N* of problem size)
of the running times may differ significantly in each case, providing
useful information about the merits of the algorithm.

A similar situation occurs for certain real number algorithms which are used in commonly available software in numerical analysis although, in the worst case, these algorithms may fail completely. Analysis of real number algorithms from this perspective was initiated by Smale in his pioneering study of Newton's method. Subsequent work in the area of linear algebra was undertaken by Demmel and has been elaborated on by many others. This work on Newton's method and in linear algebra will be reviewed; then recent work by the author and Harbir Lamba concerning similar analysis for commonly used ODE software packages (such as MATLAB) will be described.

A valid criticism of the average-case analyses of theoretical computer science is that they are highly dependent on the measure placed on the space of problems. This viewpoint will be discussed in the context of real number algorithms.