The intrinsic complexity of parametric elimination methods

J. Heintz, G. Matera, L. M. Pardo, R. Wachenchauzer

October 23, 1997

Abstract This paper is devoted to the complexity analysis of a particular property, called geometric robustness owned by all known symbolic methods of parametric polynomial equation solving (geometric elimination). It is shown that any parametric elimination procedure which owns this property must necessarily have an exponential sequential time complexity even if highly performant data structures (as e.g. the straight–line program encoding of polynomials) are used. The paper finishes with the motivated introduction of a new nonuniform complexity measure for zero-dimensional polynomial equation systems, called elimination complexity.

Keywords. Polynomial system solving, elimination, complexity.

Research was partially supported by the following Argentinian and Spanish grants : UBA-CYT.EX.001, PIP CONICET 4571, DGICYT PB96–0671–C02–02.

1 Introduction

Modern algebraic geometry started about 200 years ago as algorithmic algebraic geometry, and, more precisely, as algorithmic elimination theory. The motivation for the creation of such a field was the search for methods which allow to find the real solutions of a polynomial equation system. Nevertheless, the very origin of algebraic geometry was given by the observation that real root finding is a rather infeasible task without a previous study of the behaviour of the complex solutions of polynomial equation systems. This observation was first made by Euler and Bézout and then extended to a general theory by a long list of geometers of the last century. This list includes names as Jacobi, Sylvester, Kronecker, M. Noether, Hilbert (the creator of modern commutative algebra), Castelnuovo, Bertini, Enriques.

Unfortunately modern algebraic geometry deviated from its origins (mainly after World War II) and todays written contributions to this field are authentic masterpieces in the art of boring the reader. Nevertheless in the last twenty years a new community of old algebraic geometers doing symbolic computation splitted out of the mainstream. The intention of this community to bring back algebraic geometry to its origin (and to introduce also new aspects like efficient polynomial equation solving for industrial applications) must be praised highly. On the other hand the (mainly rewriting based) computational approach used by this community is far too simple minded for the difficult task of efficient, i.e. real world polynomial equation solving. An important drawback of this approach consists in the almost total absence of todays skill in algorithmics and data structure manipulation as well as the unawareness of modern programming techniques coming from software engineering. There is no place here to describe in detail the advances and weaknesses of symbolic computation (more precisely: computer algebra) techniques applied to elimination theory. For an overview about rewriting based methods (Gröbner basis techniques) we refer to the books [20], [15], [6] (these books include also motivations and historical considerations). The state of the art in sparse techniques can be found in [7]. Finally the seminumerical approach to elimination theory is described in the book [3] and the surveys [13], [17], [12] and in the research papers [11], [10] and [1].

It is well known that there exists no polynomial time geometric or algebraic elimination procedure if dense encoding of polynomials is used as basic data structure (see e.g. [14], [13], [17]). One may ask whether this conclusion remains still true for elimination procedures based on the more succinct straight–line program encoding of polynomials as fundamental data structure (see e.g. [13], [17], [4]).

In this paper we will give a partial answer to this question. We introduce and discuss the notion of a geometrically robust parametric elimination procedure. The main outcome is the observation that all known parametric elimination procedures are geometrically robust and that all geometrically robust parametric elimination procedures must necessarily have an exponential time complexity even if the highly performant encoding of polynomials by straight–line programs is used (Theorem 1). Therefore a revolutionary change of mathematical theory and algorithmics would be necessary in order to design a (possibly non-existent) highly performant general purpose elimination procedure. The rest of the paper is devoted to the motivated introduction of a new uniform complexity measure for zero-dimensional polynomial equation systems, called elimination complexity.

The procedures (algorithms) considered in this paper operate with division–free arithmetic circuits as basic data structure for the representation of inputs and outputs. In his turn such a circuit depends on certain input nodes, labeled by indeterminates over a given ground field k. These indeterminates are thought to be subdivided into two disjoint sets representing the parameters and variables of the given circuit. The output nodes of the circuit represent polynomials in the parameters and variables of the circuit. On the other hand the output nodes are labeled by sign marks of the form “= 0” or “≠ 0” or remain unlabeled. Thus the given circuit defines by means of its labeled output nodes a system of polynomial equations and inequations which determines in his turn a locally closed set with respect to the Zariski topology of the (affine) space of parameter and variable instances. The unlabeled nodes of the given circuit determine a polynomial map (in fact a morphism of algebraic varieties) which is defined on this locally closed set. We shall interpret the system of polynomial equations and inequations determined by the given circuit as a parametric system in the variables of the circuit. The same point of view is applied to the morphism determined by the unlabeled nodes of the circuit. We say that a given parameter point fixes an input/output instance of the procedure under consideration. Input and output instances will also be called problem and solution instances respectively.

