Computational complexity of solving polynomial differential equations over unbounded domains

DOI10.1016/J.TCS.2016.02.002MaRDI QIDQ264572zbMATHOpenAlexFDO

Authors Amaury Pouly, Daniel Graça

Publication date 31 March 2016

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

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

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)

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.

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

Cites work

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

Cited in

(18)

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

Describes a project that uses

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)