MODULAR ALGORITHM FOR SPARSE MULTIVARIATE POLYNOMIAL INTERPOLATION AND ITS PARALLEL IMPLEMENTATION

A new algorithm for sparse multivariate polynomial interpolation is pr esented. It is a multi-modular extension of the Pen-Or and Tiwari algo rithm, and is designed to be a practical method to construct symbolic formulas from numeric data produced by Vector or massively-parallel pr ocessors. The main idea in our algorithm comes from the well-known tec hnique for primality test based on Fermat's theorem, and is the applic ation of the generalized Chinese remainder theorem to the monomial exp onents. We regard the exponent vector of each multivariate monomial as a mixed-radix representation of the corresponding exponent value obta ined after the transformation by Kronecker's technique. It is shown by complexity comparison and experimenter results that the step for univ ariate polynomial factorization is most expensive in our algorithm, an d its parallelization is considered. Also reported are some empirical results of the parallelization on KLIC, a portable system of a concurr ent logic programming language KL1. (C) 1996 Academic Press Limited