Time complexity and convergence analysis of domain theoretic Picard method

Amin Farjudian, Michal Konečný

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Fingerprint

Initial value problems

Bibliographical note

The original publication is available at www.springerlink.com

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). Berlin (DE): Springer. https://doi.org/10.1007/978-3-540-69937-8_14
Farjudian, Amin ; Konečný, Michal. / Time complexity and convergence analysis of domain theoretic Picard method. Logic, language, information and computation: 15th International Workshop, WoLLIC 2008 Edinburgh, UK, July 1-4, 2008 Proceedings. editor / Wilfrid Hodges ; Ruy de Queiroz. Berlin (DE) : Springer, 2008. pp. 149-163 (Lecture notes in computer science).
@inproceedings{313f2952320d48508895937dd1a8b0a5,
title = "Time complexity and convergence analysis of domain theoretic Picard method",
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.",
author = "Amin Farjudian and Michal Konečn{\'y}",
note = "The original publication is available at www.springerlink.com",
year = "2008",
doi = "10.1007/978-3-540-69937-8_14",
language = "English",
isbn = "3-540-6996-8",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "149--163",
editor = "Wilfrid Hodges and {de Queiroz}, Ruy",
booktitle = "Logic, language, information and computation",
address = "Germany",

}

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. Lecture notes in computer science, vol. 5110, Springer, Berlin (DE), pp. 149-163. https://doi.org/10.1007/978-3-540-69937-8_14

Time complexity and convergence analysis of domain theoretic Picard method. / Farjudian, Amin; Konečný, Michal.

Logic, language, information and computation: 15th International Workshop, WoLLIC 2008 Edinburgh, UK, July 1-4, 2008 Proceedings. ed. / Wilfrid Hodges; Ruy de Queiroz. Berlin (DE) : Springer, 2008. p. 149-163 (Lecture notes in computer science; Vol. 5110).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Time complexity and convergence analysis of domain theoretic Picard method

AU - Farjudian, Amin

AU - Konečný, Michal

N1 - The original publication is available at www.springerlink.com

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=47749114654&partnerID=8YFLogxK

UR - http://www.springerlink.com/content/332778n2761v524u/

U2 - 10.1007/978-3-540-69937-8_14

DO - 10.1007/978-3-540-69937-8_14

M3 - Conference contribution

AN - SCOPUS:47749114654

SN - 3-540-6996-8

SN - 978-3-540-6996-1

T3 - Lecture notes in computer science

SP - 149

EP - 163

BT - Logic, language, information and computation

A2 - Hodges, Wilfrid

A2 - de Queiroz, Ruy

PB - Springer

CY - Berlin (DE)

ER -

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