In this paper we shall restrict our attention to input circuits which contain only output nodes labeled by “=0” and unlabeled output nodes and to output circuits having all output nodes labeled by the mark “=0”. Such an input circuit represents a parametric polynomial equation system defining an algebraic variety and a morphism defined on this variety. Therefore any input circuit represents a parametric polynomial equation system defining an algebraic variety, and a morphism having this variety as domain. The corresponding output circuit will always represent an algebraic variety which describes the image of the given morphism (this image will be Zariski closed in all cases we shall consider).

All procedures we are going to consider are geometric elimination procedures in this sense. We modelize such a procedure by a family of arithmetic networks (arithmetic– boolean circuits, see [8], [9]). Let us observe that in principle such a procedure may contain branchings.

We call an elimination procedure parametric if it contains no branchings for any input equation system which represents a (geometrically or scheme–theoretically) flat family of input instances.

We call an elimination procedure geometrically robust if it produces for any input instance of a given flat family an output circuit which depends only on the input equation system and the input morphism but not on their circuit representation. This means informally that a parametric elimination procedure is geometrically robust if it produces for (geometrically or scheme-theoretically) flat families of problem instances “continuous” or “stable” solutions.

Of course this notion of geometric robustness depends on the (geometric or schemetheoretical) context, i.e. it is not the same for schemes or varieties. Below we are going to explain our idea of geometric robustness in the typical situation of flat families of algebraic varieties given by reduced complete intersections.

Finally let us refer to the books [5], [16] and [18] as a general background for notions of algebraic complexity theory and algebraic geometry we are going to use in this paper.

1.1 Flat families of elimination problems

Let k be an infinite and perfect field with algebraic closure k̄ and let T_{1}, …, T_{m}, U_{1}, …, U_{r}, X_{1}, …, X_{n}, Y be indeterminates over k. Let G_{1}, …, G_{n}, F be polynomials belonging to the k-algebra k[T_{1}, …, T_{m}, U_{1}, …, U_{r}, X_{1}, …, X_{n}]. Suppose that the polynomials G_{1}, …, G_{n} form a regular sequence in k[T_{1}, …, T_{m}, U_{1}, …, U_{r}, X_{1}, …, X_{n}] defining thus an equidimensional subvariety V := {G_{1} = 0, …, G_{n} = 0} of the (m + r + n)-dimensional affine space IA^{m+r+n} over the field k̄. The algebraic variety V has dimension m + r. Let δ be the (geometric) degree of V. Suppose furthermore that the morphism of affine varieties π : V ⟶ IA^{m+r}, induced by the canonical projection of IA^{m+r+n} onto IA^{m+r}, is finite and generically unramified (this implies that π is flat). Let π̃ : V ⟶ IA^{m+r+1} be the morphism defined by π̃(z) := (π(z), F (z)) for any point z of the variety V. The image of π̃ is a hypersurface of IA^{m+r+1} whose minimal equation is a polynomial of k[T_{1}, …, T_{m}, U_{1}, …, U_{r}, Y] which we denote by P. Observe that P is monic in Y and that deg P ≤ δ holds. Furthermore deg_{Y} P is the cardinality of the image of the restriction of F to the set {w} × π^{−1}(w), where w is a typical point of IA^{m+r}. The polynomial P (T_{1}, …, T_{m}, U_{1}, …, U_{r}, F) vanishes on the variety V.

Let us consider an arbitrary point t = (t_{1}, …, t_{m}) of IA^{m}. For arbitrary polynomials B ∈ k[T_{1}, …, T_{m}, U_{1}, …, U_{r}, X_{1}, …, X_{n}] and C ∈ k[T_{1}, …, T_{m}, U_{1}, …, U_{r}, Y] we denote by B^{(t)} and C^{(t)} the polynomials B(t_{1}, …, t_{m}, U_{1}, …, U_{r}, X_{1}, …, X_{n}) and C(t_{1}, …, t_{m}, U_{1}, …, U_{r}, Y) which belong to k(t_{1}, …, t_{m})[U_{1}, …, U_{r}, X_{1}, …, X_{n}] and k(t_{1}, …, t_{m})[U_{1}, …, U_{r}, Y] respectively. Similarly we denote for an arbitrary polynomial A ∈ k[T_{1}, …, T_{m}] by A^{(t)} the value A(t_{1}, …, t_{m}) which belongs to the field k(t_{1}, …, t_{m}). The polynomials G_{1}^{(t)}, …, G_{n}^{(t)} form a regular sequence in k(t_{1}, …, t_{m})[U_{1}, …, U_{r}, X_{1}, …, X_{n}] and define an equidimensional subvariety V^{(t)} := {G_{1}^{(t)} = 0, …, G_{n}^{(t)} = 0} of IA^{r+n} whose degree is bounded by δ. Let π^{(t)} : V^{(t)} ⟶ IA^{r} and π̃^{(t)} : V^{(t)} ⟶ IA^{r+1} be the morphisms induced by π and π̃ on the variety V^{(t)}. Then the morphism π^{(t)} is finite and flat but not necessarily generically unramified. Furthermore the image of π̃^{(t)} is a hypersurface of IA^{r+1} on which the polynomial P^{(t)} vanishes (however P^{(t)} is not necessarily the minimal equation of this hypersurface). We call the equation system G_{1} = 0, …, G_{n} = 0 and the polynomial F a flat family of r-dimensional elimination problems depending on the parameters T_{1}, …, T_{m}. An element t ∈ IA^{m} is considered as a parameter point which determines a particular problem instance. The equation system G_{1} = 0, …, G_{n} = 0 together with the polynomial F is called the general instance of the given elimination problem and the polynomial P is called its general solution.

