Time–space tradeoffs for polynomial evaluation

Mikel ALDAZ, Joos HEINTZ, Guillermo MATERA, José Luis MONTAÑA and Luis Miguel PARDO

                        This paper is published in
            Comptes Rendus de l'Academie des Sciences de Paris
                     t.327, Série I, 1998, pp.907-912.

M.A., J.L.M. : Departamento de Matemática e Informática, Universidad Pública de Navarra, Campus de Arrosadía E–31006 Pamplona, España; mikaldaz,pepe@upna.es J.H., L.M.P. : Departamento de Matemáticas, Estadística y Computación, Universidad de Cantabria, E–39071 Santander, España; heintz,pardo@matesco.unican.es J.H., G.M. : Departamento de Matemáticas, Universidad de Buenos Aires, Ciudad Universitaria (1428) Buenos Aires, Argentina; joos,gmatera@dm.uba.ar

Abstract. We develop a new method for showing lower bounds for the time–space tradeoff of polynomial evaluation procedures given by straight–line programs. By means of this method we prove an asymptotically sharp lower bound for the time–space tradeoff of general procedures of polynomial evaluation and exhibit specific families of univariate polynomials where this bound is reached.

Le rapport entre le temps et l’espace pour l’évaluation des polynômes.

Résumé. Nous présentons une méthode qui nous permet pour la première fois d’exhiber des bornes inférieures optimales pour le rapport entre le temps et l’espace lors de l’évaluation de polynômes en une variable. A l’aide de cette méthode nous obtenons une estimation asymptotiquement exacte de ce rapport dans le cas des polynômes génériques. Nous déterminons aussi le rapport entre le temps de calcul et l’espace de mémoire pour certaines familles explicites de polynômes.

Version française abrégée

On étudie le rapport entre le temps de calcul et l’espace de mémoire dans les procédures (numériques) d’évaluation des polynômes en une variable. Notre approche est fondée sur le modèle théorique des circuits arithmétiques et sur les jeux de jetons (pebble games) dans les graphes orientés acycliques. Un circuit arithmétique (representé par un graphe acyclique) muni d’un jeu de jetons est appelé un calcul d’évaluation ou straight–line program (voir [2]). Notre méthode de démonstration de bornes inférieures pour le rapport entre le temps et l’espace lors de l’évaluation de polynômes se base sur une analyse géométrique de la notion d’un calcul d’évaluation de longueur non–scalaire L et d’espace de mémoire S. En révisant sous cet angle l’algorithme de Horner pour l’évaluation d’un polynôme F de degré d on obtient la borne supérieure LS^{2} = 4d pour le rapport LS^{2} entre le temps non–scalaire L et l’espace de mémoire S simultanément nécessaires pour évaluer F . Par un argument traditionel de dimension (ou de comptage) on déduit que cette borne est asymptotiquement optimale pour tous les polynômes de degré au plus d et à coefficients suffisamment génériques. Le resultat précis est le suivant:

Théorème 1. Soient donnés un corps infini K et un nombre naturel d. Soit X une indéterminée sur K. Il existe alors un ouvert non vide U dans la topologie de Zariski de K^{d+1} tel que pour tout polynôme F ∈ K[X] de degré au plus d et à coefficients dans U et pour tout algorithme qui évalue F en temps non–scalaire L a l’aide d’un espace de mémoire S, on a l’inégalité LS^{2} ≥ \frac{d}{8} .

D’après [7] et [4] nous appelons difficiles à calculer (dans le sens du rapport entre le temps et l’espace) les polynômes qui appartiennent à l’ensemble U introduit dans l’enoncé du théorème précédent. Notre résultat implique que tous les polynômes en une variable et suffisamment génériques de degré au plus d requièrent un espace de mémoire S ≥ c ^{4} \sqrt{d} pour leur évaluation en temps non–scalaire optimal (où c est une constante appropiée). Finalement nous utilisons notre méthode géométrique pour l’exhibition de familles spécifiques de polynômes en une variable qui sont difficiles à calculer dans notre sens. L’aspect nouveau de notre approche consiste en une analyse fine de la hauteur d’une fibre donnée d’un certain morphisme entre espaces affines. Les conclusions de cette analyse représentent l’outil principal pour borner inférieurement le rapport entre le temps et l’espace de certains polynômes à coefficients entiers. Le cas des polynômes à coefficients algébriques sur 0 Q est traité par une adaptation de la méthode du degré géometrique introduit dans [4] (voir aussi [3]). Voici les résultats obtenus:

