MITACS Seminar Series on Mathematics of Computer Algebra and Analysis
Sparse polynomial interpolation.
Michael Monagan, Department of Mathematics, Simon Fraser University.
Abstract: Consider the problem of computing the GCD G of A and B in Zp[x0,x1,...xn]. Let d be the degree of G and t be the number of non-zero terms of G. In the first lecture, we present Brown's modular GCD algorithm from 1971. It interpolates the variables sequentially using dense Newton interpolation. It needs O(d^n) univariate images to interpolate G. For sparse polynomials like x0^d + x1^d + ... + xn^d it is inefficient. In the second lecture, we present Zippel's sparse interpolation from 1979 which requires O(ndt) images to interpolate G and the Ben-Or/Tiwari sparse interpolation algorithm from 1988 which requires O(T) images to interpolate G where T is a term bound on t.