Computational complexity of solving polynomial differential equations over unbounded domains

DOI10.1016/J.TCS.2016.02.002zbMATH Open1416.65197arXiv1409.0451OpenAlexW1933685207MaRDI QIDQ264572FDOQ264572

Authors: Amaury Pouly, Daniel Graça 

Publication date: 31 March 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: In this paper we investigate the computational complexity of solving ordinary differential equations (ODEs) $y^{prime}=p(y)$ over emph{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 $varepsilon$ as input, they will output a value $ildey$ which satisfies $|y(t)-ildey|leqvarepsilon$. We analyze the complexity of these algorithms and show that they compute $ildey$ in time polynomial in several quantities including the time $t$, the accuracy of the output $varepsilon$ 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.

Full work available at URL: https://arxiv.org/abs/1409.0451

Recommendations

• Computational bounds on polynomial differential equations
• Solving analytic differential equations in polynomial time over unbounded domains
• Rigorous numerical computation of polynomial differential equations over unbounded domains
• Computability with polynomial differential equations
• Computation of all polynomial solutions of a class of nonlinear differential equations
• Complexity of solutions of partial differential equations
• Characterizing time computational complexity classes with polynomial differential equations
• On the complexity of quadratization for polynomial differential equations
• Complexity of solving parametric polynomial systems
• scientific article; zbMATH DE number 3928209

zbMATH Keywords

computational complexityordinary differential equationsadaptive Taylor algorithmscomputation with real numbers

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Nonlinear ordinary differential equations and systems (34A34) Numerical methods for initial value problems involving ordinary differential equations (65L05)

Cites Work

• Algorithm 924, TIDES, a Taylor series integrator for differential equations
• A Software Package for the Numerical Integration of ODEs by Means of High-Order Taylor Methods
• Computational complexity of one-step methods for a scalar autonomous differential equation
• A new view of the computational complexity of IVP for ODE
• Explicit a-priori error bounds and adaptive error control for approximation of nonlinear initial value differential systems
• Computability with polynomial differential equations
• Church's thesis meets the \(N\)-body problem
• Fast computation of power series solutions of systems of differential equations
• Computability, noncomputability and undecidability of maximal intervals of IVPs
• Effective computability of solutions of differential inclusions: the ten thousand monkeys approach
• Title not available (Why is that?)
• Solving Ordinary Differential Equations Using Taylor Series
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• AN EFFECTIVE CAUCHY-PEANO EXISTENCE THEOREM FOR UNIQUE SOLUTIONS
• Boundedness of the domain of definition is undecidable for polynomial ODEs
• On the complexity of solving initial value problems
• A tutorial on computable analysis
• Breaking the limits: The Taylor series method
• Lipschitz continuous ordinary differential equations are polynomial-space complete
• Adaptivity and computational complexity in the numerical solution of ODEs

Cited In (19)

• Parameterized complexity for uniform operators on multidimensional analytic functions and ODE solving
• Computational complexity of classical solutions of partial differential equations
• On the complexity of solving initial value problems
• Parametrised second-order complexity theory with applications to the study of interval computation
• Characterizing time computational complexity classes with polynomial differential equations
• Title not available (Why is that?)
• A universal ordinary differential equation
• Computational bounds on polynomial differential equations
• Solving analytic differential equations in polynomial time over unbounded domains
• Boundedness of the domain of definition is undecidable for polynomial ODEs
• Rigorous numerical computation of polynomial differential equations over unbounded domains
• Computing continuous-time Markov chains as transformers of unbounded observables
• Computational complexity of real powering and improved solving linear differential equations
• Computing the exact number of periodic orbits for planar flows
• Computation of Darboux polynomials and rational first integrals with bounded degree in polynomial time
• Real-time computability of real numbers by chemical reaction networks
• Computability of Differential Equations
• A continuous characterization of PSPACE using polynomial ordinary differential equations
• Polynomial differential equations compute all real computable functions on computable compact intervals

Uses Software

• TIDES
• Taylor

This page was built for publication: Computational complexity of solving polynomial differential equations over unbounded domains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q264572)