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.
A.G.Akritas, Elements of Computer Algebra with Applications, Wiley Interscience, New York, 1989.
2.
P.E.Alaev, Existence and uniqueness of structures computable in polynomial time, Algebra and Logic55(1) (2016), 106–112. doi:10.1007/s10469-016-9377-6.
3.
P.E.Alaev and V.L.Selivanov, Fields of algebraic numbers computable in polynomial time. I, Algebra and Logic58(6) (2019), 673–705. doi:10.33048/alglog.2019.58.601.
4.
K.I.Babenko, in: Foundations of Numerical Analysis, Moscow, Nauka, 1986, (in Russian).
5.
J.L.Balcázar, J.Díaz and J.Gabarró, Structural complexity I, in: EATCS Monographs on Theoretical Computer Science, Vol. 11, Springer-Verlag, 1988.
6.
S.Basu, R.Pollack and M.Roy, Algorithms in Real Algebraic Geometry, Springer, Heidelberg, 2006.
7.
V.Brattka, P.Hertling and K.Weihrauch, A tutorial on computable analysis, in: New Computational Paradigms, S.B.Cooper, B.Löwe and A.Sorbi, eds, 2008, pp. 425–491.
8.
P.Bürgisser, M.Clausen and A.Shokrollahi, Algebraic Complexity Theory, Springer, Berlin-Heidelberg, 1997.
9.
D.Cenzer and J.Remmel, Polynomial time versus recursive models, Annals of Pure and Applied Logic54 (1991), 17–58. doi:10.1016/0168-0072(91)90008-A.
10.
G.E.Collins and R.Loos, Real zeros of polynomials, in: Computer Algebra: Symbolic and Algebraic Computations, Springer-Verlag, 1982, pp. 83–94. doi:10.1007/978-3-7091-3406-1_7.
11.
Y.L.Ershov and S.S.Goncharov, Constructive Models, Scientific Book, Novosibirsk, 1999, (in Russian, there is an English Translation).
12.
L.C.Evans, Partial Differential Equations, Graduate Studies in Mathematics, Vol. 19, American Mathematical Society, 1998.
13.
K.O.Friedrichs, Symmetric hyperbolic linear differential equations, Communication on Pure and Applied Mathematics7 (1954), 345–392. doi:10.1002/cpa.3160070206.
14.
F.R.Gantmacher, Matrix Theory, Nauka, Moscow, 1967, (in Russian).
15.
S.K.Godunov, Equations of Mathematical Physics, Nauka, Moscow, 1971, (in Russian).
16.
S.K.Godunov (ed.), Numerical Solution of Higher-Dimensional Problems of Gas Dynamics, Nauka, Moscow, 1976, (in Russian).
17.
S.K.Godunovet al., in: Guaranteed Precision of Solving Systems of Linear Equations in Euclidean Spaces, Novosibirsk, Nauka, 1988, (in Russian).
18.
S.K.Godunov and V.S.Ryaben’kii, Introduction to the Theory of Difference Schemes, Fizmatgiz, Moscow, 1962, (in Russian). English translation: Difference Schemes: An Introduction to the Underlying Theory (Studies in Mathematics and Its Applications), Elsevier Science Ltd, 1987.
19.
F.John, Lectures on Advanced Numerical Analysis, Gordon and Breach, Science Publishers, Inc., 1966.
20.
A.Kawamura and M.Ziegler, Invitation to Real Complexity Theory: Algorithmic Foundations to Reliable Numerics with Bit-Costs, arXiv:1801.07108.
21.
K.Ker-I, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991.
22.
I.Koswara, S.Selivanova and M.Ziegler, Computational complexity of real powering and improved solving linear differential equations, in: Proc. 14th InternationalComputer Science Symposium in Russia, LNCS, Vol. 11532, 2019.
23.
A.G.Kulikovskii, N.V.Pogorelov and A.Y.Semënov, Mathematical Aspects of Numerical Solution of Hyperbolic Systems, Chapman & Hall/CRC Press, Boca Raton, 2001.
24.
A.K.Lenstra, H.W.Lenstra and L.Lovasz, Factoring polynomials with rational coefficients, Math. Ann.261 (1982), 515–534. doi:10.1007/BF01457454.
25.
R.Loos, Computing in algebraic extensions, in: Computer Algebra: Symbolic and Algebraic Computations, Springer-Verlag, 1982, pp. 115–138. doi:10.1007/978-3-7091-3406-1_9.
26.
S.Mizohata, The Theory of Partial Differential Equations, Cambridge Univ. Press, Cambridge, 1973.
27.
V.Pan and J.Reif, The bit complexity of discrete solutions of partial differential equations: Compact multigrid, Computers Math. Applic.20(2) (1990), 9–16. doi:10.1016/0898-1221(90)90235-C.
28.
V.Y.Pan and Z.Q.Chen, The complexity of the matrix eigenproblem, in: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, ACM, 1999, pp. 507–516. doi:10.1145/301250.301389.
29.
F.Rellich, Störungstheorie der Spektralzerlegung I., Analytische Stor̈ung der isolierten Punkteigenwerte eines beschränkten Operators, Math. Ann.113 (1937), 600–619, (in German). doi:10.1007/BF01571652.
30.
A.Schrijver, Theory of Linear and Integer Programming, Wiley Interscience, New York, 1986.
31.
S.Selivanova and V.Selivanov, Computing solution operators of boundary-value problems for some linear hyperbolic systems of PDEs, Logical Methods in Computer Science4(13) (2017), 1–31, Earlier version onarXiv:1305.2494(2013).
32.
S.Selivanova and M.Ziegler, Turnkey solutions to PDEs in exact real computation, in: Book of Abstracts – 12th Summer Workshop on Interval Methods, Palaiseau, France, July 23–26, 2019, pp. 21–22, https://swim2019.ensta-paris.fr/SWIM-19_Book_of_Abstracts.pdf.
33.
S.V.Selivanova and V.L.Selivanov, Computing solution operators of symmetric hyperbolic systems of PDEs, Journal of Universal Computer Science15(6) (2009), 1337–1364.
34.
S.V.Selivanova and V.L.Selivanov, On constructive number fields and computability of solutions of PDEs, Doklady Mathematics477(3) (2017), 282–285.
35.
S.V.Selivanova and V.L.Selivanov, Bit complexity of computing solutions for symmetric hyperbolic systems of PDEs (extended abstract), in: Proceedings of the Conference Computability in Europe, F.Manea, R.Miller and D.Novotka, eds, LNCS, Vol. 10936, Springer, Berlin, 2018.
36.
S.Smale, On the topology of algorithms, J. of Complexity3 (1987), 81–89. doi:10.1016/0885-064X(87)90021-5.
37.
J.C.Strikverda, Finite Difference Schemes and Partial Differential Equations, SIAM, 2004.
38.
G.Szegö, Orthogonal Polynomials, AMS 531, West 116th Street New York, 1959.
39.
L.N.Trefethen, Finite Difference and Spectral Methods for Ordinary and Partial Differential Equations, Cornell University, Department of Computer Science and Center for Applied Mathematics, 1996.
40.
B.L.van der Waerden, Algebra, Springer, Berlin, 1967.
41.
V.Vassiliev, Cohomology of braid groups and the complexity of algorithms, Functional Anal. Appl22 (1989), 182–190. doi:10.1007/BF01077624.
C.Yap, M.Sagraloff and V.Sharma, Analytic root clustering: A complete algorithm using soft zero tests, in: Conference on Computability in Europe, Springer, 2013, pp. 434–444.
45.
Y.S.Zavyalov, B.I.Kvasov and V.L.Miroshnichenko, Methods of the Spline Functions, Fizmatgiz, Moscow, 1980, (in Russian).
46.
J.-P.Zhou, On the degree of extensions generated by finitely many algebraic numbers, Journal of Number Theory34 (1990), 133–141. doi:10.1016/0022-314X(90)90144-G.
47.
M.Ziegler, Real computation with least discrete advice: A complexity theory of nonuniform computability, Annals of Pure and Applied Logic163(8) (2012), 1108–1139. doi:10.1016/j.apal.2011.12.030.
48.
M.Ziegler and V.Brattka, A computable spectral theorem, in: Proc. CCA 2000, Lecture Notes in Computer Science, Vol. 2064, 2001, pp. 378–388.
