Efficient algorithms for computing greatest common divisors (GCD) of multivariate polynomials have been developed over the last 40 years. Many of the general purpose computer algebra systems are using either Zippel's GCD Algorithm [5] or the EEZ-GCD [4] Algorithm or both. Both algorithms sequentially interpolate variables one at a time which limits parallel speedup. Since multi-core processors are now widely available, parallel algorithms are desirable. In this poster, we present a first multivariate GCD computation algorithm over Z which is based on the Ben-Or/Tiwari interpolation [1]. By using Ben- Or/Tiwari interpolation, we reduce the number of points needed to interpolate the GCD and improve parallelism.
展开▼
