Browsing by Author "Pouly, Amaury"
Now showing 1 - 4 of 4
Results Per Page
Sort Options
- Computational complexity of solving polynomial differential equations over unbounded domainsPublication . Pouly, Amaury; Graça, DanielIn this paper we investigate the computational complexity of solving ordinary differential equations (ODES) y' = p(y) over unbounded time domains, where p is a vector of polynomials. Contrarily to the bounded (compact) time case, this problem has not been well-studied, apparently due to the "intuition" that it can always be reduced to the bounded case by using rescaling techniques. However, as we show in this paper, rescaling techniques do not seem to provide meaningful insights on the complexity of this problem, since the use of such techniques introduces a dependence on parameters which are hard to compute.We present algorithms which numerically solve these ODES over unbounded time domains. These algorithms have guaranteed accuracy, i.e. given some arbitrarily large time t and error bound 8 as input, they will output a value (y) over tilde which satisfies parallel to y(t)-(y) over tilde parallel to <= epsilon. We analyze the complexity of these algorithms and show that they compute y in time polynomial in several quantities including the time t, the accuracy of the output 8 and the length of the curve y from 0 to t, assuming it exists until time t. We consider both algebraic complexity and bit complexity. (C) 2016 Elsevier B.V. All rights reserved.
- Computing with polynomial ordinary differential equationsPublication . Bournez, Olivier; Graça, Daniel; Pouly, AmauryIn 1941, Claude Shannon introduced the General Purpose Analog Computer (GPAC) as a mathematical model of Differential Analysers, that is to say as a model of continuous-time analog (mechanical, and later on electronic) machines of that time.Following Shannon's arguments, functions generated by the GPAC must satisfy a polynomial differential algebraic equation (DAE). As it is known that some computable functions like Euler's Gamma(x) = integral(infinity)(0) t(x-1)e(-t) dt or Riemann's Zeta function zeta(x) = Sigma(infinity)(k=0)k(1/x), do not satisfy any polynomial DAE, this argument has often been used to demonstrate in the past that the GPAC is less powerful than digital computation.It was proved in Bournez et al. (2007), that if a more modern notion of computation is considered, i.e. in particular if computability is not restricted to real-time generation of functions, the GPAC is actually equivalent to Turing machines.Our purpose is first to discuss the robustness of the notion of computation involved in Bournez et al. (2007), by establishing that many natural variants of the notion of computation from this paper lead to the same computability result.Second, to go from these computability results towards considerations about (time) complexity: we explore several natural variants for measuring time space complexity of a computation.Quite surprisingly, whereas defining a robust time complexity for general continuous time systems is a well known open problem, we prove that all variants are actually equivalent even at the complexity level. As a consequence, it seems that a robust and well defined notion of time complexity exists for the GPAC, or equivalently for computations by polynomial ordinary differential equations.Another side effect of our proof is also that we show in some way that polynomial ordinary differential equations can actually be used as a kind of programming model, and that there is a rather nice and robust notion of ordinary differential equation (ODE) programming. (C) 2016 Published by Elsevier Inc.
- A continuous characterization of PSPACE using polynomial ordinary differential equationsPublication . Bournez, Olivier; Gozzi, Riccardo; Graça, Daniel; Pouly, AmauryIn this paper we provide a characterization of the complexity class PSPACE by using a purely continuous model defined with polynomial ordinary differential equations.
- Solving analytic differential equations in polynomial time over unbounded domainsPublication . Bournez, Olivier; Graça, Daniel; Pouly, AmauryIn this paper we consider the computational complexity of solving initial-value problems de ned with analytic ordinary diferential equations (ODEs) over unbounded domains of Rn and Cn, under the Computable Analysis setting. We show that the solution can be computed in polynomial time over its maximal interval of de nition, provided it satis es a very generous bound on its growth, and that the function admits an analytic extension to the complex plane.