Department of Computer Science
Chair V

University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1985-1989 Copyright 1985-1989 University of Bonn, Department of Computer Science, Abt. V


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 non-zero coefficients) we have to determine the complexity of reconstructing the polynomial. Some of the recent NC-algorithms and implementations using the computer-algebra system Scratchpad II are presented.

This paper is a revised version of a thesis for a Master's Degree in Computer Science, University of Bonn, August 1988.

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