FAST PARALLEL ALGORITHMS FOR SPARSE MULTIVARIATE POLYNOMIAL INTERPOLATION OVER FINITE FIELDS*

Overview & Synopsis

The authors consider the problem of reconstructing (i.e., interpolating) a t-sparse multivariate polynomial given a black box which will produce the value of the polynomial for any value of the arguments. It is shown that, if the polynomial has coefficients in a finite field GF[q] and the black box can evaluate the polynomial in the field GF[qr2g,tnt+37], where n is the number of variables, then there is an algorithm to interpolate the polynomial in O(log (nt)) boolean parallel time and O(n2t log nt) processors. This algorithm yields the first efficient deterministic polynomial time algorithm (and moreover boolean NC-algorithm) for interpolating t-sparse polynomials over finite fields and should be contrasted with the fact that efficient interpolation using a black box that only evaluates the polynomial at points in GF[q] is not possible (cf. [M. Clausen, A. Dress, J. Grabmeier, and M. Karpinski, Theoret. Comput. Sci., 1990, to appear]). This algorithm, together with the efficient deterministic interpolation algorithms for fields of characteristic 0 (cf. [D. Yu. Grigoriev and M. Karpinski, in Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science, 1987, pp. 166-172], [M. Ben-Or and P. Tiwari, in Proceedings of the 20th ACM Symposium on the Theory of Computing, 1988, pp. 301-309]), yields for the first time the general deterministic sparse conversion algorithm working over arbitrary fields. (The reason for this is that every field of positive characteristic contains a primitive subfield of this characteristic, and so this method can be applied to the slight extension of this subfield.) The method of solution involves the polynomial enumeration techniques of [D. Yu. Grigoriev and M. Karpinski, op. cit.] combined with introducing a new general method of solving the problem of determining if a t-sparse polynomial is identical to zero by evaluating it in a slight extension of the coefficient field (i.e., an extension whose degree over this field is logarithmic in nt).