# Proceedings of the International Congress of Mathematicians Madrid, August 22–30, 2006

Full-Text PDF (188 KB) | Book articles | Book details

#### DOI: 10.4171/022-1/9

Optimal computation

Ronald A. DeVore (1)

(1) Department of Mathematics, University of South Carolina, SC 29208, COLUMBIA, UNITED STATES

A large portion of computation is concerned with approximating a function u. Typically, there are many ways to proceed with such an approximation leading to a variety of algorithms. We address the question of how we should evaluate such algorithms and compare them. In particular, when can we say that a particular algorithm is optimal or near optimal? We shall base our analysis on the approximation error that is achieved with a given (computational or information) budget n. We shall see that the formulation of optimal algorithms depends to a large extent on the context of the problem. For example, numerically approximating the solution to a PDE is different from approximating a signal or image (for the purposes of compression).

Keywords: Optimal computation, encoding and compression, learning theory, entropy and widths