Efficient Algorithms for Computing with Sparse Polynomials.

Mahdi Javadi, Simon Fraser University.

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.