# On the complexity of solving polynomial initial value problems

Abstract : In this paper we prove that computing the solution of an initial-value problem $\dot{y}=p(y)$ with initial condition $y(t_0)=y_0\in\R^d$ at time $t_0+T$ with precision $e^{-\mu}$ where $p$ is a vector of polynomials can be done in time polynomial in the value of $T$, $\mu$ and $Y=\sup_{t_0\leqslant u\leqslant T}\infnorm{y(u)}$. Contrary to existing results, our algorithm works for any vector of polynomials $p$ over any bounded or unbounded domain and has a guaranteed complexity and precision. In particular we do not assume $p$ to be fixed, nor the solution to lie in a compact domain, nor we assume that $p$ has a Lipschitz constant.
Document type :
Conference papers

Cited literature [2 references]

https://hal-polytechnique.archives-ouvertes.fr/hal-00760742
Contributor : Olivier Bournez Connect in order to contact the contributor
Submitted on : Tuesday, December 4, 2012 - 1:00:20 PM
Last modification on : Thursday, March 5, 2020 - 6:26:41 PM
Long-term archiving on: : Saturday, December 17, 2016 - 7:55:53 PM

### File

complexity_solving_pivp.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-00760742, version 1

### Citation

Olivier Bournez, Daniel Graça, Amaury Pouly. On the complexity of solving polynomial initial value problems. International Symposium on Symbolic and Algebraic Computation (ISSAC'12), 2012, France. ⟨hal-00760742⟩

### Metrics

Les métriques sont temporairement indisponibles
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.7893286943435669, "perplexity": 1266.763839667748}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2022-05/segments/1642320304309.5/warc/CC-MAIN-20220123172206-20220123202206-00688.warc.gz"}