Time complexity and convergence analysis of domain theoretic Picard method

Amin Farjudian, Michal Konečný

Research output: Chapter in Book/Published conference outputConference publication

Abstract

We present an implementation of the domain-theoretic Picard method for solving initial value problems (IVPs) introduced by Edalat and Pattinson [1]. Compared to Edalat and Pattinson's implementation, our algorithm uses a more efficient arithmetic based on an arbitrary precision floating-point library. Despite the additional overestimations due to floating-point rounding, we obtain a similar bound on the convergence rate of the produced approximations. Moreover, our convergence analysis is detailed enough to allow a static optimisation in the growth of the precision used in successive Picard iterations. Such optimisation greatly improves the efficiency of the solving process. Although a similar optimisation could be performed dynamically without our analysis, a static one gives us a significant advantage: we are able to predict the time it will take the solver to obtain an approximation of a certain (arbitrarily high) quality.
Original languageEnglish
Title of host publicationLogic, language, information and computation
Subtitle of host publication15th International Workshop, WoLLIC 2008 Edinburgh, UK, July 1-4, 2008 Proceedings
EditorsWilfrid Hodges, Ruy de Queiroz
Place of PublicationBerlin (DE)
PublisherSpringer
Pages149-163
Number of pages15
ISBN (Print)3-540-6996-8, 978-3-540-6996-1
DOIs
Publication statusPublished - 2008

Publication series

NameLecture notes in computer science
PublisherSpringer
Volume5110
ISSN (Print)0302-9743

Bibliographical note

The original publication is available at www.springerlink.com

Fingerprint

Dive into the research topics of 'Time complexity and convergence analysis of domain theoretic Picard method'. Together they form a unique fingerprint.

Cite this