Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1985-1989 Copyright 1985-1989 Universität Bonn, Institut für Informatik, 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
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope