NC algorithms for real algebraic numbers (Q1201334): Difference between revisions

This paper presents a collection of algorithmic techniques for the symbolic manipulation (arithmetic operations, sign tests) of real algebraic numbers. The main point is that the given algorithms have the property of belonging to the parallel complexity class NC (described by uniform families of boolean circuits of polylogarithmic depth and polynomial size in the size of the input). Representing real algebraic numbers by a certain sign sequence (by means of Thom's lemma [see \textit{M. Coste} and \textit{M. F. Roy}, J. Symb. Comput. 5, 121-129 (1988; Zbl 0689.14006)]), and using some variants of the techniques of \textit{M. Ben- Or}, \textit{D. Kozen} and \textit{J. Reif} [J. Comput. Syst. Sci. 32, 251-264 (1986; Zbl 0634.03031)] computations with these numbers reduce to counting the numbers of real roots of some systems of polynomial equations and inequalities. Then a multivariate Sturm theory (generalization of Hermite's method) is used to compute such number [see \textit{P. Pedersen}, \textit{M. F. Roy}, \textit{A. Szpirglas}, \textit{F. Eyssette} and \textit{A. Galligo}, ``Counting real zeros in the multivariate case'', in Computational Algebraic Geometry, Prog. Math. 109, 203-224 (1993)].