The problem instance determined by the parameter point t ∈ IA^{m} is given by the equations G_{1}^{(t)} = 0, …, G_{n}^{(t)} = 0 and the polynomial F^{(t)}. The polynomial P^{(t)} is called the solution of this particular problem instance. We call two parameter points t, t′ ∈ IA^{m} equivalent (in symbols t ∼ t′) if G_{1}^{(t)} = G_{1}^{(t′)}, …, G_{n}^{(t)} = G_{n}^{(t′)} and F^{(t)} = F^{(t′)} holds. Observe that t ∼ t′ implies also P^{(t)} = P^{(t′)}. We call polynomials A ∈ k[T_{1}, …, T_{m}], B ∈ k[T_{1}, …, T_{m}, U_{1}, …, U_{r}, X_{1}, …, X_{n}] and C ∈ k[T_{1}, …, T_{m}, U_{1}, …, U_{r}, Y] invariant (with respect to ∼) if for any two parameter points t, t′ of IA^{m} with t ∼ t′ the identities A^{(t)} = A^{(t′)}, B^{(t)} = B^{(t′)} and C^{(t)} = C^{(t′)} hold.

A straight-line program in k[T_{1}, …, T_{m}, U_{1}, …, U_{r}, Y] with parameters in k[T_{1}, …, T_{m}] is an arithmetic circuit in k[T_{1}, …, T_{m}, U_{1}, …, U_{r}, Y], say γ, modelized in the following way: γ is given by a directed acyclic graph whose internal nodes are labeled as usually by arithmetic operations. The input nodes of γ are labeled by the variables U_{1}, …, U_{r} and the nodes of γ of indegree 0 which are not input nodes (i.e. the parameter nodes of γ) are labeled by arbitrary elements of k[T_{1}, …, T_{m}] called parameters of γ. We call such a straight-line program γ invariant (with respect to the equivalence relation ∼) if all its parameters are invariant polynomials of k[T_{1}, …, T_{m}]. Let us observe that in an absolutely analogous way one may extend the notion of a straight-line program with parameters in k[T_{1}, …, T_{m}] and the notion of an invariant straight-line program to arithmetic circuits defined in k[T_{1}, …, T_{m}, U_{1}, …, U_{r}, X_{1}, …, X_{n}] or in k[T_{1}, …, T_{m}, U_{1}, …, U_{r}] (however we shall make almost exclusive use of the corresponding notion for circuits in k[T_{1}, …, T_{m}, U_{1}, …, U_{r}, Y]).

We are now ready to characterize in the given situation what we mean by a geometrically robust parametric elimination procedure. Suppose that the polynomials G_{1}, …, G_{n} and F are given by a straight–line program β in k[T_{1}, …, T_{m}, U_{1}, …, U_{r}, X_{1}, …, X_{n}]. A geometrically robust parametric elimination procedure produces from the circuit β as input an invariant straight–line program Γ in k[T_{1}, …, T_{m}, U_{1}, …, U_{r}, Y] as output such that Γ represents the polynomial P. Observe that in our definition of geometric robustness we did not require that β is an invariant straight–line program because this would be too restrictive for the modeling of real situations in computational elimination theory. However in all known practical situations β always satisfies the following (weak) invariance condition: any specialization of the input variables X_{1}, …, X_{n} in β into arbitrary values of k transforms the circuit β in a invariant straight–line program in k[T_{1}, …, T_{m}, U_{1}, …, U_{r}].

The invariance property required for the output circuit Γ means the following: let t = (t_{1}, …, t_{m}) be a parameter point of IA^{m} and let Γ^{(t)} be the straight–line program in k(t_{1}, …, t_{m})[U_{1}, …, U_{r}, Y] obtained from the circuit Γ evaluating in t the elements of k[T_{1}, …, T_{m}] which occur as parameters of Γ. Then the straight–line program Γ^{(t)} depends only on the particular problem instance determined by the parameter point t but not on t itself. Said otherwise, a geometrically robust elimination procedure produces the solution of a particular problem instance in a way which is independent of the possibly different representations of the given problem instance.

By definition a geometrically robust parametric elimination procedure produces always the general solution of the elimination problem under consideration. In other words this means that geometrically robust parametric elimination procedures do not contain branchings. Now we are going to show a complexity result which can be paraphrased as follows: none of the known (exponential time) parametric elimination procedures can be transformed into a polynomial time algorithm. For this purpose it is important to remark that the known parametric elimination procedures (which are without exception based on linear algebra as well as on comprehensive Gröbner basis techniques) are all geometrically robust for flat families of elimination problems. The invariance property of these procedures is easily verified in the situation of the flat family of r-dimensional elimination problems introduced before. One has only to observe that all known elimination procedures accept the input polynomials G_{1}, …, G_{n}, F in their dense or sparse coefficient representation or as evaluation black box with respect to the variables U_{1}, …, U_{r}, X_{1}, …, X_{n}.

