
University of Bonn > Department of Computer Science > Chair V  
CSReports 19851989  Copyright 19851989 University of Bonn, Department of Computer Science, Abt. V  
8523 01.12.2008 
Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
Dima Grigoriev, Marek Karpinski and Michael F. Singer [Download PostScript] [Download PDF] We design fast parallel deterministic algorithms (deterministic boolean NC) for interpolating arbitrary tsparse polynomials over an arbitrary finite field GF[q][x_{1},...,x_{n}]. The Interpolation Algorithm works in a slight field extension GF[q^{⌈2 log7(nt)⌉ + 3}] and uses O(log^{3}(nt)) boolean parallel time and O(n^{2}t^{5}log^{2}nt) processors. It is the first efficient deterministic polynomial time algorithm (and moreover boolean NCalgorithm) for this problem, and together with the efficient deterministic interpolation algorithms for fields of characteristic 0 (cf.[GK 87], [BT 88]) 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 characteristics, and so we can apply our method to the slight extension of this subfield). The method of solution involves the polynomial enumeration techniques of [GK 87] combined with introducing a new general method of breaking the problem of identity to zero of sparse polynomials over the (logarithmic) slight field extension. 

Last Change:
12/01/08 at 19:26:58
Deutsch 
University of Bonn > Department of Computer Science > Chair V 