Computational Complexity of Initial Value Problems
Robert Corless, University of Western OntarioFriday 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.