Tags:Analog computations, Computational complexity and Ordinary differential equations
Abstract:
We consider Continuous Ordinary Differential Equations: That is to say x′=f(x), where f:Rn→Rn is a continuous function. When an initial condition x(0)=x0 is added, this is called an Initial Value Problem (IVP), also called a Cauchy’s Problem. 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 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(t0)=y0, 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 ε>0, outputs a value ỹ T such that ‖ỹ T−y(T)‖≤ε in time polynomial in T, −logε, 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.
On the computational complexity of solving ordinary differential equations