Tech Report CS-01-04

Optimal Pruning in Parametric Differential Equations

Micha Janssen, Pascal Van Hentenryck, and Yves Deville

June 2001

Abstract:

Initial value problems for parametric ordinary differential equations (ODEs) arise in many areas of science and engineering. Since some of the data is uncertain, traditional numerical methods do not apply. This paper considers a constraint satisfaction approach that enhances traditional interval methods with a pruning component which uses a relaxation of the ODE and Hermite interpolation polynomials. It solves the main theoretical and practical open issue left in this approach: the choice of an optimal evaluation time for the relaxation. As a consequence, the constraint satisfaction approach is shown to provide a quadratic (asymptotical) improvement in accuracy over the best interval methods, while improving their running times. Experimental results on standard benchmarks confirm the theoretical results.

(complete text in pdf or gzipped postscript)