TY - GEN

T1 - Polynomial-time solution of initial value problems using polynomial enclosures

AU - Farjudian, Amin

N1 - Copyright:
Copyright 2019 Elsevier B.V., All rights reserved.

PY - 2012

Y1 - 2012

N2 - Domain theory has been used with great success in providing a semantic framework for Turing computability, over both discrete and continuous spaces. On the other hand, classical approximation theory provides a rich set of tools for computations over real functions with (mainly) polynomial and rational function approximations. We present a semantic model for computations over real functions based on polynomial enclosures. As an important case study, we analyse the convergence and complexity of Picard's method of initial value problem solving in our framework. We obtain a geometric rate of convergence over Lipschitz fields and then, by using Chebyshev truncations, we modify Picard's algorithm into one which runs in polynomial-time over a set of polynomial-space representable fields, thus achieving a reduction in complexity which would be impossible in the step-function based domain models.

AB - Domain theory has been used with great success in providing a semantic framework for Turing computability, over both discrete and continuous spaces. On the other hand, classical approximation theory provides a rich set of tools for computations over real functions with (mainly) polynomial and rational function approximations. We present a semantic model for computations over real functions based on polynomial enclosures. As an important case study, we analyse the convergence and complexity of Picard's method of initial value problem solving in our framework. We obtain a geometric rate of convergence over Lipschitz fields and then, by using Chebyshev truncations, we modify Picard's algorithm into one which runs in polynomial-time over a set of polynomial-space representable fields, thus achieving a reduction in complexity which would be impossible in the step-function based domain models.

KW - approximation theory

KW - Chebyshev series

KW - computable analysis

KW - computational complexity

KW - initial value problem

KW - Picard's method

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

U2 - 10.1007/978-3-642-32621-9_17

DO - 10.1007/978-3-642-32621-9_17

M3 - Conference contribution

AN - SCOPUS:84866371520

SN - 9783642326202

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 232

EP - 245

BT - Logic, Language, Information and Computation - 19th International Workshop, WoLLIC 2012, Proceedings

PB - Springer Verlag

T2 - 19th International Workshop on Logic, Language, Information and Computation, WoLLIC 2012

Y2 - 3 September 2012 through 6 September 2012

ER -