1.2 A particular flat family of 1-dimensional elimination problems

Let S, T, U, X_{1}, …, X_{2n}, Y be indeterminates over Q. We consider the following flat family of one-dimensional elimination problems depending on the parameters S and T. Let

G_{1} := X_{1}^{2} − X_{1}, …, G_{n} := X_{n}^{2} − X_{n},

G_{n+1} := X_{n+1} − ∑_{1≤k≤n} 2^{k−1}X_{k}, G_{n+2} := X_{n+2} − X_{n+1}^{2}, G_{2n} := X_{2n} − X_{2n−1}^{2}

and

F := (1 + S ∏_{1≤i≤n}(T^{2^{i−1}} + X_{n+i})) ∏_{1≤j≤n}((U^{2^{j−1}} − 1)X_{j} + 1).

We interpret G_{1}, …, G_{2n} and F as elements of the polynomial ring Q [S, T, U, X_{1}, …, X_{2n}]. Thus we have m := 2 and r := 1 in this situation. It is clear from this representation that the polynomials G_{1}, …, G_{2n} and F can be evaluated by a straight–line program β in Q [S, T, U, X_{1}, …, X_{2n}] of nonscalar length O(n) (which satisfies the invariance condition for input circuits mentioned before). The degree in X_{1}, …, X_{2n} of the polynomials G_{1}, …, G_{2n} and F is bounded by 2n. The variety V := {G_{1} = 0, …, G_{n} = 0} is the union of 2^{n} affine linear subspaces of IA^{3+2n} of the form IA^{3} × {ξ}, where ξ is a solution of the equation system G_{1} = 0, …, G_{2n} = 0 in ZZ^{2n}. The morphism π : V → IA^{3} is obtained by gluing together the canonical projections onto IA^{3} of these affine linear spaces. Obviously the morphismπ is finite an generically unramified. In particular π has constant fibers. Let (l_{1}, …, l_{n}) be a point of {0, 1}^{n} and let l := ∑_{1≤j≤n} l_{j}2^{j−2} be the integer 0 ≤ l < 2^{n} with bit representation l_{n}l_{n−1} … l_{1}. Put l_{n+1} := l, l_{n+2} := l^{2}, …, l_{2n} := l^{2^{n−1}}. One verifies immediately that with the convention 0^{0} := 1 the identity

F (S, T, U, l_{1}, …, l_{2n}) = U^{l}(1 + S ∑_{{0≤p,q<2^{n} \atop p+q=2^{n}−1}} T^{p}l^{q})

holds. Therefore for any point (s, t, u, l_{1}, …, l_{2n}) ∈ V with l := ∑_{1≤j≤n} l_{j}2^{j−1} we have

F (s, t, u, l_{1}, …, l_{2n}) = u^{l}(1 + s ∑_{{0≤p,q<2^{n} \atop p+q=2^{n}−1}} t^{p}l^{q}).

From this we deduce easily that the elimination polynomial P ∈ Q [S, T, U, Y] we are looking for is

P := ∏_{0≤l<2^{n}} (Y − U^{l}(1 + S ∑_{{0≤p,q<2^{n} \atop p+q=2^{n}−1}} T^{p}l^{q})) .

This polynomial has the form

P = Y^{2^{n}} − ( ∑_{0≤l<2^{n}} U^{l}(1 + S ∑_{{0≤p,q<2^{n} \atop p+q=2^{n}−1}} T^{p}l^{q})) Y^{2^{n}−1} + lower degree terms in Y.

Suppose now that there is given a geometrically robust parametric elimination procedure. This procedure produces from the input circuit β an invariant straight–line program Γ in Q [S, T, U, Y], which evaluates the polynomial P. Recall that the invariance of Γ means that the parameters of Γ are invariant polynomials of Q [S, T], say A_{1}, …, A_{N}.

Let L(Γ) be the total and L(Γ) the non-scalar length of the straight–line program Γ. We have L(Γ) ≤ L(Γ) and N ≤ (L(Γ) + 3)^{2}. Let Z_{1}, …, Z_{N} be new indeterminates. From the graph structure of the circuit Γ we deduce that there exist for 0 ≤ l < 2^{n} polynomials Q_{l} ∈ ZZ[Z_{1}, …, Z_{N}] such that Q_{l}(A_{1}, …, A_{N}) is the coefficient of the monomial U^{l}Y^{2^{n}−1} of P. This means that we have for 0 ≤ l < 2^{n} the identity

Q_{l}(A_{1}, …, A_{N}) = 1 + S ∑_{{0≤p,q<2^{n} \atop p+q=2^{n}−1}} T^{p}l^{q}.  (1)

