TY - GEN

T1 - Parameterized complexity for uniform operators on multidimensional analytic functions and ODE solving

AU - Kawamura, Akitoshi

AU - Steinberg, Florian

AU - Thies, Holger

N1 - Funding Information:
Acknowledgements. This work was supported by JSPS KAKENHI Grant Numbers JP18H03203 and JP18J10407 and by the Japan Society for the Promotion of Science (JSPS), Core-to-Core Program (A. Advanced Research Networks).

PY - 2018

Y1 - 2018

N2 - Real complexity theory is a resource-bounded refinement of computable analysis and provides a realistic notion of running time of computations over real numbers, sequences, and functions by relying on Turing machines to handle approximations of arbitrary but guaranteed absolute error. Classical results in real complexity show that important numerical operators can map polynomial time computable functions to functions that are hard for some higher complexity class like NP or # P. Restricted to analytic functions, however, those operators map polynomial time computable functions again to polynomial time computable functions. Recent work by Kawamura, Müller, Rösnick and Ziegler discusses how to extend this to uniform algorithms on one-dimensional analytic functions over simple compact domains using second-order and parameterized complexity. In this paper, we extend some of their results to the case of multidimensional analytic functions. We further use this to show that the operator mapping an analytic ordinary differential equations to its solution is computable in parameterized polynomial time. Finally, we discuss how the theory can be used as a basis for verified exact numerical computation with analytic functions and provide a prototypical implementation in the iRRAM C++ framework for exact real arithmetic.

AB - Real complexity theory is a resource-bounded refinement of computable analysis and provides a realistic notion of running time of computations over real numbers, sequences, and functions by relying on Turing machines to handle approximations of arbitrary but guaranteed absolute error. Classical results in real complexity show that important numerical operators can map polynomial time computable functions to functions that are hard for some higher complexity class like NP or # P. Restricted to analytic functions, however, those operators map polynomial time computable functions again to polynomial time computable functions. Recent work by Kawamura, Müller, Rösnick and Ziegler discusses how to extend this to uniform algorithms on one-dimensional analytic functions over simple compact domains using second-order and parameterized complexity. In this paper, we extend some of their results to the case of multidimensional analytic functions. We further use this to show that the operator mapping an analytic ordinary differential equations to its solution is computable in parameterized polynomial time. Finally, we discuss how the theory can be used as a basis for verified exact numerical computation with analytic functions and provide a prototypical implementation in the iRRAM C++ framework for exact real arithmetic.

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

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

U2 - 10.1007/978-3-662-57669-4_13

DO - 10.1007/978-3-662-57669-4_13

M3 - Conference contribution

AN - SCOPUS:85049639318

SN - 9783662576687

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

SP - 223

EP - 236

BT - Logic, Language, Information, and Computation - 25th International Workshop, WoLLIC 2018, Proceedings

A2 - de Queiroz, Ruy

A2 - Martinez, Maricarmen

A2 - Moss, Lawrence S.

PB - Springer Verlag

T2 - 25th International Workshop on Logic, Language, Information, and Computation, WoLLIC 2018

Y2 - 24 July 2018 through 27 July 2018

ER -