Polynomial-time solution of initial value problems using polynomial enclosures

Amin Farjudian

doi:10.1007/978-3-642-32621-9_17

Polynomial-time solution of initial value problems using polynomial enclosures

Amin Farjudian

School of Computer Science

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

Abstract

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.

Original language	English
Title of host publication	Logic, Language, Information and Computation - 19th International Workshop, WoLLIC 2012, Proceedings
Publisher	Springer Verlag
Pages	232-245
Number of pages	14
ISBN (Print)	9783642326202
DOIs	https://doi.org/10.1007/978-3-642-32621-9_17
Publication status	Published - 2012
Event	19th International Workshop on Logic, Language, Information and Computation, WoLLIC 2012 - Buenos Aires, Argentina Duration: 3 Sept 2012 → 6 Sept 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7456 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	19th International Workshop on Logic, Language, Information and Computation, WoLLIC 2012
Country/Territory	Argentina
City	Buenos Aires
Period	3/09/12 → 6/09/12

Keywords

Chebyshev series
Picard's method
approximation theory
computable analysis
computational complexity
initial value problem

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Farjudian, A. (2012). Polynomial-time solution of initial value problems using polynomial enclosures. In Logic, Language, Information and Computation - 19th International Workshop, WoLLIC 2012, Proceedings (pp. 232-245). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7456 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-32621-9_17

Farjudian, Amin. / Polynomial-time solution of initial value problems using polynomial enclosures. Logic, Language, Information and Computation - 19th International Workshop, WoLLIC 2012, Proceedings. Springer Verlag, 2012. pp. 232-245 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{11a35f78ba8d4861bc4056a4a79b1612,

title = "Polynomial-time solution of initial value problems using polynomial enclosures",

abstract = "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.",

keywords = "Chebyshev series, Picard's method, approximation theory, computable analysis, computational complexity, initial value problem",

author = "Amin Farjudian",

note = "Copyright: Copyright 2019 Elsevier B.V., All rights reserved.; 19th International Workshop on Logic, Language, Information and Computation, WoLLIC 2012 ; Conference date: 03-09-2012 Through 06-09-2012",

year = "2012",

doi = "10.1007/978-3-642-32621-9_17",

language = "English",

isbn = "9783642326202",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "232--245",

booktitle = "Logic, Language, Information and Computation - 19th International Workshop, WoLLIC 2012, Proceedings",

address = "Germany",

}

Farjudian, A 2012, Polynomial-time solution of initial value problems using polynomial enclosures. in Logic, Language, Information and Computation - 19th International Workshop, WoLLIC 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7456 LNCS, Springer Verlag, pp. 232-245, 19th International Workshop on Logic, Language, Information and Computation, WoLLIC 2012, Buenos Aires, Argentina, 3/09/12. https://doi.org/10.1007/978-3-642-32621-9_17

Polynomial-time solution of initial value problems using polynomial enclosures. / Farjudian, Amin.
Logic, Language, Information and Computation - 19th International Workshop, WoLLIC 2012, Proceedings. Springer Verlag, 2012. p. 232-245 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7456 LNCS).

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

TY - GEN

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

AU - Farjudian, Amin

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 - Chebyshev series

KW - Picard's method

KW - approximation theory

KW - computable analysis

KW - computational complexity

KW - initial value problem

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 -

Farjudian A. Polynomial-time solution of initial value problems using polynomial enclosures. In Logic, Language, Information and Computation - 19th International Workshop, WoLLIC 2012, Proceedings. Springer Verlag. 2012. p. 232-245. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-32621-9_17

Polynomial-time solution of initial value problems using polynomial enclosures

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this