Olivier Bournez

Olivier Bournez
Ecole Polytechnique, Paris, France

 Title

On the computational complexity of solving ordinary differential equations

 Abstract

We consider Continuous Ordinary Differential Equations: That is to say $x’=f(x)$, where $f: R^{n} \to R^n$ is a continuous function. When an initial condition $x(0)=x_0$ is added, this is called an Initial Value Problem (IVP), also called a Cauchy’s Problem. A trajectory is any solution of the problem, that is to say, any derivable function $\xi: I \subset R_{\ge 0} \to R^n$, where $I$ is some interval containing $0$ satisfying $\xi(0)=x_0$, and $\xi'(t)=f(\xi(t))$ on its domain. The solution is said to be maximal, if $I$ is maximal (for inclusion) with this property.
For $f$ continuous, IVP are known to always have solutions, but possibly non unique, by Peano-Arzelà’s Theorem. When in addition $f$ is Lipschitz (in particular if it is $\mathcal{C}^1$) then unicity is guaranteed, by Cauchy-Lipschitz theorem. When $f$ is analytic, solutions are know to be analytic.

In this talk we will survey various results related to the difficulty of computing a or the solutions for various classes of functions $f$.

In particular, we will discuss the case $y’=p(t,y)$, $y(t_0)=y_0$, where $p$ is a vector of polynomials). In this case, there is a polynomial time algorithm that, given the initial-value problem, the time $T$ at which we want to compute the solution of the IVP, and the maximum allowable error $\varepsilon>0$, outputs a value $\tilde{y}_T$ such that $\|\tilde{y}_T-y(T)\|\leq\varepsilon$ in time polynomial in $T$, $-\log\varepsilon$, and in several quantities related to the polynomial IVP.

We will relate the discussion to questions related to the computational power of several continuous time analog models such as the General Purpose Analog Computer (GPAC) from Claude Shannon. The GPAC was introduced as a model of famous mechanical, and later-on electronics, analog computers named Differential Analysers.

Bio

Olivier Bournez is Professor of Computer Science in Ecole Polytechnique in France. His research interest include computability and complexity theory for computations over the reals, and in particular continuous time analog models of computation.