Observe now that for any two values t, t′ ∈ IA^{1} the points (0, t) and (0, t′) of IA^{2} are equivalent (in symbols: (0, t) ∼ (0, t′)). From the invariance of A_{1}, …, A_{N} we deduce therefore that A_{j}(0, t) = A_{j}(0, t′) holds for 1 ≤ j ≤ N. This means that α_{1} := A_{1}(0, T), …, α_{N} := A_{N}(0, T) are constant values of Q . From identity (1) we deduce that Q_{l}(α_{1}, …, α_{N}) = 1 holds for any 0 ≤ l < 2^{n}.

Let us consider the morphisms of affine spaces μ : IA^{2} ⟶ IA^{N} and ψ : IA^{N} ⟶ IA^{2^{n}} given by μ := (A_{1}, …, A_{N}) and ψ := (Q_{l})_{0≤l<2^{n}}.

Observe that

ψ ∘ μ = (Q_{l}(A_{1}, …, A_{N}))_{0≤l<2^{n}} = (1 + S ∑_{{0≤p,q<2^{n} \atop p+q=2^{n}−1}} T^{p}l^{q})_{0≤l<2^{n}}

holds. Furthermore let us consider the points α := (α_{1}, …, α_{N}) ∈ IA^{N} and ω := (1, …, 1) ∈ IA^{2^{n}}. From our previous considerations we deduce the identities

(ψ ∘ μ)(0, T) = (Q_{l}(A_{1}(0, T), …, A_{N}(0, T)))_{0≤l<2^{n}} =
= (Q_{l}(α_{1}, …, α_{N}))_{0≤l<2^{n}} = (Q_{l}(α))_{0≤l<2^{n}} = (1, …, 1) = ω.

In particular we have ψ(α) = ω. We analyze now the local behaviour of the morphism ψ in the point α ∈ IA^{N}. Let E_{α} and E_{ω} be the tangent spaces of the points α and ω belonging to IA^{N} and IA^{2^{n}} respectively. Let us denote the differential of the map ψ in the point α by (Dψ)_{α} : E_{α} ⟶ E_{ω}. Taking the canonical projections of IA^{N} and IA^{2^{n}} as local coordinates in the points α and ω respectively, we identify E_{α} with IA^{N} and E_{ω} with IA^{2^{n}}. For any value t ∈ Q we consider the parametric curves γ_{t} : IA^{1} ⟶ IA^{N} and δ_{t} : IA^{1} ⟶ IA^{2^{n}} defined by

γ_{t} := (A_{1}(S, t), …, A_{N}(S, t)) and δ_{t} := (1 + S ∑_{{0≤p,q<2^{n} \atop p+q=2^{n}−1}} t^{p}l^{q})_{0≤l<2^{n}}

respectively. Observe that ψ ∘ γ_{t} = δ_{t} and that γ_{t}(0) = α, δ_{t}(0) = ω holds (independently of the value t).

We consider γ_{t} and δ_{t} as one-parameter subgroups of IA^{N} and A^{2^{n}} respectively.

Now fix t ∈ Q and consider

γ′_{t}(0) = (\frac{∂A_{1}}{∂S} (0, t), …, \frac{∂A_{N}}{∂S} (0, t)) and δ′_{t}(0) = ( ∑_{{0≤p,q<2^{n} \atop p+q=2^{n}−1}} t^{p}l^{q})_{0≤l<2^{n}}.

We have γ′_{t}(0) ∈ E_{α} and δ′(0) ∈ E_{ω}. Moreover one sees easily that

(Dψ)_{α}(γ′_{t}(0)) = δ′_{t}(0) = ( ∑_{{0≤p,q<2^{n} \atop p+q=2^{n}−1}} t^{p}l^{q})_{0≤l<2^{n}}

holds. Choosing now 2^{n} different values t_{0}, …, t_{2^{n}−1} of Q we obtain 2^{n} tangent vectors v_{l} := γ′_{t_{l}}(0) of E_{α} with 0 ≤ l < 2^{n}. Let M be the 2^{n} × 2^{n} matrix whose row vectors are (Dψ)_{α}(v_{0}), …, (Dψ)_{α}(v_{2^{n}−1}). Observe that M has the form

M = (t_{h}^{2^{n}−p−1})_{0≤h,p<2^{n}} · (l^{q})_{0≤l,q<2^{n}}.

Thus M is the product of two non-singular Vandermonde matrices and therefore itself non-singular. This means that in E_{ω} the tangent vectors (Dψ)_{α}(v_{0}), …, (Dψ)_{α}(v_{2^{n}−1}) are linearly independent. Hence in E_{α} the tangent vectors v_{0}, …, v_{2^{n}−1} are linearly independent too.

Therefore we have 2^{n} ≤ dim E_{α} = N which implies 2^{n} ≤ N ≤ (L(Γ) + 3)^{2}. From this we deduce the estimation 2^{\frac{n}{2}} − 3 ≤ L(Γ) ≤ L(Γ).

