
University of Bonn > Department of Computer Science > Chair V  
CSReports 19851989  Copyright 19851989 University of Bonn, Department of Computer Science, Abt. V  
8529 10.12.2008 
A Survey of Parallel Algorithms for Sparse Algebraic Interpolation
Thorsten Werther [Download PostScript] [Download PDF]
This paper gives a survey of some recent results on the parallel complexity of the sparse black box interpolation problem for multivariate polynomials and rational functions over arbitrary fields. In this setting, rather than the degree of the polynomial, the number of terms is of importance. Given a multivariate polynomial (or rational function) over an arbitrary field, as a black box (input oracle), and an information about its sparsity (a bound on the number of nonzero coefficients) we have to determine the complexity of reconstructing the polynomial. Some of the recent NCalgorithms and implementations using the computeralgebra system Scratchpad II are presented. 

Last Change:
12/10/08 at 15:01:17
Deutsch 
University of Bonn > Department of Computer Science > Chair V 