Title:      Relating symbolic computations to numeric computations

Speaker： Professor Dr. Victor Selivanov

Time：2:30-3:30 PM, Thursday March 15, 2018

Location：Room 623, Big Data Institute, College of Computer Science & Software Engineering, Shenzhen University

Abstract.

The algorithms used in mathematics-oriented software can be divided into two big classes:  symbolic algorithms which aim to find precise solutions, and approximate algorithms which aim to find “good enough” approximations to precise solutions. The symbolic algorithms are implemented e.g. in computer algebra systems or SMT-solvers while the approximate algorithms - in numerical mathematics packages. The both classes of algorithms are widely used in applications and in mathematical research. The symbolic algorithms correspond well to computations on discrete structures (with mathematical foundations in the classical computability and complexity theory) while the approximate algorithms - to computations on continuous structures (with mathematical foundations in the field of computability and complexity in analysis evolving under the slogan “Exact real computation”).

An important idea relating the both classes of algorithms is to look for approximate solutions to a numerical problem with guaranteed precision. Finding such a solution is of crucial importance for safety-critical applications but it often requires much additional work because it sometimes needs a sophisticated algorithm and careful estimations of approximations made during the computation. In many cases the statement of a guaranteed-precision version of some problem on a continuous structure (which requires numerical mathematics and/or computable analysis) reduces it to a problem on a discrete structure which enables to apply the classical computability and complexity theory (sometimes called bit complexity). The bit complexity of an algorithm is fundamental because it estimates the amount of computational resources needed to implement the algorithm on a computing device.

In this talk we discuss some recent results (joint with Svetlana Selivanova) on the bit complexity of finding guaranteed precision solutions for Cauchy and boundary-value problems for symmetric hyperbolic systems of PDEs.

Biography

Professor Dr. Victor Selivanov is a Chief Research Fellow at A.P. Ershov of Informatics Systems (Siberian Branch of Russian Academy of Sciences) and professor of Novosibirsk State University. He is the leader of a team which recently won (together with 5 other teams) a national competition for creating a Regional Mathematical Center. The Center is soon to be established at Kazan Federal University. He was the founding head of department of Informatics and Discrete Mathematics at Novosibirsk Pedagogical University (1991-2009). He had visiting professor positions at universities of Paris-7, Wuerzburg (Germany), Siegen (Germany) and several visiting research positions in Europe. He was/is the coordinator of a Russian team in EU Marie Curie collaboration projects “Computable Analysis” (2012-2015) and “Computing with Infinite Data” (2017-2020). 

Professor Selivanov is known for his contributions to several parts of Computation Theory (computability, complexity, automata), Mathematical Logic and Descriptive Set Theory. He published over 100 refereed papers in prestigious journals and conference proceedings. He was PC member or organizer of several international conferences, including 6 workshops at Leibniz International Center for Computer Science in Dagstuhl (Germany).