We have therefore shown that any geometrically robust parametric elimination procedure applied to our flat family of one-dimensional elimination problems produces a solution circuit of size at least 2^{\frac{n}{2}} −3 i.e. a circuit of exponential size in the length O(n) of the input.

The discussion of the previous example shows that the objective of a polynomial time procedure for geometric (or algebraic) elimination can not be reached following a evolutionary way, i.e. constructing improvements of known elimination methods.

It was fundamental in our argumentation above that our notion of geometrically robust parametric elimination procedure excludes branchings in the output program. This suggests that any polynomial time elimination algorithm (if there exists one) must have a huge topological complexity. Thus hypothetical efficiency in geometric elimination seems to imply complicated casuistics.

This idea is worth to be discussed further. One may also ask whether admitting divisions in the output circuit helps to lower its minimal size. To some limited extent divisions in the output circuit are compatible with our proof method. However one has to take care of the way how these divisions may affect the dependence of the coefficients of the output polynomial on the parameters of the circuit representing it.

The formulation of a condition which guarantees the generalization of our method to output circuits with divisions seems to be cumbersome. In our example one has to make sure that even in presence of divisions for any value t ∈ Q the one-parameter subgroup γ_{t} still converges to one and the same point of IA^{N}.

Finally let us mention that our proof method above contributes absolutely nothing to the elucidation of the fundamental thesis of algebraic complexity theory, which says that geometric elimination is non-polynomial in the (unrestricted) non-uniform complexity model. Similarly no advance is obtained by our method with respect to the question whether PC ≠ NPC holds in the BSS complexity model, see [3, Chapter 7].

In fact our contribution consists only in the discovery of a very limiting uniformity property (geometric robustness) present in all known elimination procedures. This uniformity property inhibits the transformation of these elimination procedures into polynomial time algorithms. We resume the conclusions from the complexity discussion of our example in the following form:

Theorem 1 For any n ∈ IN there exists a one-dimensional elimination problem depending on one parameter and 2n + 1 variables, having input length O(n) such that the following holds: any geometrically robust parametric elimination procedure which solves this problem produces an output circuit of size at least 2^{\frac{n}{2}} − 3 (i.e. of exponential size in the input length).

2 On the complexity of geometric elimination procedures in the unrestricted non-uniform model

Let us now analyze from a general non-uniform point of view how the seminumerical elimination procedure designed in [11] and [10] works on a given flat family of zerodimensional elimination problems. Let T_{1}, …, T_{m}, X_{1}, …, X_{n}, Y be indeterminates over the ground ground field k and let G_{1}, …, G_{n}, F be polynomials belonging to the k-algebra k[T_{1}, …, T_{m}, X_{1}, …, X_{n}]. Let d := max{deg G_{1}, …, deg G_{n}} and suppose that G_{1}, …, G_{n} and F are given by straight–line programs in k[T_{1}, …, T_{m}X_{1}, …, X_{n}] of length L and K respectively. Suppose that the polynomials G_{1}, …, G_{n} form a regular sequence in k[T_{1}, …, T_{m}, X_{1}, …, X_{n}] defining thus an equidimensional subvariety V = {G_{1} = 0, …, G_{n} = 0} of IA^{m+n} of dimension m.

Assume that the morphism π : V ⟶ IA^{m}, induced by the canonical projection of IA^{m+n} onto IA^{m} is finite and generically unramified. Let δ be the degree of the variety V and let D ≤ δ be the degree of the morphism π. Furthermore let π̃ : V ⟶ IA^{m+1} be the morphism of affine varieties defined by π̃(z) := (π(z), F (z)) for any point z of V. Let P ∈ k[T_{1}, …, T_{m}, Y] be the minimal polynomial of the image of π̃. The polynomial P is monic in Y and one sees immediately that deg P ≤ δ deg F and deg_{Y} P ≤ D holds. Let us write δ_{∗} := deg_{T_{1},...,T_{m}} P.

Let us consider as Algorithm 1 and Algorithm 2 two non-uniform variants of the basic elimination method designed in [11] and [10].

• Algorithm 1 is represented by an arithmetic network of size Kδ^{O(1)}+L(ndΔ)^{O(1)} where Δ is the degree of the equation system G_{1} = 0, …, G_{n} = 0 (observe that always δ ≤ Δ ≤ deg G_{1} ⋯ deg G_{n} holds). The output is a straight–line program Γ_{1} in k[T_{1}, …, T_{m}, Y] of length (K + L)(nδ)^{O(1)} which represents the polynomial P.

• Algorithm 2 starts from the geometric description of a unramified parameter (and lifting) point t = (t_{1}, …, t_{m}) of k^{m} which has the additional property that the image of F restricted to the set {t} × π^{−1}(t) has cardinality D_{∗} = deg_{Y} P. The algorithm produces then a straight–line program Γ_{2} in k[T_{1}, …, T_{m}, Y] of length O(KD^{O(1)} log δ_{∗}) + δ_{∗}^{O(1)} = K(δ deg F)^{O(1)} which represents the polynomial P.

