Complexity of the Wu-Ritt decomposition
Ágnes Szántó · 1997
Given a polynomial ideal Z by a generating set of polyrtw mials, we present an efficient parallel algorithm to express the radical of Z u an intersection of unmixed ideals, each represented by a triangular set of polynomials.This triangular structure is convenient for many purposes, e.g. for conducting symbolic computation on the common roots of the polynomials in the ideal, or for computing the union, the intersection or the quotient of radicals.The sequential (parallel) complexity of our algorithm is subexponential (subpolynomial).