Computational Complexity of Sparse Rational Interpolation.
The authors analyze the computational complexity of sparse rational interpolation, and give the first deterministic algorithm for this problem with singly exponential bounds on the number of arithmetic  operations.
Introduction
In this paper we present an algorithm which, given a black box to evaluate a t-sparse (a
quotient of two t-sparse polynomials) n-variable rational function f with integer coefficients,
can find the coefficients and exponents appearing in a t-sparse representation of f using
t (nt) log d
black box evaluations and arithmetic operations and with arithmetic depth
(nt log d) O(1) , where d denotes the degree of t-sparse representation of f (see the Theorem
at the end of section 4 for an exact statement of this result). Although these bounds involve
the size of the exponents, this dependency only arises at the end of our algorithm. The
algorithm genuinely produces (that is produces in a way whose arithmetic complexity does
not depend on the size of the coefficients of f or on the degree of f , [19]) a polynomial whose
roots are p-powers (for some small p) of the exponents appearing in a t-sparse representation
of f . All known algorithms to find the roots of this polynomial (even knowing that they
are p-powers) have complexity that depend on the size of the roots. This dependency also
occurs in algorithms for interpolating t-sparse polynomials (c.f.,[1]) for the same reason.
To find the exponents appearing in some t-sparse representation of a t-sparse univariate
rational function f(X) we proceed as follows: We consider representations of f(X) of the
are real numbers. Such a function is
called a real quasirational function. Furthermore, we call such a representation minimal
if it has a minimal number of nonzero terms in the numerator and denominator and is
called normalized if some term is 1. We show that there are only a finite number of
minimal normalized representations and that the exponents must be integers. We are able
to produce a system T of polynomial equalities and inequalities (whose coefficients depend
on the values of f(X) at t O(t) points) that determine all the possible values of any such ff i
and fi i . Using the methods of [13], we can then find all ff i and fi i . To find the exponents
when multivariate polynomial, we show how to produce sufficiently many
n-tuples of integers (- such that the exponents of f can be recovered from the
exponents of all the f(X -
Complexity issues for t-sparse polynomial and rational function interpolation have
been dealt with in several papers. Polynomial (black box) interpolation was studied in
[1],[2],[9],[12],[17], [19],[27], [28]. For bounded degree rational interpolation (when the
bound on the degree is part of the input) see [15],[16],[25]. Approximative unbound interpolation
arises also naturally in issues of computational learnability of sparse rational
functions (cf. [21]). The present authors have previously studied the problem of interpolation
of rational functions in [10], but the algorithm presented there for finding the
exponents had considerably worse complexity. The present paper significantly improves
the results of that paper by introducing the notion of a minimal representation (allowing
us to directly compute a finite set of possible exponents instead of just bounding them)
and a new technique for reducing multivariate interpolation to univariate interpolation. As
we shall see these ideas give us a more efficient algorithm.
The rest of the paper is organized as follows: In Section 1 we give formal definitions
of a quasirational function and related concepts and prove some basic facts about these
functions. In Section 2 we introduce some useful linear operators on fields of these functions.
We use these operators to derive criteria for a function to be t-sparse. In Section 3 we
use these criteria to give an algorithm for t-sparse univariate interpolation. In Section 4,
we again use these operators to show how multivariate interpolation can be reduced to
univariate interpolation. Complexity analyses of the algorithms are also given in Sections
and 4.
Quasirational Functions
A finite sum
I
c I X I (1)
called a quasipolynomial
of n variables. The set of quasipolynomials forms a ring under the obvious operations and
we denote this ring by C The subring of quasipolynomials (1) with ff i 2 IR
and c I 2 IR will be referred to as the ring of real quasipolynomials and will be denoted
by ratio of two quasipolynomials (real quasipolynomials) is called a
quasirational function (real quasirational function). The set of such functions forms a
field that we denote by C hhX ii). Note that Q
We use the expressions "polynomial" or "rational function" in the usual
sense, that is for a quasipolynomial or quasirational function with non-negative integer
exponents in their terms.
We say that the quasipolynomial (1) is t-sparse if at most t of the c I are nonzero. If
a quasirational function f can be written as a quotient of a numerator that is t 1 -sparse
and a denominator that is t 2 -sparse then we say that f is )-sparse. For example,
2)-sparse and also (m; 1)-sparse. If f is
sparse but not 1)-sparse, we say that f is minimally
Note that the above example is both minimally (2; 2)-sparse and minimally (m; 1)-sparse.
We say that a representation
minimally )-sparse and p is t 1 -sparse and q is t 2 -sparse.
We will need a zero test for rational functions. This is similar to the
well known zero test for t-sparse polynomials (c.f., [1],[9],[11]). We assume that we are
given a black box for an n-variable rational function f with integer coefficients in which
we can put points with rational coefficients. The output of the black box is either the
value of the function at this point or some special sign, e.g., "1", if the denominator
of the irreducible representation of the function vanishes at this point (a representation
and h are relatively prime).
Lemma 1. Let f be a rational function of n variables, let
distinct primes and let
f is not identically zero
if and only if the black box outputs a number different from 0 and 1 at one of the points
Proof. Recall that if M are distinct positive numbers then any t \Theta t subdetermi-
nant of the r \Theta t matrix (M j
s ) 1-s-t; 1-j-r is non-singular (c.f., [5]). Since the black box gives
output based on an irreducible representation of f , we see that any zero of the denominator
of such a representation is zero of the denominator of a )-sparse representation of f .
Using the remark about the matrix (M j
above we see that the denominator can vanish at,
at these points. A similar argument applies to the numerator. Therefore,
the f is not identically zero if and only if the black box outputs a
number different from 0 and 1 at one of these points P j .
We note that Lemma 1 is not true for quasirational functions. For example, let
2 and
log 2 . We then have that f(2 i restricts
oneself to real quasirational functions, then Lemma 1 is also not true for n - 2. To see
this, let
3. However, we do have a zero
test for univariate real quasirational functions. We will only need such a test for real
quasipolynomials which we state in the following lemma.
Lemma 2. Let p be a positive real number and let f 2 IRhXi be t-sparse. If f(p i
Proof. Let
a 1
a 2
a
Since the ff i are real, p ff i 6= p ff j if i 6= j. Therefore the above t \Theta t matrix is non-singular
and so a
If f is a quasirational function, we call a representation
normalized if g or h contains the constant term 1. For an arbitrary representation h,
there are a finite number of monomials M such that (~g=M)=( ~ h=M) is normalized.
Lemma 3. a) Assume
p=-q are normalized representations of a multivariate
quasirational function and assume that p=q is a minimal
Then the ZZ-module generated by the exponent vectors of p and q is a submodule of the
ZZ-module generated by the exponent vectors of -
q.
There exist at most
thermore, for given exponent vectors, the coefficients in the corresponding minimal representation
are unique.
c) Assume the same conventions as in a). Then
Proof. Let I
be the exponent vectors of p, J
be the exponent vectors of
q and let f -
I i g (respectively f -
be the exponent vectors of - p (respectively - q). We define a
weighted directed graph G in the following way. The vertices of G correspond to the
exponents of p=q. We join I i and J j if I
I
for some assign the weight
I
to the edge
for some j
assign weight -
J j to the edge
Finally, we join J j and J
if
I
I
for some i
I
I i to the edge
We claim that G is connected. If not, let G o be the connected component which contains
the exponent vector One sees that the representation p obtained from p=q
by deleting all terms with exponent vectors not belonging to this connected component
p=-q. This contradicts the minimality of p=q and proves the claim.
To prove a) and c), consider a spanning tree T of G and let be the root of T .
Any exponent vector I i (respectively J i ) equals the sum of the weights along the unique
path connecting I i (respectively J i ) with the root and so lies in the module generated by
the -
I i and -
To prove b), note that the spanning tree above uniquely determines the set of exponent
vectors that can occur in p=q. Therefore the number of exponent vectors in the
numerator and denominator is at most the product of the number of such weighted trees
and
(the latter value being the number of choices of exponents for the numerator
and denominator). The number of rooted trees with vertices is at most
. For a fixed tree, the number of ways to assign weights of the above form
from a fixed set
I i
can be bounded by Thus the number of
exponent vectors can also be bounded by
We now prove the last statement of b). Assume that p are two different
representations with the same exponent vectors in the corresponding
numerators and denominators. For suitable c 2 C ,
is a representation that
is either contradicting the minimality of
completes the proof of Lemma 3.
We have the following immediate consequence of Lemma 3 a).
Corollary 4. Any normalized minimal quasi-rational representation of a
rational function has exponents that are integers.
Operators
In the following sections it will be useful to consider the actions of certain linear operators
on fields of quasirational functions.
be distinct prime numbers and let D
ii be the C -linear operator defined by D n (X ff
, where the number
i is defined to be e ff log p i for some fixed branch of the logarithm. When
write C hhXii instead of C hhX 1 ii and D instead of D 1 .
hhXii be the C -linear operator defined by
d
dX
Note that D n is a homomorphism, i.e. D n while D is a derivation,
i.e. difference will force us to deal with these operators
separately. We begin by studying D n .
Lemma 5. a) Let f 2 C (X assume that D n
assume that
Proof. a) If D n
implies that f(X
for new variables Y
I
a I X I
Comparing
coefficients of the corresponding monomials in X and Y we have that, after a suitable
re-ordering, I I for all I; J . Therefore f 2 C .
b) The proof is the same as in a) using Lemma 2 instead of Lemma 1.
Note that Lemma 5 a) is not true for f 2 IRhhX 2.
To see this let
not true for f 2 C hhXii
since, for
log 2 gives a counterexample.
Lemma 6. a) If y are linearly dependent
over C if and only if
b) If y are linearly dependent over IR if and only
Proof. a) If y are linearly dependent over C then we clearly have
Now assume that WDn (y In this case there exist
zero, such that
We may assume f Applying D n to each of these equations, we have
This implies that
m, in which case we are done by
Lemma 5, or by induction there exist ff all zero, such that ff 2 D n y
proof of part b) is similar and omitted.
Lemma 6 immediately implies the following criterion for a real quasirational function
to be
)-sparse if and only if there exist
I
)-sparse if and only if there exist
Proof. a) f is )-sparse if and only if there exist I
C , not all zero,
such that
a
happens if and only if
The proof of b) is similar.
We now consider the other linear operator D on C hhXii. We will need results similar
to Lemmas 5 and 6.
Lemma 8. If f 2 C hhXii and
Proof. First assume that
a
a
and a
Now let f 2 C hhXii. f is minimally
a minimal normalized representation. If then we have just shown
that h 2 C . Since
and so f 2 C . We will therefore now assume Dh 6= 0 and derive a contradiction. Since
or a 1)-sparse representation of f , a contradiction.
Lemma 9. If y are linearly dependent over C if and
only if
Proof. Lemma 8 implies that C hhXii is a differential field with constant subfield equal
to C . The result now follows from ([18], Theorem 3.7).
3 Univariate Interpolation
Lemma 7 in the previous section allows us to characterize rational functions
and is the basis of the following algorithm for finding the exponents of a sparse univariate
rational function.
Assume we are given a black box to evaluate a univariate rational function f 2
and assume we are told that it is minimally case when we are
only told it is )-sparse is handled below). Consider the expression
Note that S is a polynomial in the indicated terms with integer coefficients. Replacing
we get a polynomial
with at most terms in the
and multilinear in the black boxes
Since we are looking for the exponents of a normalized minimal
of f , we may assume Y
be a vector of such exponents if and only if
Observe that S as a rational function from IR(X) is
by lemma 1 condition (2) is equivalent to the condition that S is either 1 or 0 for
1. For at least
(being independent from ff
will be zero. Using the black box for f(X), we
can determine a system T consisting of equations in the unknowns
of degree at most
1 that is equivalent
to (2),(3) (for Y
has a finite number of
solutions in IR t 1 . Note that Corollary 4 implies that these solutions are integers. We
can apply the algorithm of [13], [14] (cf. also [1]) to this system and find these solutions
with
arithmetic operations and depth
d is the maximum of the exponents ff
. Note that the algorithm of [13], [14] will
yield a polynomial satisfied by these p-powers with operations
and As we noted in the introduction, the dependence on d of the final
complexity is introduced when we find the roots of this polynomial. One can find these
roots as in [23] or more simply by considering the powers of p that divide the coefficients.
We remark that this algorithm also implies that there are at most solutions
(cf. lemma 3b)) and that these solutions p ff are bounded by p d -
is a bound on the bitsize of the values yielded by the black box when
we evaluate f(p i+j ) for Hence
the exponents ff
of the rational function f do not exceed d -
Notice that the algorithm can find the exponents ff
in
arithmetic operations with the depth d) O(1) .
We can find the coefficients by solving a system of linear equations gotten from
a
by letting 1. Note that Lemma 3 b) implies that this system
will have a unique solution. This can be found with operations with
depth since to set up this system one has to compute powers p ff
which were computed above.
Turning to the general case where we are only told that f is )-sparse, we proceed
as follows: We consider all pairs (t 0
use the above
algorithm for these pairs. The first time that the above algorithm yields a non-empty
set of solutions, we are guaranteed that, for this (t 0
has a minimal (t 0
representation and that the algorithm has yielded the exponents and the coefficients.
4 Multivariate Interpolations
rational function given
by a black box. We shall show in this section how the problem of finding the exponent
vectors of f can be reduced to the univariate case. In particular, we shall show that the
set of vectors - minimally
)-sparse is a small set V . We will then show that if we find the exponents of f- for
sufficiently many - 62 V , then we can recover the exponents appearing in f .
Lemma 10. Let f(X rational function and let
linearly independent over ZZ. Then f(X
sparse.
Proof. Let ~
p(X)=~q(X) be a minimally ( ~
)-sparse representation of f(X -
with . By Lemma 3 a), we may assume that ~ p; ~ q 2 C [X -
Since the map sending X - i to X i induces an isomorphism of C (X
)-sparse representation of f(X
Lemma 11. Let f be a minimally rational function with integer coefficients.
The set V of vectors - 2 C n such that f- is not minimally )-sparse lies in the union of
at most determined by linear forms with integer coefficients.
Proof. We will first show that V is defined by a set of polynomial equalities and inequalities
with coefficients in Q (i.e. V is a Q -constructible set). Let
ables. We shall write down conditions on V Vn ) is
sparse, let these conditions determine a set W (1) (similar conditions can be derived for
Vn ) to be these conditions determine a set W (2) ). Thus
implies that f(X Vn ) is )-sparse if and only if
there exist ff
2 C such that ff i
Vn Vn
Vn Vn
When we clear the denominator of (4) we will get a linear function in expressions of the
, that are polynomials in
coefficients. Observe that there are at
most that can appear
For any pair \Sigmaa states
that for any choice (-
if and only if there exist ff
2 C such that all the C a considered
above vanish. Let \Phi be the formula, from the language of algebraically closed fields, with
bound variables ff
that expresses this
latter statement. This formula contains at most polynomials, each of degree
at most
Applying the results of [6] (see also [4]), we can eliminate quantifiers and get a quantifier
equivalent to \Phi. Furthermore, the polynomials
occurring in \Psi have degrees at most (t 1 and there are at most (t 1
of these. This formula determines a constructible set W 0 ae C n . As it was shown above the
symmetric difference (W (1) n W lies in a union of all
of the kind L a;b for considered above integer vectors a; b. ?From Lemma 10, we know
that for each point (- there exists a relation
not all zero. ?From Lemma 12 of the appendix we know that each irreducible
component of W 0 (and also of W) lies in a hyperplane. Therefore W lies in the union of at
most determined by linear forms with integer coefficients.
We now proceed to describe an algorithm to find p-powers of the exponents of a minimally
normalized rational function f .
For any c ? 0 using the construction from ([11] or [12], Lemma), one can explicitly
produce, for suitable
where the integers 1 - (i)
)n such that for any family of
hyperplanes (containing the origin) at least n of these vectors lie in none
of these hyperplanes and any n of these vectors are linearly independent. We take c ? 0
such that the number of hyperplanes in lemma 11 is at most for the
algorithm we have only to estimate explicitely constant c once and forever) and apply to
this c the construction mentioned above. For each of the vectors - (i) produced in this
way, use the algorithm from Section 3 to find t (i)- t 1 , t (i)- t 2 such that the rational
function f - (i) 2 Q (X) has a minimal (t (i)
)-sparse representation. By Lemma 11 and
the construction of the - (i) , there exist at least n vectors among the - (i) (without loss of
generality we let them be - )-sparse for all
Using the algorithm from section 3 we find p-powers of the exponents of all
normalized )-sparse representations of f - (i) for each 1 - i - n (recall that there are at
most of these). For each f - (i) , 1 - i - n, pick out one set of such p-powers
of the exponents p ff (i)
. For each pick out two
permutations
and oe (i)
, where Sm is the permutation group on m elements.
For every the algorithm solves the p-power form of a linear system
and for every
Using [22] the algorithm produces the inverse matrix (- (i)
n \Theta n matrix (- (i)
k ), which is invertible because of the construction of the vectors - (i) .
1-i-n
ff (i)
and the algorithm computes the right side of this equal-
ity. The algorithm also computes p -Z (j 2 )
k . Similar computations can be made for different
primes p. The vectors Y
are considered as candidates for being
exponents vectors in the numerator and denominator of a
of f . The algorithm represents them by p -Y (j 1 )
k . The algorithm tests, whether
The then algorithm tests whether these candidates fit. For this aim consider a linear
system
l
l
in the unknown coefficients OE of the )-sparse representation of f currently being
tested. (In (7) we skip the equations for which f(p -l
that (7) is solvable if and only if exponent vectors Y (j) ; Z (j) fit (we apply here lemma 1
probably not to rational functions, since the exponents Y (i)
k could be rational, but it
is still valid by making a replacement of the variables
-l
n). If (7) is
solvable then Y (i)
are integers because of lemma 3a), moreover it has a unique solution
by lemma 3b). This completes the description of the algorithm for f being minimally
To treat the case when we are only told that f is )-sparse, we proceed
as in Section 3.
Now we proceed to the complexity bounds. Let us assume we are given the black box for
a rational function. The algorithm produces vectors
- (i) and, for each of these, applies the algorithm from Section 3 to the univariate rational
function f - (i) . This part of the algorithm requires
operations with depth ((t 1 +t 2 )n log d) 0(1) . The algorithm then selects, for each
some )-sparse representation of f - (i) and also two permutations - (i) ; oe (i) . This is again
within the same bounds. The algorithm then solves p-power forms of linear
systems of type (5), (6). To invert n \Theta n matrix (- (i)
operations are used
with depth log 0(1) n. Since - (i)
can be done within the same complexity bounds. The same applies to solving system (7).
If we are only told that f is )-sparse, the additional search required by the algorithm
does not change the complexity.
We are also able to give some bounds on the degree d of a sparse representation. Assume
that A is a bound for all the exponents ff (i)
found for the univariate rational functions
(such a bound can be found using the techniques of Section 3). We can then bound d
by looking at p-power forms of the linear systems (5) and (6); in fact d - A(t 1
Thus, we can formulate the main result of the paper:
Theorem. 1) One can construct some
sentation
a
rational function f
in
arithmetic operations with the depth d) O(1) .
2) the exponents j (i)
l do not exceed d - is the bound
on bitsizes of all the outputs of applications of a black box during the computation.