We observe that Kδ^{O(1)} is a characteristic quantity which appears in the length of both straight–line programs Γ_{1} and Γ_{2}. We are going now to analyze the question whether a complexity of type Kδ^{O(1)} is intrinsic for the elimination problem under consideration.

In the next subsection we are going to exhibit an example of a particular zerodimensional elimination problem for which the quantity Kδ appears as a lower bound for the nonscalar size of the output polynomial in the unrestricted non-uniform complexity model.

2.1 A particular flat family of zero-dimensional elimination problems

Let S, T_{1}, …, T_{δ}, X, Y be indeterminates over Q and let G := ∏_{1≤l≤δ}(X − T_{l}) and F := SX^{2^{K}}. Let V := {G = 0} be the hypersurface of IA^{δ+2} defined by the polynomial G and let π : V ⟶ IA^{δ+1} be the finite, generically unramified morphism induced by the canonical projection of IA^{δ+2} onto IA^{δ+1}. Observe that δ is the degree of the hypersurface V of IA^{δ+2} and of the morphism π (in fact V is the union of δ distinct hyperplanes of IA^{δ+2}).

The polynomials G and F have a nonscalar complexity δ and K + 1 respectively. They represent a flat family of zero-dimensional elimination problems with m := δ + 1, n := 1, deg V = δ and deg π = δ (see Subsection 1.1). The general solution of this elimination problem is represented by the polynomial

P := ∏_{1≤l≤δ}(Y − ST_{l}^{2^{K}}) = Y^{δ} − Y^{δ−1}S ∑_{1≤l≤δ} T_{l}^{2^{K}} + higher degree terms in S

which belongs to Q [S, T_{1}, …, T_{δ}, Y]. Let Γ be straight–line program of nonscalar length L(Γ) in k[S, T_{1}, …, T_{δ}, Y] which computes the polynomial P. We transform the circuit Γ into a straight–line program Γ^{∗} in Q [T_{1}, …, T_{δ}] of nonscalar length L(Γ^{∗}) ≤ 3L(Γ) which computes the polynomial R := ∑_{1≤l≤δ} T_{l}^{2^{K}}. This can be done as follows: first we derive the straight–line program Γ with respect to the variable S and then we specialize S and the variable Y into the values 0 and 1 respectively.

Analyzing the complexity of the polynomial R by means of Strassen’s degree method as in [2], [19] we find that L(Γ^{∗}) ≥ (K −1)δ holds. This implies L(Γ) ≥ \frac{1}{3}(K −1)δ = Ω(Kδ).

Unfortunately the meaning of the parameter δ is ambiguous: δ is the degree of the variety V and the degree of the morphism π as well as the nonscalar complexity of the polynomial G. Nevertheless our example shows that any optimal elimination procedure which produces the general solution of a given flat family of zero-dimensional elimination problems has an inherent complexity which depends linearly on the nonscalar length of the polynomial which defines the projection we are considering. The factor of proportionality of this linear dependence appears as an invariant of the equational part of our elimination problem. For the moment we are not able to interpret unambiguously this factor of proportionality. It is always bounded from above by a polynomial function of the straight–line program size, of the number of variables eliminated and of the degree of the input variety and appears in some cases as bounded from below by a quantity which may be interpreted alternatively as the degree of the input system or as its nonscalar length. This leads us to the following notion of elimination complexity of a given flat family of zero-dimensional elimination problems. This notion is the subject of the next subsection.

2.2 The elimination complexity of a zero-dimensional polynomial equation system

Let T_{1}, …, T_{m}, X_{1}, …, X_{n}, Y be indeterminates over k and let G_{1}, …, G_{n} ∈ k[T_{1}, …, T_{m}, X_{1}, …, X_{n}] be polynomials forming a regular sequence in k[T_{1}, …, T_{m}, X_{1}, …, X_{n}]. Let V = {G_{1} = 0, …, G_{n} = 0} be the equidimensional variety defined by the polynomials G_{1}, …, G_{n} and let π : V ⟶ IA^{m} be the morphism of affine varieties induced by the canonical projections of IA^{m+n} onto IA^{m}. Suppose that π is finite and generically unramified and observe that V has dimension m.

For any polynomial F ∈ k[T_{1}, …, T_{m}, X_{1}, …, X_{n}] we consider the flat family of zero-dimensional elimination problems given by the equations G_{1} = 0, …, G_{n} = 0 and the polynomial F. Let P_{F} ∈ k[T_{1}, …, T_{m}, Y] be the general solution of this problem. Let L(F) and L(P_{F}) be the nonscalar complexity of the polynomials F and P_{F} respectively. Observe that the set of values

N_{G_{1},...,G_{n}} := \{\frac{L(P_{F})}{L(F)}; F ∈ K[T_{1}, …, T_{m}, X_{1}, …, X_{n}]\}

