Speaker
Description
In this talk we discuss the exact real computation paradigm, which turns into practice the rigorous but theoretical computable analysis approach (see, e.g., [Weihrauch 2000]). We also highlight some of its recent applications in computing solutions of differential equations with guaranteed prescribed precision. Exact real computation packages allow to conveniently implement imperative algorithms involving real numbers, converging sequences, and smooth functions without using the Turing machines formalism (which computability analysis heavily relies on). This approach differs from traditional reliable numerics in considering real numbers as exact entities (as opposed to intervals) while guaranteeing output approximations up to error 1/2^n (as opposed to intermediate precision propagation). Here n is the output error parameter, i.e., the number of computed digits of the output, which can be arbitrary and is given by the user. One of the crucial theoretical problems to address within this approach is estimating the bit-complexity of computation w.r.t. the parameter n (see, e.g., [Ko 2003] on complexity theory for real functions), which reflects the speed of implementations. Thus, the talk also contains a brief discussion on algorithmic complexity classification of differential equations, compared to their other known classifications.
