Symbolic Computation Group

David R. Cheriton School of Computer Science
University of Waterloo, Waterloo, Ontario, Canada

A new view of the computational complexity of the numerical solution of ordinary differential equations
Rob Corless, University of Western Ontario
Friday, March 8, 2002, at U. of Waterloo.

Abstract:

The theory of information-based computational complexity of the solution of initial-value problems for ordinary differential equations is not well-regarded by many of the practitioners of scientific computing, because its main results (adaption is no better than nonadaption, and the cost to solve a problem to accuracy~$\e$ is exponential in $\ln\e$) contradict their experience. This has not gone unnoticed by the complexity theorists. Indeed, in~\cite{Werschulz:1991} we find the following passage: ``This result (adaption is no better than nonadaption) has not been enthusiastically accepted by many practitioners of scientific computation''. Thus the view of the whole field of computational complexity of the solution of IVP for ODE is coloured by the negative perception of some of its results. I hope to change that view with this paper, by changing the theory.

 

Last modified on Sunday, 04 November 2012, at 20:42 hours.