is bounded by a quantity which depends polynomially on the degree of V and the number n of variables to be eliminated (compare this with the length of the straight– line program Γ_{1} in Algorithm 1 in this section).

We define now the supremum sup N_{G_{1},...,G_{n}} as the elimination complexity of the equation system G_{1} = 0, …, G_{n} = 0. In the example of the previous subsection the nonscalar straight–line program length of the equational part of the input system equals the quantity deg V and this quantity represents a lower bound for the elimination complexity of the given equation system.

References

[1] B. Bank, M. Giusti, J. Heintz, and G. Mbakop. Polar Varieties and Efficient Real Equation Solving: The Hypersurface Case. J. of Complexity, vol. 13 (1):pp. 5–27, 1997.

[2] W. Baur and V. Strassen. The complexity of partial derivatives. Theoret. Comp. Sci., vol. 22:pp. 317–330, 1983.

[3] L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. preprint, 1997.

[4] L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. of the AMS, vol. 21 (1):pp. 1–46, 1989.

[5] P. Bürgisser, M. Clausen, and M. Amin Shokrollahi. Algebraic Complexity Theory, vol. 315 of Grundlehren der mathematischen Wissenschaften. Springer, 1997.

[6] D. Cox, J. Little, and D. O’Shea. Ideals, Varieties, and Algorithms: an introduction to computational algebraic geometry and commutative algebra. Undergraduate Texts in Mathematics. Springer Verlag, Berlin, 1992.

[7] I. Emiris. On the Complexity of Sparse Elimination. J. Complexity, vol. 12:pp. 134– 166, 1996.

[8] J. von zur Gathen. Parallel arithmetic computations: a survey. In B. R. J. Gruska and J. Wiedermann, eds., Proceedings of the 12th Symposium on Mathematical Foundations of Computer Science, vol. 233 of LNCS, pp. 93–112. Springer, Bratislava, Czechoslovakia, August 1986.

[9] J. von zur Gathen. Parallel Linear Algebra. In J. H. Reif, ed., Synthesis of Parallel Algorithms. Morgan Kaufmann, 1993.

[10] M. Giusti, K. Hägele, J. Heintz, J. E. Morais, J. L. Montaña, and L. M. Pardo. Lower Bounds for Diophantine Approximation. In Proceedings of MEGA’96 , vol. 117,118, pp. 277–317. Journal of Pure and Applied Algebra, 1997.

[11] M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo. Straight– Line Programs In Geometric Elimination Theory. to appear in J. of Pure and App. Algebra, pp. 1–46, 1997.

[12] J. Heintz. The Project TERA: the Comeback of Oblomov in Computer Science. SAC Newsletter, vol. 1, nov 1996.

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

[14] E. Mayr and A. Meyer. The complexity of the word problem for commutative semigroups. Adv. in Math., vol. 46:pp. 305–329, 1982.

[15] B. Mishra. Algorithmic Algebra. Springer Verlag, New York, 1993. ISBN 0-387-94090-1.

[16] D. Mumford. The Red Book of Varieties and Schemes, vol. 1358 of LNM . Springer, Berlin, first edition, 1988.

[17] L. M. Pardo. How lower and upper complexity bounds meet in elimination theory. In G. Cohen, H. Giusti, and T. Mora, eds., Applied Algebra, Algebraic Algorithms and Error Corecting Codes. Proceedings of AAECC-11 , vol. 948 of LNCS. Springer, 1995.

[18] I. Shafarevich. Basic algebraic geometry. Graduate Texts in Mathematics. Springer-Verlag, 1984.

[19] V. Strassen. Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationspolynomen. Numer. Math., vol. 2:pp. 238–251, 1973.

[20] V. Weispfenning and T. Becker. Groebner bases: a computational approach to commutative algebra, vol. 141 of Graduate Texts in Mathematics: readings in mathematics. Springer, 1993.

J. Heintz  Guillermo Matera
Depto. de Matemáticas, Est. y Comp. Depto. de Matemáticas
Facultad de Ciencias  FCEyN, Universidad de Buenos Aires
Universidad de Cantabria  Ciudad Universitaria, Pab. I
E-39071 SANTANDER, Spain  (1428) BUENOS AIRES, Argentina

heintz@matsun1.matesco.unican.es  gmatera@dm.uba.ar

Depto. de Matemáticas  Instituto de Ciencias, Roca 850
FCEyN, Universidad de Buenos Aires Universidad Nacional de Gral. Sarmiento
Ciudad Universitaria, Pab. I  (1663) San Miguel - Pcia. de Buenos Aires
(1428) BUENOS AIRES, Argentina  Argentina
Luis M. Pardo  Rosita Wachenchauzer
Depto. de Matemáticas, Est. y Comp. Departamento de Computación
Facultad de Ciencias  FCEyN, Universidad de Buenos Aires
Universidad de Cantabria  Ciudad Universitaria
E-39071 SANTANDER, Spain  (1428) BUENOS AIRES, Argentina

pardo@matsun1.matesco.unican.es   rosita@dc.uba.ar