Time complexity and convergence analysis of domain theoretic Picard method

Amin Farjudian, Michal Konečný

Research output: Chapter in Book/Report/Conference proceedingConference 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.

  • Research Output

    • 1 Technical report

    Time Complexity and Convergence Analysis of Domain Theoretic Picard Method (Extended Abstract)

    Farjudian, M. A. & Konecny, M., 23 Apr 2008.

    Research output: Working paperTechnical report

    File

    Cite this

    Farjudian, A., & Konečný, M. (2008). Time complexity and convergence analysis of domain theoretic Picard method. In W. Hodges, & R. de Queiroz (Eds.), Logic, language, information and computation: 15th International Workshop, WoLLIC 2008 Edinburgh, UK, July 1-4, 2008 Proceedings (pp. 149-163). (Lecture notes in computer science; Vol. 5110). Springer. https://doi.org/10.1007/978-3-540-69937-8_14