Modular Algorithm for Sparse Multivariate Polynomial Interpolationand its Parallel Implementation

A new algorithm for sparse multivariate polynomial interpolation is presented. It is a multi-modular extension of the Ben-Or and Tiwari algorithm, and is designed to be a practical method to construct symbolic formulas from numeric data produced by vector or massively-parallel processors. The main idea in our algorithm comes from the well-known technique for primality test based on Fermatʹs theorem, and is the application of the generalized Chinese remainder theorem to the monomial exponents. We regard the exponent vector of each multivariate monomial as a mixed-radix representation of the corresponding exponent value obtained after the transformation by Kroneckerʹs technique. It is shown by complexity comparison and experimental results that the step for univariate polynomial factorization is most expensive in our algorithm, and its parallelization is considered. Also reported are some empirical results of the parallelization on KLIC, a portable system of a concurrent logic programming language KL1.