
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 19851989  Copyright 19851989 Universität Bonn, Institut für Informatik, Abt. V  
8526 05.12.2008 
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 tsparse 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,Q ∈ Z[x_{1}, ..., x_{n}] for P. Q tsparse, relatively prime, with coefficients bounded in absolute value by 2^{n}, and such that deg_{xi}(P), deg_{xi}(Q) < d, the algorithm works in O(log^{3}(ndt)) boolean parallel time and O(n^{4}d^{7.5}t^{17.5}log 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: N → N, S(n) ≥ n, there exists an implementation (cf. [BCP 83]) of our algorithm in NC^{3}(log S).) 

Last Change:
12/05/08 at 09:10:11
English 
Universität Bonn > Institut für Informatik > Abteilung V 