Exact Real Computation of Solution Operators for Linear Analytic Systems of Partial Differential Equations

Abstract

We devise and analyze the bit-cost of solvers for linear evolutionary systems of Partial Differential Equations (PDEs) with given analytic initial conditions. Our algorithms are rigorous in that they produce approximations to the solution up to guaranteed absolute error 1 / 2 n for any desired number n of output bits. Previous work has shown that smooth (i.e. infinitely differentiable but non-analytic) initial data does not yield polynomial-time computable solutions unless it holds P=NP (or stronger complexity hypotheses). We first resume earlier complexity investigations of the Cauchy-Kovalevskaya Theorem about linear PDEs with analytic matrix coefficients: from qualitative polynomial-time solutions for any fixed polynomial-time computable analytic initial conditions, to quantitative parameterized bit-cost analyses for any given analytic initial data, as well as turn devised algorithms into computational practice. We secondly devise a parameterized polynomial-time solver for the Heat and the Schrödinger equation with given analytic initial data: PDEs not covered by Cauchy-Kovalevskaya. Reliable implementations and empirical performance evaluation (including testing on the Elasticity and Acoustic systems examples) in the Exact Real Computation (ERC) paradigm confirm the theoretical predictions and practical applicability of our algorithms. These involve new continuous abstract data types operating on power and Fourier series without rounding error. © 2021, Springer Nature Switzerland AG.