The Computational Complexity of Differential and Integral Equations

This book is concerned with a central question in numerical analysis: how efficient can algorithms be made given only incomplete information about a differential or integral equation? Typically this question might arise when an equation is of the form Lu = f, where f is some function defined on a domain and L is a differential operator. We may not be given f exactly, merely its value at a finite number of points in the domain. Consequently the best that can be hoped for is to solve the equation to within a given accuracy at minimal cost or complexity.

The author develops the theory of the complexity of the solution to differential and integral equations and discusses the relationship between the worst-case setting and two (sometimes more tractable) related problems: the average-case setting and the probalistic setting. He addresses both the computation of the complexity of algorithms and also determining optimal algorithms (in the sense of having minimal cost).