Appendix

. For the convenience of the reader, we give a short proof of the result about
complex varieties that was needed in the proof of Lemma 11. This result is true for varieties
over any algebraically closed field of characteristic 0, but the proof is more complex and
depends on the Hilbert Irreducibility Theorem instead of elementary topological notions.
Lemma 12. Let W be an irreducible constructible set in C n (i.e. a constructible set
whose Zariski closure is irreducible). Assume that for each - there exist
not all zero, such that
there exist ~
all zero, such that
Proof. If W has dimension 0, then it is a point and we are done. Therefore assume
By definition, W is open in its Zariski closure W. Therefore there exists
a point - 2 W that is non-singular in W. We select a sufficiently small ffl such that
will be closed in the usual topology and contain an open
subset of W. For each (fl
0g. Since W ffl is closed, the Baire Category Theorem ([24], p. 139) implies
that for some (~fl
contains an open subset of W ffl (and so, of W). Therefore
dim(H ~
is irreducible, we must have (H ~
[26], p. 54) so W ' H ~

Acknowledgement

. We are indebted to Volker Strassen for motivating the problem and
a number of simulating discussions.



--R

A Deterministic Algorithm for Sparse Multivariate Polynomial Interpolation
On the Decidability of Sparse Univariate Polynomial Interpolation
An Algorithm of Polynomial Complexity for Factoring Polynomials and Finding the Components of a Variety in Subexponential Time
Complexity of quantifier elimination in the first-order theory of algebraically closed fields
Generalized Vandermonde Determinants and Roots of Unity of Prime Order
Sequential and parallel complexity bounds for the quantifier elimination of algebraically closed fields
Factoring Polynomials over a Finite Field and Solving Systems of Algebraic Equations
Complexity of deciding Tarski algebra
The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents is in NC
Interpolation of Sparse Rational Functions without Knowing Bounds on Exponents
Fast Parallel Algorithms for Sparse Multi-variate Polynomial Interpolation over Finite Fields
The interpolation problem for k-sparse sums of eigenfunctions of operators
Solving Systems of Polynomial Inequalities in Subexponential Time
Complexit'e du principe de Tarski-Seidenberg
Uniform Closure Properties of P
Computing with Polynomials Given by Black Boxes for Their Evaluations: Greatest Common Divisors
Improved Sparse Multivariate Polynomial Interpolation
An Introduction to Differential Algebra
Boolean Circuit Complexity of Algebraic Interpolation Problems
Meyer auf der Heide
VC Dimension and Learnability of Sparse Polynomials and Rational Functions
A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
Some polynomial and Toeplitz matrix computations
Real Analysis

Basic Algebraic Geometry
Probabilistic Algorithms for Sparse Polynomials
Interpolating Polynomials from their Values
--TR

--CTR
Y. N. Lakshman , B. David Saunders, On computing sparse shifts for univariate polynomials, Proceedings of the international symposium on Symbolic and algebraic computation, p.108-113, July 20-22, 1994, Oxford, United Kingdom
Mark Giesbrecht , Erich Kaltofen , Wen-shin Lee, Algorithms for computing the sparsest shifts of polynomials via the Berlekamp/Massey algorithm, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.101-108, July 07-10, 2002, Lille, France
Mark Giesbrecht , Erich Kaltofen , Wen-shin Lee, Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases, Journal of Symbolic Computation, v.36 n.3-4, p.401-424, September
Zhang , Rajiv Gupta, Hiding program slices for software security, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
Adam R. Klivans , Daniel Spielman, Randomness efficient identity testing of multivariate polynomials, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.216-223, July 2001, Hersonissos, Greece
Amir Shpilka, Interpolation of depth-3 arithmetic circuits with two multiplication gates, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
Dima Yu. Grigoriev , Y. N. Lakshman, Algorithms for computing sparse shifts for multivariate polynomials, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.96-103, July 10-12, 1995, Montreal, Quebec, Canada
Gudmund S. Frandsen , Igor E. Shparlinski, On reducing a system of equations to a single equation, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.163-166, July 04-07, 2004, Santander, Spain
Erich Kaltofen , Wen-shin Lee, Early termination in sparse interpolation algorithms, Journal of Symbolic Computation, v.36 n.3-4, p.365-400, September
Igor E. Shparlinski, Sparse polynomial approximation in finite fields, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.209-215, July 2001, Hersonissos, Greece
interpolation;sparse rational functions;arithmetic operations;computational complexity