Symbolic vs Numeric: relating computations in discrete and continuous structures

• 主讲人：Victor Selivanov (Saint Petersburg State University)
• 举办方： Beijing-Saint Petersburg Mathematics Colloquium
• 时间： 2025-03-27 20:00 - 2025-03-27 21:00
• 地点： Online

​

To Join Tencent Meeting: https://meeting.tencent.com/dm/LisB1icKvvyu

Meeting ID: 927-4841-9441    Password: 202503

 

Abstract: Symbolic algorithms provide precise solutions (presented in a suitable form) and are widely used in computer algebra systems. Numeric algorithms provide approximate solutions and are widely used in numerical packages.

This talk is a short informal survey of some results on computable fields of real numbers and their applications to some computation problems in linear algebra and analysis (symmetric hyperbolic systems of PDEs with constant coefficients). Along with general computability (without any bound on computational resources) we discuss primitive recursive and polynomial-time computability. We trace how more efficient algorithms on fields of reals (which are symbolic algorithms on countable discrete structures) yield more efficient numeric algorithms on continuous structures (like the reals and other relevant metric spaces). From available competing models of computation on continuous structures we choose the model going back to Turing that arguably better corresponds to numeric algorithms (namely, to algorithms with arbitrary guaranteed precision). Our results suggest that adequate mathematical foundations for symbolic and numeric computations are provided by, respectively, computable model theory and computable analysis.

All results mentioned in the talk are joint with either Svetlana Selivanova or Pavel Alaev.

 

Bio: Professor Victor Lvovich Selivanov is an outstanding expert in Theory of Computation, Logic, Automata Theory, Computability in Analysis. He has got his PhD degree in 1979 with the thesis topic 'On computable numbering' and the DS/Habilitation in 1990 on 'Hierarchical Classification of Arithmetic Sets and Index Sets'.

Victor Lvovich previously worked at A.P. Ershov Institute of Informatics Systems (IIS), Siberian Branch of the Russian Academy of Sciences in Novosibirsk at Novosibirsk State University and Kazan Federal University. He has got multiple prestigious awards and grants on national and international levels.

Nowadays, Victor Selivanov is a professor of the Department of Mathematics and Computer Science at Saint Petersburg State University.