Grid methods in computational real algebraic (and semialgebraic) geometry (Q1754715)

As the author describes in the abstract, the numerical algorithms that have appeared in recents years to solve problems in real algebraic and semialgebraic geometry are numerically stable, ``but their complexity analysis, based on the condition of the data, is radically different from the usual complexity analysis in symbolic computation as these numerical algorithms may run forever on a thin set of ill-posed inputs''. In this paper, after a detailed overview of the development of algorithms in real algebraic and semialgebraic geometry and their computational complexity, the author considers three problems: the feasibility problem for systems of homogeneus polynomials, the problem of counting zeros for square systems of homogeneus polynomials and the problem of the computation of the homology of basic semialgebraic sets. These problems are algorithmically solved by means of grid methods. Analysis of the algorithms is also given.