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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Edalat, A., Pattinson, D.: A domain theoretic account of Picard’s theorem. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 494–505. Springer, Heidelberg (2004)
Edalat, A., Pattinson, D.: A domain theoretic account of Euler’s method for solving initial value problems. In: Dongarra, J., Madsen, K., Waśniewski, J. (eds.) PARA 2004. LNCS, vol. 3732, pp. 112–121. Springer, Heidelberg (2006)
Farjudian, A., Konečný, M.: Time complexity and convergence analysis of domain theoretic picard method (March 2008), http://www-users.aston.ac.uk/~farjudia/AuxFiles/2008-Picard.pdf
Müller, N.T.: The iRRAM: Exact arithmetic in C++. In: Blank, J., Brattka, V., Hertling, P. (eds.) CCA 2000. LNCS, vol. 2064, pp. 222–252. Springer, Heidelberg (2001)
Lambov, B.: Reallib: An efficient implementation of exact real arithmetic. Mathematical Structures in Computer Science 17(1), 81–98 (2007)
Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. Society for Industrial and Applied Mathematics, Philadelphia (2002)
Edalat, A., Pattinson, D.: Domain theoretic solutions of initial value problems for unbounded vector fields. In: Escardó, M. (ed.) Proc. MFPS XXI. Electr. Notes in Theoret. Comp. Sci, vol. 155, pp. 565–581 (2005)
Rauh, A., Hofer, E.P., Auer, E.: Valencia-ivp: A comparison with other initial value problem solvers. In: CD-Proc. of the 12th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics SCAN 2006, Duisburg, Germany. IEEE Computer Society, Los Alamitos (2007)
Nedialkov, N.S.: Vnode-lp: A validated solver for initial value problems in ordinary differential equations. Technical Report CAS-06-06-NN, Department of Computing and Software, McMaster University (July 2006)
Makino, K., Berz, M.: Cosy infinity version 9. Nuclear Instruments and Methods A558, 346–350 (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Farjudian, A., Konečný, M. (2008). Time Complexity and Convergence Analysis of Domain Theoretic Picard Method. In: Hodges, W., de Queiroz, R. (eds) Logic, Language, Information and Computation. WoLLIC 2008. Lecture Notes in Computer Science(), vol 5110. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69937-8_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-69937-8_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69936-1
Online ISBN: 978-3-540-69937-8
eBook Packages: Computer ScienceComputer Science (R0)