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

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

Get full access to this article

View all access options for this article.

References

A.G.

Akritas, Elements of Computer Algebra with Applications, Wiley Interscience, New York, 1989.

P.E.

Alaev, Existence and uniqueness of structures computable in polynomial time, Algebra and Logic 55(1) (2016), 106–112. doi:10.1007/s10469-016-9377-6.

P.E.

Alaev and

V.L.

Selivanov, Fields of algebraic numbers computable in polynomial time. I, Algebra and Logic 58(6) (2019), 673–705. doi:10.33048/alglog.2019.58.601.

K.I.

Babenko, in: Foundations of Numerical Analysis, Moscow, Nauka, 1986, (in Russian).

J.L.

Balcázar,

Díaz and

Gabarró, Structural complexity I, in: EATCS Monographs on Theoretical Computer Science, Vol. 11, Springer-Verlag, 1988.

Basu,

Pollack and

Roy, Algorithms in Real Algebraic Geometry, Springer, Heidelberg, 2006.

Brattka,

Hertling and

Weihrauch, A tutorial on computable analysis, in: New Computational Paradigms,

S.B.

Cooper,

Löwe and

Sorbi, eds, 2008, pp. 425–491.

Bürgisser,

Clausen and

Shokrollahi, Algebraic Complexity Theory, Springer, Berlin-Heidelberg, 1997.

Cenzer and

Remmel, Polynomial time versus recursive models, Annals of Pure and Applied Logic 54 (1991), 17–58. doi:10.1016/0168-0072(91)90008-A.

10.

G.E.

Collins and

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 Mathematics 7 (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.

Godunov

et 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.

John, Lectures on Advanced Numerical Analysis, Gordon and Breach, Science Publishers, Inc., 1966.

20.

Kawamura and

Ziegler, Invitation to Real Complexity Theory: Algorithmic Foundations to Reliable Numerics with Bit-Costs, arXiv:1801.07108.

21.

Ker-I, Complexity Theory of Real Functions, Birkhäuser, Boston, 1991.

22.

Koswara,

Selivanova and

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

Lovasz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515–534. doi:10.1007/BF01457454.

25.

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.

Mizohata, The Theory of Partial Differential Equations, Cambridge Univ. Press, Cambridge, 1973.

27.

Pan and

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.

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.

Schrijver, Theory of Linear and Integer Programming, Wiley Interscience, New York, 1986.

31.

Selivanova and

Selivanov, Computing solution operators of boundary-value problems for some linear hyperbolic systems of PDEs, Logical Methods in Computer Science 4(13) (2017), 1–31, Earlier version on

arXiv:1305.2494

(2013).

32.

Selivanova and

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 Science 15(6) (2009), 1337–1364.

34.

S.V.

Selivanova and

V.L.

Selivanov, On constructive number fields and computability of solutions of PDEs, Doklady Mathematics 477(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,

Manea,

Miller and

Novotka, eds, LNCS, Vol. 10936, Springer, Berlin, 2018.

36.

Smale, On the topology of algorithms, J. of Complexity 3 (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.

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.

Vassiliev, Cohomology of braid groups and the complexity of algorithms, Functional Anal. Appl 22 (1989), 182–190. doi:10.1007/BF01077624.

42.

Weihrauch, Computable Analysis, Springer, Berlin, 2000.

43.

Weihrauch, Computational complexity on computable metric spaces, Mathematical Logic Quarterly 49(1) (2003), 3–21.

44.

Yap,

Sagraloff and

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 Theory 34 (1990), 133–141. doi:10.1016/0022-314X(90)90144-G.

47.

Ziegler, Real computation with least discrete advice: A complexity theory of nonuniform computability, Annals of Pure and Applied Logic 163(8) (2012), 1108–1139. doi:10.1016/j.apal.2011.12.030.

48.

Ziegler and

Brattka, A computable spectral theorem, in: Proc. CCA 2000, Lecture Notes in Computer Science, Vol. 2064, 2001, pp. 378–388.