Polynomial-time solution of initial value problems using polynomial enclosures

Research output: Chapter in Book/Conference proceedingConference contributionpeer-review

Abstract

Domain theory has been used with great success in providing a semantic framework for Turing computability, over both discrete and continuous spaces. On the other hand, classical approximation theory provides a rich set of tools for computations over real functions with (mainly) polynomial and rational function approximations. We present a semantic model for computations over real functions based on polynomial enclosures. As an important case study, we analyse the convergence and complexity of Picard's method of initial value problem solving in our framework. We obtain a geometric rate of convergence over Lipschitz fields and then, by using Chebyshev truncations, we modify Picard's algorithm into one which runs in polynomial-time over a set of polynomial-space representable fields, thus achieving a reduction in complexity which would be impossible in the step-function based domain models.

Original languageEnglish
Title of host publicationLogic, Language, Information and Computation - 19th International Workshop, WoLLIC 2012, Proceedings
PublisherSpringer Verlag
Pages232-245
Number of pages14
ISBN (Print)9783642326202
DOIs
Publication statusPublished - 2012
Event19th International Workshop on Logic, Language, Information and Computation, WoLLIC 2012 - Buenos Aires, Argentina
Duration: 3 Sep 20126 Sep 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7456 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference19th International Workshop on Logic, Language, Information and Computation, WoLLIC 2012
Country/TerritoryArgentina
CityBuenos Aires
Period3/09/126/09/12

Keywords

  • approximation theory
  • Chebyshev series
  • computable analysis
  • computational complexity
  • initial value problem
  • Picard's method

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'Polynomial-time solution of initial value problems using polynomial enclosures'. Together they form a unique fingerprint.

Cite this