Théorème 2. Dans les estimations (1)–(4) qui suivent, (F_{d})_{d∈IN} est une famille de polynômes à coefficients entiers, le polynôme F_{d} ayant degré d. Dans l’estimation (5) les coefficients de F_{d} sont algébriques sur 0 Q . Pour chaque polynôme F_{d} soit donné un calcul d’évaluation de longueur non–scalaire L et d’espace de mémoire S. On a alors les bornes inférieures suivantes:

(1) Pour F_{d} := ∑_{0≤j≤d} 2^{j!}X^{j} on a LS^{2} = Ω(d) .

(2) Pour F_{d} := ∏_{0≤j≤d}(X − 2^{2^{j}}) ou F_{d} := ∏_{0≤j≤d}(X − 2^{j!}) on a LS^{2} = Ω(\frac{d}{log_{2} d}) .

(3) Plus généralement, pour F_{d} := ∑_{0≤j≤d} 2^{2^{⌊ ^{k} \sqrt{j}⌋}}X^{j} ou F_{d} := ∏_{0≤j≤d}(X − 2^{2^{⌊ ^{k} \sqrt{j}⌋}}) on

a LS^{2} = Ω(\frac{\sqrt[k]{d}}{log_{2} d}) si k ≥ 1 est un nombre naturel quelconque.

(4) Soit f_{j} le j –ième nombre de Fibonacci. Alors pour F_{d} := ∑_{0≤j≤d} 2^{f_{j}}X^{j} ou F_{d} := ∏_{0≤j≤d}(X − 2^{f_{j}}) on a LS^{2} = Ω(\frac{d}{log_{2} d}) .

(5) Soit p_{j} le j –ième nombre premier. Alors pour F_{d} := ∑_{1≤j≤d} \sqrt{p_{j}}X^{j−1} ou F_{d} := ∏_{1≤j≤d}(X − \sqrt{p_{j}}) on a LS^{2} = Ω(\frac{d}{log_{2} d}) ().

A nouveau nous pouvons conclure que tout polynôme F_{d} de la liste du théorème précédent exige un espace S = Ω( ^{4} \sqrt{d}) pour son évaluation en temps non–scalaire optimal. Observons ici qu’il s’agit de la première fois qu’on obtient une méthode capable de minorer le rapport entre le temps de calcul et l’espace de mémoire pour un problème algébrique avec une seule sortie. Finalement nous appliquons notre méthode à des problèmes classiques de transcendance de séries formelles.

1 Introduction

Computer oriented algorithmics often requires simultaneous optimization of more than one complexity measure. In this sense we are going to study the interplay between the (computational) issue of time and space in the case of (numerical) evaluation of univariate polynomials. Our theoretical model is that of the straight–line programs (or arithmetic circuits) represented by directed acyclic graphs (DAGs) on which we play a pebble game (see [2]). A particularity of our model is that any polynomial can be evaluated in constant memory space (as one easily sees analyzing Horner’s rule). However computation time cannot be compressed arbitrarily in polynomial evaluation, the logarithm of the degree being a universal lower bound. This motivates the study of time-space tradeoffs or alternatively the behaviour of memory space under the assumption of time-optimal algorithms. Our method for obtaining lower bounds for the time–space tradeoff of polynomial evaluation is based on a geometrical interpretation of the notion of a straight–line program of given nonscalar time L and storage space S. Time is measured by the number of pebble placements on nodes of the given DAG representing nonscalar multiplications/divisions. Storage space is measured by the maximal number of pebbles used during the game. The time–space tradeoff function under consideration is LS^{2} . We show in Section 2 that for “almost all” univariate polynomials of degree at most d our time–space tradeoff function satisfies the inequality LS^{2} ≥ \frac{d}{8} . From this result we conclude that for “almost all” univariate polynomials of degree d, any nonscalar time– optimal evaluation procedure requires space at least S ≥ c ^{4} \sqrt{d}, where c > 0 is a suitable universal constant. In Section 3 we develop a strategy which allows us to exhibit specific families of univariate polynomials which are “hard to compute” in the sense of time–space tradeoffs (this means that our tradeoff function increases linearly in the degree). We finally apply our method to classical questions of transcendence of formal power series.

