Atlas home || Conferences | Abstracts | about Atlas

First St.Petersburg Days of Logic and Computability
May 26-29, 1999
Steklov Institute of Mathematics
St. Petersburg, Russia

Organizers
Evgeny Dantsin, Gennadii Davydov, Dima Grigoriev, Eduard Karavaev, Nickolai Kossovskii, Vladimir Lifschitz, Maurice Margenstern, Yuri Matiyasevich (chairman), Grigori Mints, Vladimir Orevkov, Anatol Slissenko, Maxim Vsemirnov

View Abstracts
Conference Homepage

Computing the complexification of a semialgebraic set
by
Nicolai Vorobjov
University of Bath
Coauthors: M-F Roy

We describe an algorithm for producing the smallest complex algebraic variety containing a given semialgebraic set S in Rn, and all the irreducible components of S. Let S be defined by s polynomials of degrees less than d with integer coefficients of bit lengths less than M. Then the complexity of the algorithm is bounded from above by a polynomial in M, sn, dn2. We prove that the geometric degree of the complexification is less than sndO(n), while the degrees of polynomials defining the complexification and irreducible components are less than dO(n). The algorithm has many applications, like computing the real radical of a polynomial ideal, while the degree bound can be used for proving new complexity lower bounds for algebraic comptation trees.

Date received: February 23, 1999

Copyright © 1999 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cacs-05.