| Given a set of multivariate polynomials {dollar}{lcub}fsb1,...,fsb{lcub}k{rcub}{rcub}subset{lcub}rm l!k{rcub}lbrack xsb1,...,xsb{lcub}n{rcub}rbrack,{dollar} consider the algebraic set {dollar}V={lcub}xin{lcub}bf K{rcub}sp{lcub}n{rcub}vert fsb1(x)=...=fsb{lcub}k{rcub}(x)=0{rcub},{dollar} where K is the algebraic closure of the coefficient field {dollar}rm l!k.{dollar} The problem addressed in the thesis is to compute a representation of algebraic sets such that membership in the radical ideal I(V) is decidable, set operations on algebraic sets are efficiently computable, and the representation is suitable for deriving improved time and space complexity bounds.; Representation by Ritt-Wu characteristic sets serves as a starting point for the representation we propose in the thesis. Gallo and Mishra proves sub-exponential bounds for the size and the complexity of computing the Ritt-Wu characteristic sets. On the other hand, we might loose information about the algebraic set when considering the characteristic set of the corresponding ideal. Kalkbrener proposes a representation where the algebraic set is decomposed into unmixed dimensional components, and he proves that assuming some non-vanishing properties of leading coefficients of the polynomials in the representation, every algebraic set is faithfully representable this way. Similar techniques are extensively studied and widely used in computational algebra systems, but it required extra effort to overcome the problem of degree growth and the computation of superfluous components, and to prove sub-exponential complexity results. Kalkbrener states this as a "challenging problem for future research".; In the dissertation we develop a fast parallel algorithm which finds Kalkbrener's unmixed representation. We present a randomized algorithm with sequential (parallel) complexity {dollar}dsp{lcub}O(nsp2(l+1)){rcub}lbrack(n log(d))sp{lcub}O(1){rcub}rbrack,{dollar} where n is the number of variables, d is the maximal degree of the polynomials in the generating set and l is the dimension of the algebraic set. We use multivariate resultant techniques to eliminate variables simultaneously. Then we apply Wu-Ritt type decomposition techniques to factor out superfluous components. This result represents significant theoretical improvement over the known algorithms computing the unmixed representation, since for the first time we prove sequential and parallel complexity bounds which are the same as the best known complexity bounds for computing characteristic sets.; The subroutines we use in our constructions are of independent interest. Given an unmixed algebraic set represented by characteristic set, our method gives a "lazy decomposition" procedure, which is an efficient algorithm for conducting symbolic arithmetic on algebraic numbers without explicitly computing them. In the zero-dimensional case these algorithms are in the complexity class NC (using arithmetic circuits over {dollar}rm l!k).{dollar} These results have applications for example in mechanical geometric theorem proving, in resolving singularities of plane curves and of higher dimensional varieties. |