2 The time–space tradeoff of general procedures for polynomial evaluation

The purpose of this section is to establish a lower bounds for the time–space tradeoff of general procedures for the evaluation of univariate polynomials. First of all let us observe that the computation DAG associated to Horner’s rule for the evaluation of a univariate polynomial P of degree d can be pebbled using exactly two pebbles in total time 2d and nonscalar time d. Let L and S denote nonscalar time and the space used by the Horner algorithm for the evaluation of the polynomial P . Then L and S satisfy the obvious time–space tradeoff upper bound LS^{2} = 4d. We are now going to prove that this bound is asymptotically exact for almost all univariate degree d polynomials over any given infinite field K. Therefore let be given an infinite field K and let X be an indeterminate over K.

Using a simple counting argument we deduce that any straight–line program β using nonscalar time L and space S can be described by means of N := 8LS^{2} parameters. Using a method inspired by [7] we analyze how the output F of the straight–line program β depends on these parameters if F is a polynomial belonging to K[X] . By a straightforward normalization of our computational model we may assume without loss of generality that each (nonscalar) step of β consists of a multiplication or division of two linear combinations of previous results of β. In case of a division a suitable parameter change allows us to represent the rational function under consideration as a formal power series in K[[X]] . This yields a recursion between the coefficients of the intermediate results of β seen as elements of K[[X]] . From this recursion we deduce immediately the following technical result which represents our main tool for the inference of lower bounds for the time–space tradeoff of univariate polynomials:

Lemma 1. Let d, L, S be given natural numbers, let N := 8LS^{2}+1 and let Z_{1} …, Z_{N} be new indeterminates. Then there exist polynomials P_{d}, …, P_{0} ∈ ZZ[Z_{1}, …, Z_{N}] of degree and weight bounded by 2(Ld + 1) and (d + 1)!(4(S + 1))^{(d+1)^{L+1}} respectively such that the morphism of affine spaces Φ_{d,L,S} : K^{N} ⟶ K^{d+1} defined by these polynomials has the following property: for any polynomial F ∈ K[X] of degree at most d which can be computed by a straight–line program using at most nonscalar time L and space S, the point (f_{d}, …, f_{0}) ∈ K^{d+1} given by the representation F = ∑_{0≤i≤d} f_{i}X^{i} belongs to the image of Φ_{d,L,S}.

From Lemma 1 we deduce our first complexity result. This result characterizes the intrinsic time–space tradeoff of “almost all” univariate polynomials of degree at most d. It generalizes the main outcome of [6] and shows that Horner’s rule is asymptotically optimal in terms of time–space tradeoffs.

Theorem 2. Let d be a given natural number. Then there exists a nonempty Zariski open subset U of K^{d+1} such that for any polynomial F ∈ K[X] of degree at most d with F ∈ U and for any algorithm which evaluates F in nonscalar time L and memory space S the tradeoff estimate LS^{2} ≥ \frac{d}{8} holds.

The proof of Theorem 2 is based on the simple observation that the dimension of the image of the morphism Φ_{d,L,S} of Lemma 1 is at most 8LS^{2} + 1 . In analogy with [7] and [4] we call polynomials like those which belong to the set U hard to compute in terms of time–space tradeoff.

From Theorem 2 we also obtain lower bounds for the space complexity for any time optimal evaluation procedure of univariate polynomials. Following [6] there exists a constant c > 0 such that any polynomial F ∈ K[X] of arbitrary degree d can be evaluated by a straight– line program in K[X] in nonscalar time not exceeding c\sqrt{d}. Combining this result with Theorem 2 we have:

