TY - GEN
T1 - Time complexity and convergence analysis of domain theoretic Picard method
AU - Farjudian, Amin
AU - Konečný, Michal
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
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 - 3540699368
SN - 9783540699361
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 149
EP - 163
BT - Logic, Language, Information and Computation - 15th International Workshop, WoLLIC 2008, Proceedings
T2 - 15th International Workshop on Logic, Language, Information and Computation, WoLLIC 2008
Y2 - 1 July 2008 through 4 July 2008
ER -