Bit-complexity of classical solutions of linear evolutionary systems of partial differential equations

Abstract

We study the bit-complexity intrinsic to solving the initial-value and (several types of) boundary-value problems for linear evolu-tionary systems of partial differential equations (PDEs), based on the Computable Analysis approach. Our algorithms are guaranteed to compute classical solutions to such problems approximately up to error 1/2n, so that n corresponds to the number of reliable bits of the output; bit-cost is measured with respect to n. Computa-tional Complexity Theory allows us to prove in a rigorous sense that PDEs with constant coefficients are algorithmically 'easier' than general ones. Indeed, solutions to the latter are shown (un-der natural assumptions) computable using a polynomial number of memory bits, and we prove that the complexity class PSPACE is in general optimal; while the case of constant coefficients can be solved in #P-also essentially optimally so: the Heat Equation 're-quires' #P1. Our algorithms raise difference schemes to exponential powers, efficiently: we compute any desired entry of such a power in #P, provided that the underlying exponential-sized matrices are circulant of constant bandwidth. Exponentially powering modular two-band circulant matrices is established even feasible in P; and under additional conditions, also the solution to certain linear PDEs becomes polynomial time computable. (c) 2023 Elsevier Inc. All rights reserved.