Corollary 3. There exist a constant c′ > 0 with the following property: let d be a given natural number and let U be the nonempty Zariski open subset of K^{d+1} introduced in Theorem 2. Then for any polynomial F ∈ K[X] of degree at most d satisfying the condition F ∈ U and for any straight–line program β in K(X) which evaluates F in optimal nonscalar time the space S(β) required by the procedure β is bounded from below by S(β) ≥ c′ ^{4} \sqrt{d}.

3 Families of polynomials hard to compute

We develop now a global strategy for the exhibition of specific families of univariate polynomials which are hard to compute in the above sense. The new aspect of our strategy consists in a problem adapted analysis of the height of points lying in a given fiber of a suitable 0 Q –definable algebraic morphism of affine spaces. Let be given a specific polynomial F ∈ K[X] of degree d. In order to prove a lower bound on the time–space tradeoff of any straight–line program evaluating F we are faced with the following situation: only from the knowledge of the coefficients of F we have to deduce a lower bound for the quantity LS^{2} where L and S are natural numbers satisfying the condition F ∈ imΦ_{d,L,S} with Φ_{d,L,S} defined as in Lemma 1. This lemma establishes a link between the size of the complexity parameters L and S and the degree and height of the algebraic morphism Φ_{d,L,S}. Therefore we need a tool which allows us to estimate these geometric invariants from the knowledge of just one specific point belonging to the image of the morphism Φ_{d,L,S}. The following result yields such a tool:

Proposition 4. Let N , d, D and η be given natural numbers and let Φ := (P_{d}, …, P_{0}) : C^{N} ⟶ C^{d+1} be a morphism of affine spaces with P_{0}, …, P_{d} being polynomials belonging to ZZ[Z_{1}, …, Z_{N}] . Let F be a given point of ZZ^{d+1} . Consider the Φ –fiber V := Φ^{−1}(F) of the point F as a 0 Q –definable Zariski closed subvariety of C^{N} . Suppose that V is nonempty. Let h_{1}, …, h_{s} ∈ ZZ[Z_{1}, …, Z_{N}] be polynomials satisfying the following conditions:

1. V := {z ∈ C^{N} : h_{1}(z) = 0, …, h_{s}(z) = 0}

2. max{deg(h_{i}) : 1 ≤ i ≤ s} ≤ D and

3. max{log_{2} height(h_{i}) : 1 ≤ i ≤ s} ≤ η

Then, there exists a point θ = (θ_{1}, …, θ_{N}) of the fiber V satisfying the estimate log_{2} max {| θ_{i} | : 1 ≤ i ≤ N} ≤ D^{cN}(log_{2} s + η) , where c > 0 is a suitable universal constant.

In order to prove the proposition we translate the question into the problem of estimating heights of the isolated points of a diophantine variety. This allows us to apply the height estimates of e.g. [5]. For this purpose, we show that it is possible to intersect the variety V of the statement of Proposition 4 with r := dim(V) hyperplanes H_{1}, …, H_{r} of controlled height in such a way that V ∩H_{1} ∩⋯∩H_{r} is a nonempty finite set. The existence of such hyperplanes is shown by making use of suitable versions of the effective Nullstellensätze and Bézout Inequalities from geometric and arithmetic elimination and intersection theory. Proposition 4 is our main tool for the analysis of the heights of points lying in the fiber V := Φ_{d,L,S}^{−1}(F) of a given univariate polynomial F . The conclusions of this analysis constitute our key argument for establishing time–space tradeoffs lower bounds for univariate polynomials with integer coefficients. As an application of our method we obtain the following time–space tradeoff lower bounds:

Theorem 5.

(1) The family (F_{d})_{d∈IN} of polynomials with F_{d} := ∑_{0≤j≤d} 2^{j!}X^{j} has a time–space tradeoff LS^{2} = Ω(d) .

