Parameterized Complexity for Uniform Operators on Multidimensional Analytic Functions and ODE Solving
Parameterized Complexity for Uniform Operators on Multidimensional Analytic Functions and ODE Solving
复制标题
DOI：
10.1007/978-3-662-57669-4_13
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
A. Kawamura;Florian Steinberg;Holger Thies
中科院分区：
文献类型：
--
作者：
A. Kawamura;Florian Steinberg;Holger Thies
真实的复杂性理论是对可计算分析的一种资源受限的细化，它通过依赖图灵机来处理任意但保证绝对误差的近似值，提供了一个关于真实的数、序列和函数的计算运行时间的现实概念。经典的真实的复杂性结果表明，重要的数值算子可以将多项式时间可计算的函数映射到一些更高复杂性的函数类，如或。然而，仅限于解析函数，这些运算符将多项式时间可计算函数再次映射到多项式时间可计算函数。最近的工作由Kawamura，Müller，Rösnick和齐格勒讨论了如何扩展到统一算法的一维解析函数在简单的紧域使用二阶和参数化的复杂性。本文将他们的一些结果推广到多维解析函数的情形。我们进一步使用这一点来表明，运营商映射的解析常微分方程的解决方案是可计算的参数化多项式时间。最后，我们讨论了如何理论可以作为一个基础，验证精确的数值计算与解析函数，并提供了一个原型实现theiRRAMC++框架的精确真实的算法。
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 likeor. 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 theiRRAMC++ framework for exact real arithmetic.