Optimal computation

Autores: Ronald DeVore
Localización: Proceedings oh the International Congress of Mathematicians: Madrid, August 22-30,2006 : invited lectures / coord. por Marta Sanz Solé , Javier Soria de Diego , Juan Luis Varona Malumbres , Joan Verdera , Vol. 1, 2006, ISBN 978-3-03719-022-7, págs. 187-215
Idioma: inglés
Enlaces
- Texto completo (pdf)
Resumen
- 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).