Efficient Algorithms for Computing with Sparse Polynomials.
Mahdi Javadi, Simon Fraser University.Monday January 17th, in K9509 at 10:00am.
Abstract. The problem of interpolating a sparse polynomial has always been one of the central objects of research in the area of computer algebra. It is the key part of many algorithms such as polynomial GCD computation. We present a probabilistic algorithm to interpolate a sparse multivariate polynomial over a finite field, represented with a black box. Our algorithm modifies the algorithm of Ben-Or and Tiwari from 1988 for interpolating polynomials over rings with characteristic zero to positive characteristics by doing additional probes. To interpolate a polynomial in $n$ variables with $t$ non-zero terms, Zippel’s (1990) algorithm interpolates one variable at a time using $O(ndt)$ probes to the black box where $d$ bounds the degree of the polynomial. Our new algorithm does $O(nt)$ probes. We provide benchmarks comparing our algorithm to Zippel's algorithm and the racing algorithm of Kaltofen and Lee. The benchmarks demonstrate that for sparse polynomials our algorithm often makes fewer probes. Also our algorithm can be parallelized more efficiently compared to the other two algorithms. Our main application for an efficient sparse interpolation algorithm is to compute the GCD of polynomials. Furthermore we present an efficient algorithm for factoring multivariate polynomials over algebraic fields with multiple field extensions and parameters. Our algorithm uses Hensel lifting and extends the EEZ algorithm of Wang which was designed for factorization over rationals. We also give a multivariate $p$-adic lifting algorithm which uses sparse interpolation. This enables us to avoid using poor bounds on the size of the integer coefficients in the factorization when using Hensel lifting. We provide timings demonstrating the efficiency of our algorithm.