Optimal computation Conference Paper uri icon


  • 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). 2007 European Mathematical Society.

published proceedings

  • International Congress of Mathematicians, ICM 2006

author list (cited authors)

  • Devore, R. A.

complete list of authors

  • Devore, RA

publication date

  • December 2006