
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 19851989  Copyright 19851989 Universität Bonn, Institut für Informatik, 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
English 
Universität Bonn > Institut für Informatik > Abteilung V 