Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions
Grégoire Lecerf · 2000
Let ƒ1, … , ƒs be polynomials in n variables over a field of characteristic zero and d be the maximum of their total degree. We propose a new probabilistic algorithm for computing a geometric resolution of each equidimensional part of the variety defined by the system ƒ1 = ··· = ƒs = 0. The returned resolutions are encoded by means of Straight-Line Programs and the complexity of the algorithm is polynomial in a geometric degree of the system. In the worst case this complexity is asymptotically polynomial in sdn.