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 Deterministic Algorithm for Rational Function Interpolation
Dimar Grigoriev and Marek Karpinski
[Download PostScript] [Download PDF]

We construct a deterministic polynomial time (deterministic boolean NC [C 85]) algorithm for interpolating arbitrary t-sparse rational functions. It is the first deterministic polynomial time algorithm for this problem. Given an arbitrary rational function f (in the most general setting given by a black box), such that f = P/Q, P,QZ[x1, ..., xn] for P. Q t-sparse, relatively prime, with coefficients bounded in absolute value by 2n, and such that degxi(P), degxi(Q) < d, the algorithm works in O(log3(ndt)) boolean parallel time and O(n4d7.5t17.5log n log d log t) boolean processors. (In general, if the coefficients of P and Q are bounded in the absolute value by the function S. S: NN, S(n) ≥ n, there exists an implementation (cf. [BCP 83]) of our algorithm in NC3(log S).)

Having established the above deterministic circuit complexity upper bounds for the Rational Function Interpolation, the very challenging practical matter arises to improve on the number of boolean processors (or the sequential deterministic time) of our algorithm.

Last Change: 12/05/08 at 09:10:11
University of Bonn -> Department of Computer Science -> Chair V