Loading...
35 results
Search Results
Now showing 1 - 10 of 35
- 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.
- Computability with polynomial differential equationsPublication . Graça, Daniel; Campagnolo, Manuel; Buescu, JorgeIn this paper, we show that there are Initial Value Problems de ned with polynomial ordinary di erential equations that can simulate univer- sal Turing machines in the presence of bounded noise. The polynomial ODE de ning the IVP is explicitly obtained and the simulation is per- formed in real time.
- The general purpose analog computer and recursive functions over the realsPublication . Graça, DanielPretende-se analisar na presente dissertação diversos modelos matemáticos de computação analógica. Começa-se por analisar o primeiro modelo conhecido deste tipo, o Computador Analógico (GPAC, abreviatura do inglês). São descritos os principais resultados existentes para este modelo, sendo também apresentada uma abordagem alternativa. É mostrado que esta nova abordagem origina um modelo mais robusto que o GPAC, mantendo, no entanto, as suas principais propriedades, tais como a equivalência com funções diferencialmente algébricas. Introduzem-se também novos conceitos que julgamos relevantes, tais como o procedimento de inicializaºão e a noção de GPAC efectivo. Seguidamente, o nosso estudo incide sobre a teoria das funções reais recursivas, uma teoria análoga à teoria clássica das funções recursivas, em que as funções são consideradas sobre o conjunto dos reais, em vez do conjunto dos naturais. Prop˜oem-se novas classes de funções, relacionando-se estas com as principais classes da teoria clássica, incluindo a Hierarquia Aritm´etica. Além disso, mostram-se ainda relações entre as funções reais recursivas e funções geradas por modelos semelhantes ao GPAC.
- On the functions generated by the general purpose analog computerPublication . Olivier, Bournez; Graça, Daniel; Amaury, PoulyWe consider the General Purpose Analog Computer (GPAC), introduced by Claude Shannon in 1941 as a mathematical model of Differential Analysers, that is to say as a model of continuous-time analog (mechanical, and later one electronic) machines of that time. The GPAC generates as output univariate functions (i.e. functions f:R→R). In this paper we extend this model by: (i) allowing multivariate functions (i.e. functions f:Rn→Rm); (ii) introducing a notion of amount of resources (space) needed to generate a function, which allows the stratification of GPAC generable functions into proper subclasses. We also prove that a wide class of (continuous and discontinuous) functions can be uniformly approximated over their full domain. We prove a few stability properties of this model, mostly stability by arithmetic operations, composition and ODE solving, taking into account the amount of resources needed to perform each operation. We establish that generable functions are always analytic but that they can nonetheless (uniformly) approximate a wide range of nonanalytic functions. Our model and results extend some of the results from [19] to the multidimensional case, allow one to define classes of functions generated by GPACs which take into account bounded resources, and also strengthen the approximation result from [19] over a compact domain to a uniform approximation result over unbounded domains.
- 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.
- Computability of limit sets for two-dimensional flowsPublication . Graça, Daniel; Zhong, NingA classical theorem of Peixoto qualitatively characterizes, on the two-dimensional unit ball, the limit sets of structurally stable flows defined by ordinary differential equations. Peixoto's density theorem further shows that such flows are typical in the sense that structurally stable systems form an open dense set in the space of all continuously differentiable flows. In this note, we discuss the problem of explicitly finding the limit sets of structurally stable planar flows.
- Effective computability of solutions of differential inclusions-the ten thousand monkeys approachPublication . Collins, Pieter; Graça, DanielIn this note we consider the computability of the solution of the initial- value problem for ordinary di erential equations with continuous right- hand side. We present algorithms for the computation of the solution using the \thousand monkeys" approach, in which we generate all possi- ble solution tubes, and then check which are valid. In this way, we show that the solution of a di erential equation de ned by a locally Lipschitz function is computable even if the function is not e ectively locally Lips- chitz. We also recover a result of Ruohonen, in which it is shown that if the solution is unique, then it is computable, even if the right-hand side is not locally Lipschitz. We also prove that the maximal interval of existence for the solution must be e ectively enumerable open, and give an example of a computable locally Lipschitz function which is not e ectively locally Lipschitz.
- Computability and dynamical systems: a perspectivePublication . Graça, DanielIn this paper we look at dynamical systems from a computability perspective. We survey some topics and themes of research for dynamical systems and then see how they can be fitted in a computational framework. We will recall some selected results, and enounce problems that might lay possible routes for further research.
- The ordinary differential equation defined by a computable function whose maximal interval of existence is non-computablePublication . Graça, Daniel; Zhong, Ning; Buescu, JorgeLet (®, ¯) ½ R denote the maximal interval of existence of solution for the initial-value problem ½ dx dt = f(t, x), f : E ! Rm,E is an open subset of Rm+1 x(t0) = x0, with (t0, x0) 2 E. We show that (®, ¯) is r.e. (recursively enumerable) open and the solution x(t) defined on (®, ¯) is computable, provided that (a) f is computable and effectively locally Lipschitz, and (b) (t0, x0) is a computable point. We also prove that this result is the best in the sense that, for some initial-value problems satisfying (a) and (b), their maximal intervals of existence are non-recursive.
- Computability, noncomputability and undecidability of maximal intervals of IVPsPublication . Graça, Daniel; Zhong, Ning; Buescu, JorgeLet (α, β) ⊆ R denote the maximal interval of existence of solution for the initial-value problem dx dt = f(t, x) x(t0) = x0, where E is an open subset of Rm+1, f is continuous in E and (t0, x0) ∈ E. We show that, under the natural definition of computability from the point of view of applications, there exist initial-value problems with computable f and (t0, x0) whose maximal interval of existence (α, β) is noncomputable. The fact that f may be taken to be analytic shows that this is not a lack of regularity phenomenon. Moreover, we get upper bounds for the “degree of noncomputability” by showing that (α, β) is r.e. (recursively enumerable) open under very mild hypotheses. We also show that the problem of determining whether the maximal interval is bounded or unbounded is in general undecidable.