Computational Complexity of Initial Value Problems

Robert Corless, University of Western Ontario

Friday March 12th, 2004 in K9509 at 10:30pm.



In this talk we look at a relatively new model of the computational
complexity of the numerical solution of initial value problems for ordinary
differential equations.  This new model successfully explains the speed of
practical codes by showing that adaptive strategies are never worse than
nonadaptive strategies and, in this model, the cost of solution to accuracy
eps is polynomial in ln(eps).  These two unexceptional and to-be-expected
results contradict the heretofore standard (but not well-regarded) theory
which, contrary to the practitioner's experience, states that cost is 
exponential and adaption doesn't help.  Those obviously nonsensical results 
contributed to the stifling of the development of complexity theory for 
numerical methods; by breaking the logjam we pave the way to potentially 
useful observations about practical codes.  In addition,
these results imply that certain methods for approximate factorization of
multivariate polynomials have polynomial cost.

Some recent work on the complexity of numerical methods for BVP and for DAE
may be mentioned, if time permits.