(2) The families (F_{d})_{d∈IN} of polynomials with F_{d} := ∏_{0≤j≤d}(X − 2^{2^{j}}) and

F_{d} := ∏_{0≤j≤d}(X − 2^{j!}) have time–space tradeoff LS^{2} = Ω(\frac{d}{log_{2} d}) .

(3) More generally, the families (F_{d})_{d∈IN} of polynomials with F_{d} := ∑_{0≤j≤d} 2^{2^{⌊ ^{k} \sqrt{j}⌋}}X^{j}

and F_{d} := ∏_{0≤j≤d}(X − 2^{2^{⌊ ^{k} \sqrt{j}⌋}}) have time–space tradeoff LS^{2} = Ω(\frac{\sqrt[k]{d}}{log_{2} d}) for any k ∈ IN .

(4) For f_{j} being the j –th Fibonnacci number the families (F_{d})_{d∈IN} of polynomials with F_{d} := ∑_{0≤j≤d} 2^{f_{j}}X^{j} and F_{d} := ∏_{0≤j≤d}(X − 2^{f_{j}}) have time–space tradeoff LS^{2} = Ω(\frac{d}{log_{2} d}).

The case of polynomials with algebraic coefficients over 0 Q is treated using an adaptation of the degree method of [4] (see also [3]). We obtain the following results:

Theorem 6. Let p_{j} be the j –th primer number. The following families (F_{d})_{d∈IN} of polynomials with algebraic coefficients have time–space tradeoff LS^{2} = Ω(\frac{d}{log_{2} d}) :

(1) F_{d} := ∑_{1≤j≤d} \sqrt{p_{j}}X^{j−1} (2) F_{d} := ∏_{1≤j≤d}(X − \sqrt{p_{j}}) .

Our time–space tradeoff results imply that any nonscalar time optimal algorithm which evaluates any of the mentioned polynomial families needs at least space S = Ω( ^{4} \sqrt{d}) . Let us observe that to our knowledge our method is the first one which is able to produce time– space tradeoff lower bounds for algebraic computation problems with just one output.

Our general complexity method can also be applied to classical questions of transcendence of formal power series over an infinite field. Our method implies the following results:

Theorem 7. [1] The following power series belonging to 0 Q[[X]] are transcendental over the function field 0 Q(X) :

(1) ∑_{j≥0} \frac{1}{2^{2^{j}}} X^{j}. (2) ∑_{j≥0} _{\frac{1}{2^{2^{⌊ ^{k} \sqrt{j}⌋}}}} X^{j}, for any k ∈ IN .

(3) ∑_{j≥0} _{\frac{1}{2^{2^{⌊log^{k}_{2}j⌋}}}} X^{j}, for any k ∈ IN with k ≥ 3 .

Acknowledgments : Research was partially supported by the following Argentinian and Spanish grants : UBACYT EX–001, PIP CONICET 4571, DGICYT PB96–L–02–00.

The authors would like to express their gratitude to Alan Borodin and Jacques Morgenstern for inspiring this work through many discussions on the subject.

References

[1] Aldaz M., 1997. Ph. D. Thesis (work in progress). University of Navarra.

[2] Borodin A., 1993. Time–space tradeoffs (getting closer to the barrier?). Proc. of the 4th ACM–SIGSAM Int. Symp. ISAAC’93, Springer LNCS, 762, pp. 209–220.

[3] Heintz J. and Morgenstern J., 1993. On the intrinsic complexity of elimination theory. J. of Complexity, 9, pp. 471–498.

[4] Heintz J. and Sieveking M., 1980. Lower bounds for polynomials with algebraic coefficients. Theoret. Comput Sci., 11, pp. 321–330.

[5] Krick T. and Pardo L.M., 1996. A Computational Method for Diophantine Approximation. Progress in Mathematics, 143, Birkhäuser Verlag, pp. 193–254.

[6] Paterson M.S. and Stockmeyer L.J., 1973. On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM Journal of Computing, 2(1), pp. 60–66.

[7] Strassen V., 1974. Polynomials with rational coefficients which are hard to compute. SIAM J. Comput., 3, pp. 128–149.