Bit complexity of computing solutions for symmetric hyperbolic systems of PDEs with guaranteed precision

Article type: Research Article

Authors: Selivanova, Svetlana^{a; *} | Selivanov, Victor^b

Affiliations: [a] School of Computing, KAIST, 291 Daehak-ro, Yuseong-gu, Daejeon 34141, Republic of Korea. sseliv@kaist.ac.kr | [b] Theoretical Programming Laboratory, A.P. Ershov Institute of Informatics Systems SB RAS, 6 Acad. Lavrentjev pr., Novosibirsk 630090, Russia. vseliv@iis.nsk.su

Correspondence: [*] Corresponding author. sseliv@kaist.ac.kr.

Abstract: We establish upper bounds on bit complexity of computing solution operators for symmetric hyperbolic systems of PDEs, combining symbolic and approximate algorithms to obtain the solutions with guaranteed prescribed precision. Restricting to algebraic real inputs allows us to use the classical (“discrete”) bit complexity concept.

Keywords: Symmetric hyperbolic system, bit complexity, solution operator, guaranteed precision, symbolic computations, algebraic real, approximation, symmetric matrix, spectral decomposition, difference scheme

DOI: 10.3233/COM-180215

Journal: Computability, vol. 10, no. 2, pp. 123-140, 2021