On the complexity of solving initial value problems

Abstract

In this paper we prove that computing the solution of an initial-value problem $\dot{y}=p(y)$ with initial condition $y(t_0)=y_0\in {\mathbb{R}}^d$ at time $t_0+T$ with precision $e^{-\mu }$ where $p$ is a vector of polynomials can be done in time polynomial in the value of $T$, $\mu$ and $Y=\sup_{t_0\leqslant u\leqslant T}\infnorm{y(u)}$. Contrary to existing results, our algorithm works for any vector of polynomials $p$ over any bounded or unbounded domain and has a guaranteed complexity and precision. In particular we do not assume $p$ to be fixed, nor the solution to lie in a compact domain, nor we assume that $p$ has a Lipschitz constant.

8 pages (two columns per page), submitted to ISSAC'12 conference

Cited by in corpus (4)

• Computational complexity of solving polynomial differential equations over unbounded domains
• Turing machines can be efficiently simulated by the General Purpose Analog Computer
• Axiomatization of Compact Initial Value Problems: Open Properties
• Computing the exact number of periodic orbits for planar flows