Repository logo
 
Loading...
Project Logo
Research Project

Untitled

Authors

Publications

Computational complexity of solving polynomial differential equations over unbounded domains
Publication . Pouly, Amaury; Graça, Daniel
In 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 of ordinary differential equations
Publication . Graça, Daniel; Zhong, Ning
In this paper we provide a brief review of several results about the computability of initial-value problems (IVPs) defined with ordinary differential equations (ODEs). We will consider a variety of settings and analyze how the computability of the IVP will be affected. Computational complexity results will also be presented, as well as computable versions of some classical theorems about the asymptotic behavior of ODEs.
Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length
Publication . Olivier, Bournez; Daniel, Graça; Amaury, Pouly
The outcomes of this article are twofold. Implicit complexity. We provide an implicit characterization of polynomial time computation in terms of ordinary differential equations: we characterize the class P of languages computable in polynomial time in terms of differential equations with polynomial right-hand side. This result gives a purely continuous elegant and simple characterization of P. We believe it is the first time complexity classes are characterized using only ordinary differential equations. Our characterization extends to functions computable in polynomial time over the reals in the sense of Computable Analysis. Our results may provide a new perspective on classical complexity, by giving a way to define complexity classes, like P, in a very simple way, without any reference to a notion of (discrete) machine. This may also provide ways to state classical questions about computational complexity via ordinary differential equations. Continuous-Time Models of Computation. Our results can also be interpreted in terms of analog computers or analog models of computation: As a side effect, we get that the 1941 General Purpose Analog Computer (GPAC) of Claude Shannon is provably equivalent to Turing machines both in terms of computability and complexity, a fact that has never been established before. This result provides arguments in favour of a generalised form of the Church-Turing Hypothesis, which states that any physically realistic (macroscopic) computer is equivalent to Turing machines both in terms of computability and complexity.
On the functions generated by the general purpose analog computer
Publication . Olivier, Bournez; Graça, Daniel; Amaury, Pouly
We 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.
Equation of state of a laser-cooled gas
Publication . Rodrigues, J. D.; Rodrigues, J. A.; Moreira, O. L.; Tercas, H.; Mendonca, J. T.
We experimentally determine the equation of state of a laser-cooled gas. By employing the Lane-Emden formalism, widely used in astrophysics, we derive the equilibrium atomic profiles in large magneto-optical traps where the thermodynamic effects are cast in a polytropic equation of state. The effects of multiple scattering of light are included, which results in a generalized Lane-Emden equation for the atomic profiles. A detailed experimental investigation reveals an excellent agreement with the model, with a twofold significance. On one hand, we can infer the details of the equation of state of the system, from an ideal gas to a correlated phase due to an effective electrical charge for the atoms, which is accurately described by a microscopical description of the effective electrostatic interaction. On the other hand, we are able map the effects of multiple scattering onto directly controllable experimental variables, which paves the way to subsequent experimental investigations of this collective interaction.

Organizational Units

Description

Keywords

Contributors

Funders

Funding agency

Fundação para a Ciência e a Tecnologia

Funding programme

5876

Funding Award Number

UID/EEA/50008/2013

ID