Computing with polynomials given by straight-line programs I: greatest common divisors
Erich Kaltofen · 1985
We develop algorithms on multivariate polynomials represented by straight-line programs for the greatest common divisor problem and conversion to sparse representation. Our algorithms are in random polynomial-time for the usual coefficient fields and output with controllably high probability the correct result which for the GCD problem is a straight-line program determining the GCD of the inputs and for the conversion algorithm is the sparse representation of the input. The algorithms only require an a priori bound for the total degrees of the inputs. Over rational numbers the conversion algorithm also needs a bound on the size of the polynomial coefficients. As specializations we get, e.g., random polynomial-time algorithms for computing the sparse GCD of polynomial determinants or for computing the sparse solution of a linear system whose coefficients are given by formulas.