1990 · 35 citations · 19 references
ComputingComputer ScienceMathematicsAlgorithmsComputational GeometryTheory Of ComputationComplexity TheoryComputational AlgebraComputational ComplexityAlgorithms For Ideals
We show that if a system of polynomials fl,f2,... ,Jr in n variables with deg(fl) _< d over the rational numbers has only finitely many affine zeros, then, all the affine zeros can be determined in time polynomial in d n by a Las Vegas type randomized algorithm. We then describe single exponential time algorithms to compute reduced Gr5bner bases for the radical of the ideal generated by fi and for all the prime ideals containing the radical.
19
Some algebraic and geometric computations in PSPACE
John Canny · 1988 · 581 citations · Full text
Subresultants and Reduced Polynomial Remainder Sequences
George E. Collins · Journal of the ACM · 1967 · 330 citations