Integration of multivariate rational functions given by straight-line programs

Guillermo Matera^{∗}^{†}^{‡}

Departamento de Matemáticas, Fac. de Ciencias Exactas Univ. de Buenos Aires (1428) Buenos Aires, ARGENTINA.

                               gmatera@mate.dm.uba.ar

                        This paper is published in
      Applied Algebra, Algebraic Algorithms and Error Correcting Codes
         Proc.AAECC-11, Springer LNCS Vol.948, 1995, pp.347-364.

Abstract

We present a well-parallelizable algorithm which, taking a straight-line program for the evaluation of a vectorial field of rational functions of Q(X_{1}, …, X_{n}) as input, decides whether they allow a rational potential function and, in case of affirmative answer, computes it as output. We introduce a mixed model of representation of polynomials to allow the application of integration techniques and show how to perform some basic operations with it. The algorithm is presented as a family of arithmetic networks of polynomial size and polylogarithmic depth in the degree of the occurring polynomials.

1 Introduction

This paper is concerned with the complexity problem of performing integration on polynomials (or rational functions) represented by straight-line programs.

The choice of the representation of multivariate polynomials and rational functions is one of the most important tasks in computer algebra systems. The “classical” model is the dense representation: the data structure which represents a polynomial is supplied with one unit of memory space for each possible coefficient in it; in other words we represent a polynomial F ∈ k[X_{1}, …, X_{n}] of degree at most d by the vector of all its \binom{d+n}{n} possible coefficients. Since \binom{d+n}{n} ≤ d^{n}, we observe that to the polynomial F corresponds in dense representation a data structure of size O(d^{n}).

The amount of space requiered by this exponential behaviour may become intractable some problems from a computational point of view.

∗Partially supported by Research Project PB93-0472-C02-02

†Partially supported by GDR de Calcul Formel Medicis (CNRS) France

‡EC Project ESPRIT BRA Contract 6846 PoSSo

Hence, several different models have been suggested. A valid alternative is given by the straight-line programs. They constitute an algebraic “modelization” of the concept of algorithm without branchings and have proved to be a very useful tool to improve known bounds of some algorithmic algebraic problem. A straight-line program can be defined as a (finite) sequence of rational functions of Q(X_{1}, …, X_{n}) namely Q_{1}, …, Q_{α} (intermediate results), such that every Q_{i} of the sequence is either a variable X_{1}, …, X_{n} or an element of Q (parameter), or either the sum, the difference, the product or the division of two preceeding polynomials in the sequence (for precisions and elementary properties of straightline programs we refer to [7, 8, 13, 14]).

An example of the convenience of this representation is the symbolic n × n determinant: its dense representation has size n! but it can be computed with O(n^{3}) operations by techniques of gaussian elimination.

It is often convenient to use the representation of a straight-line program by a directed acyclic graph. The inputs are the sources of the graph, the node for every Q_{i} is labelled by its operation and it has 2 input edges numbered from the predecessors of Q_{i}. Two natural measures for a straight-line program β are its size or sequential time (total number of gates) and its depth or parallel complexity (length of the longest path in β).

We shall use the nonscalar measures which counts the steps where an essential operation is performed, that is, the product between two nonconstant polynomials and the division with nonconstant denominator. A justification of the choice of this measure would be the fact that, from a complexity point of view, nonscalar time “dominates” other known measures. Besides, nonscalar depth provides the best bounds for the degree of the represented polynomials.

Naturally a question arises: whether polynomials given by straight-line program can be manipulated in order to perform operations like greatest common divisor, differentation, etc. In this sense, several important transformations are known (see [11, 15]). A fundamental one by Baur-Strassen [1] allows to compute all first derivatives with growth in length only by a constant factor (without even the need of a degree bound). It has enormous consequences in complexity theory and computer science.

Thus, we ask for the “inverse” problem, that is, the integration: given a straight-line program to evaluate a rational function (or more generally, a gradient field of rational functions from Q(X_{1}, …, X_{n})), construct a straight-line program to evaluate its integral (their potential function).

Here we can hardly expect the Baur-Strassen’s kind of bounds. There is some evidence that integration is conected with some problems involving straight-line programs which are known to be NP-hard. Hence, an upper bound of order (nL)^{O(1)} for the process of integration would probably imply that P=NP.

On the other side, it is well known that the dense representation of an n-variate polynomial of degree d can be obtained from a straight-line program of nonscalar length L by means of d^{n}L nonscalar operations. Since we are interested in the advantages of the straight-line program structure, this is a natural upper bound to the results to be obtained.

In this work we solve this problem by means of a well-parallelizable algorithm with (ndL)^{O(1)} nonscalar size. More precisely, we shall prove the following:

Theorem 1 Let F_{1}, …, F_{n} , G_{1}, ..., G_{n} be polynomials in Q[X_{1}, …, X_{n}] of highest degree d, given by an arithmetic circuit without divisions of nonscalar size L and nonscalar depth ℓ. Suppose further that G_{i} ≠ 0 for i = 1, ..., n.

Let P_{1} := \frac{F_{1}}{G_{1}} , ..., P_{n} := \frac{F_{n}}{G_{n}}.

Then there exists a randomized algorithm with nonscalar sequential time complexity (Lnd)^{O(1)} and nonscalar parallel time complexity O(ℓ + log^{3} d) which:

1. decides whether the vector field (P_{1}, ..., P_{n}) allows a potential function Q

2. being (1) true, whether there exists a potential function Q belonging to Q(X_{1}, …, X_{n})

3. in case of affirmative answer in (2), constructs a straight-line program that evaluates Q on the domain of P_{1}, …, P_{n}.

The network can be constructed by a probabilistic algorithm of nonscalar size O(Lnd)^{O(1)} and nonscalar depth O(ℓ + log^{3} d).

1.1 On the complexity model

Our algorithms will be represented by randomly generated (alternatively, non uniform) families of arithmetic networks over Q (see [7]). These arithmetic networks are directed acyclic graphs whose internal nodes are labelled by arithmetic operations of Q, comparisons in Q, selections of elements of Q (associated to comparisons) and Boolean operations corresponding to propositional logic.

We consider the nonscalar measures as real valued functions depending on input parameters of the given straight-line program such that d, n, L and ℓ (highest degree, number of variables, nonscalar size and nonscalar depth) and we try to analyse their asymptotic behaviour.

2 The mixed representation model

All the algorithmic tools developed for rational integration seem strongly dependent on the knowledge of the coefficients of the polynomials to integrate. However, the integration of a multivariate rational function with respect to one variable only requires the dense structure with respect to that variable. This is a key observation for this work, because it suggests a model well adapted to our requirements.

2.1 A mixed model: dense representation and straight-line programs

As we mentioned in the introduction, the dense representation is too expensive to compute. On the other side, the straight-line program code does not seem to allow univariate integration. The mixed representation is an intermediate model which avoids these two difficulties.

It consists of the representation of n-variate polynomials with respect to one fixed variable, giving the coefficients (which are themselves n − 1-variate polynomials) by means of a straight-line program. It is less explicit than dense representation, which allows its computation from a straight-line program, but enough to allow univariate integration.

Let X_{i} be a fixed indeterminate (the variable of “integration”), and let F be a polynomial

in Q[X_{1}, …, X_{n}]. Let us write F = ∑_{k=0}^{d} F_{k}·X_{i}^{k}, where F_{0}, …, F_{d} ∈ Q[X_{1}, .., X_{i−1}, X_{i+1}, .., X_{n}].

Then the mixed representation of F with respect to X_{i} is defined as a straight-line program β in Q[X_{1}, .., X_{i−1}, X_{i+1}, .., X_{n}] which computes F_{0}, …, F_{d}.

The next lemma computes the nonscalar cost required to transform a straight-line program into a mixed representation.

Lemma 1 Let X_{1}, …, X_{n}, T be distinct indeterminates over Q and let F ∈ Q[X_{1}, ..., X_{n}, T] a polynomial of degree d given by a division-free straight-line program β in Q[X_{1}, ..., X_{n}, T] of nonscalar size L and nonscalar depth ℓ. Then there exists a division-free straight-line program in Q[X_{1}, ..., X_{n}] of nonscalar size O(dL) and nonscalar depth ℓ computing the mixed representation of F with respect to T.

Proof Since deg(F) = d, in particular deg_{T} (F) ≤ d, and therefore we can find the writing in the variable T by interpolating in d+1 points of Q. Doing all the interpolations in parallel, with (nonscalar) sequential cost (d + 1)L and parallel cost ℓ, we obtain the a straight-line program in Q[X_{1}, ..., X_{n}] which computes the coefficients of F with respect to T. □

2.2 Correct test sequences

A crucial point in algorithms treating with polynomial expressions is the “equality checking” between two polynomials which appear as intermediate results. Suppose for the moment that one wishes to know if a n-variate polynomial F with degree d produced by a suitable straight-line program is the zero polynomial. A straightforward procedure for this purpose consists in the succesive evaluation of the straight-line program in the integer points of a box of cardinality d^{n} (interpolation) and is therefore exponential in the degree of F.

This main difficulty can be partially avoided by means of a fine result due to J.Heintz & C.P. Schnorr [9] (see also [10]).

Let d, L, ℓ be non negative integers. We consider the set W (d, n, L, ℓ) of all polynomials in Q[X_{1}, …, X_{n}] of degree bounded by d which can be evaluated by an straight-line program in Q(X_{1}, …, X_{n}) of size and depth bounded by L and ℓ. Let m ∈ IN, we say that a sequence γ := (γ_{1}, …, γ_{m}) (where γ_{i} ∈ Q^{n} for 1 ≤ i ≤ m) is a correct test sequence for W (d, n, L, ℓ) if the polynomial 0 is the unique polynomial of the set W (d, n, L, ℓ) that annihilates γ_{1}, γ_{2}, … and γ_{m}.

With these notations we have:

Theorem 2 ([9, Theorem 4.4]) Let Γ be a subset of Q of cardinality (2^{ℓ+1} − 2)(2^{ℓ} + 1)^{2}, m := 6(L + n)(L − (n + 1)) and denote by σ(d, n, L, ℓ, Γ) the subset of Q^{nm} of all correct test sequences of W (d, n, L) contained in Γ^{nm}. Then the following inequality holds:

(#Γ)^{nm}(1 − (#Γ)^{− \frac{m}{6}} ) ≤ #σ(d, n, L, ℓ, Γ).

Suppose now that F ∈ Q[X_{1}, …, X_{n}] is an arbitrary polynomial of degree bounded by d and which can be computed by a straight-line program in Q[X_{1}, …, X_{n}] without divisions of size L and depth ℓ. From the previous proposition one deduces:

Corollary 1 [6, Corollaire 2.1]) There exists an arithmetical network over Q working in size O(Lm) = O(L(L+n)^{2}) and depth O(ℓ) which decides if F is the polynomial zero. Moreover, this network can be constructed by a probabilistic algorithm in sequential time O(L(L + n)^{2}) and parallel time O(ℓ); its failure probability is smaller than ε = \frac{1}{262144}.

Let us remark that the proposition guarantees the existence of at least one correct test sequence of size m which depends polynomially on the parameters (and not exponentially as in interpolation). The construction of correct test sequences depends only on the parameters; therefore if one knows a priori upper bounds for all polynomials in the algorithm, it is quite natural to consider the construction of the correct test sequences as a preprocessing computed once for ever.

The corollary introduces a probabilistic algorithm (choosing randomly a correct test sequence) which unfortunately has a failure probability (ε < \frac{1}{2}): if one is interested in the application of this procedure in order to check if a given polynomial is zero, the answer NO is always true but YES involves a failure probability smaller than ε.

2.3 The manipulation of polynomials given by mixed representations

This section is devoted to perform some manipulation with the mixed model, keeping polynomial-size polylogarithmic-depth complexity bounds. We shall pay attention to the computation of greatest common divisor (gcd) and square-free factorisation because the integration techniques to be applied are based on them.

Let us fix some notations. Throughout the remaining of the section, let d, e, n be fixed

natural numbers. We shall deal with polynomials F (X_{1}, ..., X_{n}, T) = ∑_{k=0}^{d} F_{k}(X_{1}, ..., X_{n})T^{k}

and G(X_{1}, ..., X_{n}, T) = ∑_{k=0}^{e} G_{k}(X_{1}, ..., X_{n})T^{k} of Q[X_{1}, ..., X_{n}][T] with degree d,e in T re-

spectively, given by their mixed representations. Their coefficients {F_{k}, G_{k}} will be given by a straight-line program β of nonscalar size L and nonscalar depth ℓ. We shall assume furthermore that we are given an n-tuple \underline{α} ∈ Q^{n} such that F_{d}(\underline{α}) ≠ 0 and G_{e}(\underline{α}) ≠ 0.

The idea of the next algorithms is the following: we start running β on input \underline{α} ∈ Q^{n} to evaluate the coefficients of the input polynomials, and then we operate with those coefficients in order to compute the required output. The philosophy is to carry our problems to a linear algebra setting where they can be solved by means of well-parallelizable networks of polynomial size.

2.3.1 Computation of greatest common divisor

We shall follow here the ideas of [3]: given polynomials f,g in Q[T], with deg(f) := d ≥ deg(g) := e, if f is not a constant multiple of g, then deg(gcd(f, g)) := j = min{k ∈ IN; ∃r, s in Q[T], deg(r) < e − k, deg(s) < d − k and deg(rf + sg) = k}.

This can be translated into a linear system, whose matrix, namely P_{j}(f, g), is known as the j-th principal submatrix of the Sylvester matrix of f and g. It can be obtained from this latter by deleting its last k columns of coefficients of f, its last k columns of coefficients of g and its last 2k rows.

Since deg(gcd(f, g)) = min{k; det(P_{k}) ≠ 0} ([7, theorem 2.3]), we can multiply both sides of the system by Adj(P_{j}(f, g)) and conclude that

det(P_{j}(f, g))(r_{e−j−1}, ⋯, r_{0}, s_{d−j−1}, ⋯, s_{0})^{t} = Adj(P_{j}(f, g))(0, ⋯, 0, 1)^{t}

(let us remark that the right hand side of the last equation is the last column of Adj(P_{j}(f, g))). This allows us to compute a det(P_{j}(f, g))-multiple of the coefficients of r(T) and s(T) in a suitable construction.

In our setting, since F_{d}(\underline{α})·G_{e}(\underline{α}) ≠ 0 it follows that P_{k}(F (\underline{α}, T), G(\underline{α}, T)) = P_{k}(F, G)(\underline{α}) (where P_{k}(F, G) is the k-th principal submatrix of F and G as polynomials in Q(X_{1}, …, X_{n})[T]).

We design the following algorithm:

- Input: A straight-line program β and an n-tuple \underline{α} ∈ Q^{n}.

- Run β on \underline{α} to obtain the coefficients (F_{d}(\underline{α}), …, F_{0}(\underline{α})) and (G_{e}(\underline{α}), …, G_{0}(\underline{α})).

- Compute det(P_{i}(F (\underline{α}, T), G(\underline{α}, T))), A^{(i)}(T) = ∑_{k=0}^{e−i−1} r_{k}^{(i)}T^{k} and B^{(i)}(T) = ∑_{k=0}^{d−i−1} s_{k}^{(i)}T^{k}

in parallel for every i, where the vector (r_{e−i−1}^{(i)}, ⋯, r_{0}^{(i)}, s_{d−i−1}^{(i)}, ⋯, s_{0}^{(i)})^{t}(\underline{α}) is the last

column of Adj(P_{i}(F (\underline{α}, T), G(\underline{α}, T))).

- Compute (in parallel) the coefficients of A^{(i)}(T) · F (\underline{α}, T) + B^{(i)}(T) · G(\underline{α}, T)

- Set j := min\{i|P_{i}(F (\underline{α}, T), G(\underline{α}, T)) ≠ 0\}.

- Compute

det(P_{j}(F (\underline{α}, T), G(\underline{α}, T)))·gcd(F (\underline{α}, T), G(\underline{α}, T)) = A^{(j)}(T)·F (\underline{α}, T)+B^{(j)}(T)·G(\underline{α}, T)

During its execution, the algorithm computes O(d^{2}) determinants in parallel – the principal subresultants and the last column of Adj(P_{i}(F, G))(\underline{α}) – of matrices whose maximal size is d × d and performs O(d) comparisons (only O(log d) sequentially) and O(d) products (in parallel). The determinants are computed by means of effective methods of linear algebra due to Berkowitz [2] with sequential time d^{3} and parallel time log^{2} d. In conclusion, we have:

Proposition 1 There exists a division-free arithmetic network which, on input \underline{α}, computes a scalar multiple of gcd(F (\underline{α}, T), G(\underline{α}, T)) by means of O(L + d^{O(1)}) sequential and O(ℓ + log^{2} d) parallel nonscalar steps.

2.3.2 Square-free Factorisation

Let f be a polynomial in Q[T], we can write f(T) = ∏_{k=1}^{d}(f_{k}(T))^{k} where, for every k, the

f_{k}’s belong to Q[T], are square-free and satisfy: gcd(f_{i}, f_{j}) = 1 for every 1 ≤ i < j ≤ d. This is known as the square-free factorisation of f.

In order to get low parallel complexity, we take the ideas of [7] and compute the factors f_{k} in the following way: for 0 ≤ k ≤ d, let us define g_{k}:= gcd(f, f′, …, f^{(k)}) (hence we have g_{k} = f_{k+1}f_{k+2}^{2} … f_{d}^{d−k}); therefore the factors f_{k} of the square-free factorisation satisfy the equality:

f_{k} = \frac{\frac{g_{k−1}}{g_{k}}}{gcd(\frac{g_{k−1}}{g_{k}} , g′_{k−1})}

Following the above scheme, we design an algorithm to compute square-free factorisation on polynomials in mixed representation:

- Input: A straight-line program β and an n-tuple \underline{α} ∈ Q^{n}

- Run β on \underline{α} to obtain (F_{d}(\underline{α}), …, F_{0}(\underline{α})).

- For every k, compute (in parallel) \frac{∂^{k}F}{∂T^{k}} (\underline{α}, T) = ∑_{i=k}^{d} i ⋯ (i − k + 1)F_{i}(\underline{α}, T)T^{i−k} and

all G_{k}(\underline{α}, T) := gcd(F (\underline{α}, T), …, \frac{∂^{k}F}{∂T^{k}} (\underline{α}, T)) by a tree of gcd’s: start computing (in

parallel) all possible gcd(\frac{∂^{2j−1}F}{∂T^{2j−1}} (\underline{α}, T), \frac{∂^{2j}F}{∂T^{2j}} (\underline{α}, T)) and, every next step, compute gcd of two (successive) previous results. (Let us observe that only O(log d) parallel steps of computation of greatest common divisors are needed).

- Compute (in parallel) all gcd(\frac{G_{k}(\underline{α}, T)}{G_{k−1}(\underline{α}, T)}, \frac{∂G_{k−1}}{∂T} (\underline{α}, T)).

- Compute (in parallel) all F_{k}(\underline{α}, T) = \frac{\frac{G_{k}(\underline{α}, T)}{G_{k−1}(\underline{α}, T)}}{gcd(\frac{G_{k}(\underline{α}, T)}{G_{k−1}(\underline{α}, T)}, \frac{∂G_{k−1}}{∂T} (\underline{α}, T))}.

Let us remark that the last step of the algorithm consists of a division of two polynomials whose result is known to be a polynomial a priori. This task can be rewritten as a linear system of suitable size, whose parameters depend on the coefficients of the polynomials involved. Hence, the size and depth of the whole procedure are increased in a way according to our requirements.

Since derivation in T is not counted in the nonscalar model, applying the result of proposition 1 we have:

Proposition 2 There exists a division-free arithmetic network of nonscalar size O(L + d^{O(1)}) and nonscalar depth O(ℓ + log^{3} d) which, on input \underline{α}, performs the square-free factorisation F (\underline{α}, T).

3 On the integration of rational functions

3.1 Algorithmic tools of integration

We start this section with a short account of the techniques we shall apply to integrate rational functions, which are taken from [5]. They are a strongly simplified fragment of the Liouville’s theory of formal integration.

A differential field is a field F, together with a derivation on F, that is, a map of F into itself, usually denoted by a → a′, such that (a + b)′ = a′ + b′ and (ab)′ = a′b + ab′. If a, b are elements of a differential field F, we say that b is a primitive of a, or b is an integral of a, if b′ = a. Sometimes we denote a primitive of a by ∫ a. Likewise, if a is nonzero, b is a

logarithm of a if b′ = \frac{a′}{a}. By a differential extension field of a differential field F we mean a differential field which is an extension field of F whose derivation extends the derivation on F. Let us remark that if F is a differential field of characteristic zero and K is an algebraic extension field of F, then the derivation on F can be extended to a derivation on K in a unique way. We shall assume all algebraic extension fields provided with this uniquely determined differential structure.

Let E be an algebraic extension of Q and X an indeterminate over Q. In the sequel we shall deal with Q(T) provided with its natural differential structure, given by the unique derivation defined by the rule T′ = 1. We say that a primitive of a rational function f is expressible in E (by means of adjunctions of logarithms) if there exists a primitive of f on a differential extension field of E(T), which is obtained by adjoining some logarithms of rational functions of E(T).

A first observation is that an algebraic extension is sufficient to express the integral of a rational function. In fact, the decomposition field of its denominator, namely E, is enough. Furthermore, we can write the primitive as a sum of a rational function g in E(T) plus a sum of logarithms of rational functions from E(T). This construction is effective and provides a fundamental tool to this work: the rational function g can be choosen in Q(T). We summarize all this in the following theorem.

Theorem 3 Let f be a rational function de Q(T), let f(T) = \frac{p(T)}{q(T)} where p, q ∈ Q[T] are

coprimes. Let E be the decomposition field of q(T). Then, there exists a primitive of f which can be written as ∫ f(T)dT = g(T) + ∫ h(T)dT where g, h ∈ Q(T) and the primitive of h is a sum of logarithms of elements of E(T) (up to constants).

Proof ([5, Chapter 1,Theorems 1 and 2])

Let q(T) = ∏_{j=1}^{d} (q_{j}(T))^{j} be the square-free factorisation of q.

The main tool in the proof is the partial fraction decomposition of f with respect to the square-free factorisation of q: this consists of the writing

f(T) = a_{0}(T) + ∑_{j=1}^{d} \frac{a_{j}(T)}{(q_{j}(T))^{j}}

where the a_{j}’s are polynomials of Q[T] verifying deg(a_{j}) < deg(q_{j}).

By integration in the expression above we have

∫ f(T)dT = ∫ a_{0}(T)dT + ∑_{j=1}^{d} ∫ \frac{a_{j}(T)}{(q_{j}(T))^{j}} dT

Since a_{0}(T) is a polynomial from Q[T], we know that it has a primitive in Q[T].

On the other hand, all \frac{a_{j}(T)}{(q_{j}(T))^{j}} are rational functions of type \frac{r(T)}{s^{j}(T)} where r, s are

polynomials of Q[T] coprime and s is square-free.

We write r(T) = b_{1}(T)·s(T)+b_{2}(T)·s′(T) where deg(b_{1}) < deg(s′) and deg(b_{2}) < deg(s). Then we have

\frac{r}{s^{j}} = \frac{b_{2} · s′}{s^{j}} + \frac{b_{1}}{s^{j−1}} = −\frac{1}{j − 1}(\frac{b_{2}}{s^{j−1}} )′ + \frac{b}{s^{j−1}}

where b = b_{1} + \frac{1}{j − 1}b′_{2}. Thus

∫ \frac{r}{s^{j}} = −\frac{1}{j − 1} · \frac{b_{2}}{s^{j−1}} + ∫ \frac{b}{s^{j−1}}

Iterating this procedure we obtain an expression of the from:

∫ \frac{r(T)}{s^{j}(T)}dX = g̃(T) + ∫ \frac{b̃(T)}{s(T)}dT

where g̃ ∈ Q(T) and b̃ ∈ Q[T]. Since s is square-free, its integral is a sum of logarithms (of rational functions of E(T)) and hence we have proven the theorem. □

3.2 Decomposition in partial fractions

The proof of theorem 3 contains all essential methodical points we need in our algorithmic setting. As it can be seen, we need the decomposition of rational functions given by mixed representations into partial fractions with respect to square-free factorisation.

We start with the following:

Lemma 2 Let p, q be polynomials in Q[T] such that deg(p) < deg(q) and let q = q_{1} ⋯ q_{s} be the square-free factorisation of q. Then, there exist unique polynomials r_{1}, …, r_{s} with deg(r_{i}) < deg(q_{i}) for i = 1, …, s verifying:

\frac{p}{q} = ∑_{i=1}^{s} \frac{r_{i}}{q_{i}}

Proof [12, Theorem 8, Chapter 5, Paragraph 5]. □

We can replace the condition above by the following:

p = ∑_{i=1}^{s} r_{i} \frac{q}{q_{i}}

This latter can be rewritten as a linear system with the coefficients of r_{1}, …, r_{n} as unknowns, whose matrix has size d×d. The uniqueness forces this matrix to be nonsingular, and applying the same ideas as in section 2.3.1 we compute the coefficients of r_{1}, …, r_{s} by means of d^{O(1)} arithmetic sequential operations in O(log^{2} d) parallel steps.

Now, let F, G ∈ Q[X_{1}, …, X_{n}, T] polynomials of degree d, e in T, with d < e, given by a mixed representation of nonscalar sequential time L and nonscalar parallel time ℓ. Let \underline{α} ∈ Q^{n} such that F_{d}(\underline{α}) ≠ 0 and G_{e}(\underline{α}) ≠ 0. Set p(T) := F (\underline{α}, T) and q(T) := G(\underline{α}, T). First, we can compute the square-free factorisation of q(T) and then, we can apply the scheme explained above in order to compute decomposition in partial fractions of \frac{p}{q} with respect to the square-free factorisation of q. The results obtained are summarized in the following:

Theorem 4 There exists an arithmetic network working in nonscalar sequential time O(L+ d^{O}(1)) and nonscalar parallel time O(ℓ+log^{3} d) which on input \underline{α} computes the decomposition

in partial fractions of \frac{F (\underline{α}, T)}{G(\underline{α}, T)}.

3.3 The “rational” decomposition

After performing decomposition in partial fractions we come into a situation of integration of a rational function of type \frac{r}{s^{j}}, where r, s ∈ Q[T], s is square-free and deg(r) < deg(s^{j}). We reduce this problem to the computation of a polynomial b ∈ Q[T] and a rational function

g ∈ Q(T), such that deg(b) < deg(s) and an equality of the type ∫ \frac{r}{s^{j}} = g + ∫ \frac{b}{s} holds.

This expression, which we call the rational decomposition of \frac{r}{s^{j}}, completes the process of rational integration. g and h are called the rational and the logarithmic part of ∫ \frac{r}{s^{j}}.

We shall perform this rational decomposition in two stages: first, we compute a kind of

“Taylor” representation of r as r = ∑_{i=1}^{n−1} r_{i}·s^{i} where deg(r_{i}) < deg(s) for every i = 1, …, n−1.

The existence and uniqueness of this representation is straightforward, and an efficient parallel computation can be performed if one takes into account the following observations:

- the remainder of the division of r by s^{i} is r_{i−1}s^{i−1} + ⋯ + r_{0}.

- the quotient of r_{i−1}s^{i−1} + ⋯ + r_{0} by s^{i−1} is r_{i−1}.

- these two operations can be done in parallel for every i = 1, …, j − 1.

Further, we obtain the rational decompositions under the additional assumption that deg(r) < deg(s) which is guaranteed by the previous stage. We first prove the existence and uniqueness of this representation:

Lemma 3 Let r, s polynomials of Q[T] such that s is square-free and deg(r) < deg(s). Then, there exists unique polynomials r_{0}, r_{1}, …, r_{j−1} such that deg(r_{i}) < deg(s) for every i = 0, …, j − 1 and

∫ \frac{r}{s^{j}} = ∑_{i=1}^{j−1} \frac{r_{i}}{s^{i}} + ∫ \frac{r_{0}}{s}

Proof Let us prove the uniqueness. Given two rational decompositions, we can write their difference in the form:

0 = ∑_{i=1}^{j−1} \frac{r_{i}}{s^{i}} + ∫ \frac{r_{0}}{s}

where deg(r_{i}) < deg(s) for every i = 0, …, j − 1.

Taking derivative and multiplying the last expression by s^{j} we have:

0 = ∑_{i=1}^{j−2} [r′_{i} · s^{j−i} − i · r_{i} · s′ · s^{j−i−1}] − [r′_{j−1} · s − (j − 1) · r_{j−1} · s′] + r_{0} · s^{j−1}

This identity implies that s divides r_{j−1} and since deg(r_{j−1}) < deg(s), r_{j−1} = 0. By inductive arguments, it follows that r_{j−2} = ⋯ = r_{1} = 0, and finally that r_{0} = 0.

The existence is contained in the proof of theorem 3. □

Now we consider the problem of parallelizing this procedure. The proof of the Theorem 3 shows that

∫ \frac{r}{s^{j}} = −\frac{1}{j − 1} · \frac{b}{s^{j−1}} + ∫ \frac{a + \frac{b′}{j−1}}{s^{j−1}}

where a, b satisfies the relation r = a · s + b · s′ and deg(a) < deg(s′) and deg(b) < deg(s). We obtain the rational decomposition repeating this process.

Let r(T) := r_{d−1} · T^{d−1} + ⋯ + r_{0} and let us denote by P_{0}(s, s′) the Sylvester matrix of s and s′. In section 2.3.1 is shown that the coefficients a_{d−2}, …, a_{0}, b_{d−1}, …, b_{0} of a, b satisfy the following equation:

( a_{d−2} ; ⋮ ; a_{0} ; b_{d−1} ; ⋮ ; b_{0} ) = P_{0}(s, s′)^{−1} · ( 0 ; ⋮ ; 0 ; r_{d−1} ; ⋮ ; r_{0} )

The next step consists of the computation of polynomials a^{(1)}, b^{(1)} of suitable degree such that

a^{(1)} · s + b^{(1)} · s′ = a + \frac{b′}{j − 1}

This can be done in the following way: let A be a fixed (2d − 1) × (2d − 1) matrix such that

A · ( a_{d−2} ; ⋮ ; a_{0} ; b_{d−1} ; ⋮ ; b_{0} ) = ( 0 ; ⋮ ; 0 ; a_{d−1} + \frac{d−1}{j−1} · b_{d−1} ; ⋮ ; a_{0} + \frac{1}{j−1} · b_{1} )

Then the coefficients a_{d−2}^{(1)}, …, a_{0}^{(1)}, b_{d−1}^{(1)}, …, b_{0}^{(1)} of a^{(1)}, b^{(1)} can be computed as:

( a_{d−2}^{(1)} ; ⋮ ; a_{0}^{(1)} ; b_{d−1}^{(1)} ; ⋮ ; b_{0}^{(1)} ) = P_{0}(s, s′)^{−1} · ( 0 ; ⋮ ; 0 ; b_{d−1} + \frac{d−1}{j−1} · b_{d−1} ; ⋮ ; a_{0} + \frac{1}{j−1} · b_{1} ) = P_{0}(s, s′)^{−1} · A · P_{0}(s, s′)^{−1} · ( 0 ; ⋮ ; 0 ; r_{d−1} ; ⋮ ; r_{0} )

The same ideas lead us to compute every a^{(i)}, b^{(i)} as a product of matrices. Since the iterated product of matrices works well in parallel, we compute the rational decomposition by means of d^{O(1)} products in O(ℓ + log^{3} d) parallel steps. These ideas, in a mixed representation setting, yield the following result:

Theorem 5 With notations as in theorem 4, on input \underline{α} the rational decomposition of

\frac{F (\underline{α}, T)}{G(\underline{α}, T)} can be performed by a division-free arithmetic network of nonscalar size Ld^{O(1)}

and nonscalar depth O(ℓ + log^{3} d).

3.4 The existence of a rational primitive

An important point in this work is to decide whether a rational function allows a rational primitive. In order to answer this question, we shall deal with the residues of the function to be integrated.

From Theorem 3, we know that all the logarithms which appear in a primitive of a given rational function f ∈ Q(T) can be expressed by means of the integral of a rational

function h(T) = \frac{p_{1}(T)}{q_{1}(T)} where gcd(p_{1}, q_{1}) = 1, deg(p_{1}) < deg(q_{1}) and q_{1} is square-free. Let

q_{1}(T) = ∏_{i=1}^{d}(T − c_{i}) the factorisation of q_{1} over C, since h(T) = ∑_{i=1}^{d} \frac{Res_{c_{i}}(f)}{(T − c_{i})}, we have:

∫ h(T)dT = ∑_{i=1}^{d} ∫ \frac{Res_{c_{i}}(f)}{(T − c_{i})}dT = ∑_{i=1}^{d}Res_{c_{i}}(f) log(T − c_{i})

Since c_{i} ≠ c_{j} if i ≠ j, one easily deduces that \frac{1}{(T − c_{1})}, …, \frac{1}{(T − c_{d})} are linearly inde-

pendent over Q(c_{1}, …, c_{d}). Hence, the same is true for log(T − c_{1}), …, log(T − c_{d}). Thus, ∫ h(T)dT = 0 iff Res_{c_{1}}(f) = ⋯ = Res_{c_{d}}(f) = 0. That is, we have proved:

Lemma 4 f(T) has a rational primitive in Q(T) iff Res_{c_{i}}(f) = 0 for i = 1, …, d

We can check this condition by means of the following result, due to Bronstein [4]: there exists a polynomial B(f) whose roots are exactly the residues of f at all its poles. Furthermore, it can be computed in a completely rational way, as follows: write f = \frac{p}{q} where p, q ∈ Q[T], gcd(p, q) = 1 and q is monic. Let q = q_{1} · q_{2}^{2} ⋯ q_{d}^{d} be

the square-free factorisation of q and let m be a natural number smaller than d such that deg(q_{m}) ≥ 1. Let U be a differential indeterminate over Q(T). Compute

h = \frac{(fq_{m}U^{−m})^{(m−1)}}{(m − 1)!} ∈ Q(T)⟨U⟩

and write h as

h = \frac{P (T, U, U′, …, U^{(m−1)})}{Q(T, U, U′, …, U^{(m−1)})}

where P, Q are (d + 1)-variate polynomials with coefficients in Q.

Then compute

P̃ = P (T, q′_{m}, \frac{q′′_{m}}{2} , …, \frac{q_{m}^{(m)}}{m} ) ∈ Q[T]

Q̃ = Q(T, q′_{m}, \frac{q′′_{m}}{2} , …, \frac{q_{m}^{(m)}}{m} ) ∈ Q[T]

Let B_{m}(P) = Res_{T} (P̃ − T Q̃, q_{m}) ∈ Q[T]. Hence the roots of B_{m}(P) are the residues of f at all its poles of order m in \overline{Q}. Thus, the residues of f at all its poles are exactly the

roots of B(f) := ∏_{m=1}^{d} B_{m}(f) over \overline{Q}.

Hence we replace the condition of existence of a rational primitive ∫ f(T)dT by nonexistence of nonzero roots of B(f). Altogether, we have:

Proposition 3 With notations as in theorem 4, on input \underline{α} it can be decided whether

\frac{F (\underline{α}, T)}{G(\underline{α}, T)} allows a rational primitive by a division-free arithmetic network of nonscalar size

O(L + d^{O(1)}) in O(ℓ + log^{3} d) nonscalar parallel steps.

4 The main results

Throughout this section, F_{1}, …, F_{n}, G_{1}, …, G_{n} will denote polynomials in Q[X_{1}, …, X_{n}], represented by a division-free straight-line program with nonscalar size L and nonscalar

depth ℓ. Assume that the G_{i} ≠ 0 for i = 1, …, n and set P_{1} := \frac{F_{1}}{G_{1}} , …, P_{n} := \frac{F_{n}}{G_{n}}.

We start studying the first question of this work: whether the vectorial field (P_{1}, …, P_{n}) is a gradient field.

Theorem 6 There exists a randomized division-free arithmetic network of nonscalar size O((Ln)^{3}) and nonscalar depth is O(ℓ) which decides whether (P_{1}, …, P_{n}) is a gradient field. This network can be produced by a probabilistic algorithm of sequential time O(L(L + n)^{2}) and parallel time O(ℓ).

Proof: The statement of the Theorem is equivalent to prove that

\frac{∂P_{i}}{∂X_{j}} = \frac{∂P_{j}}{∂X_{i}}

for every 1 ≤ i, j ≤ n.

We can rephrase this condition by (G_{i}G_{j})^{2} · \frac{∂P_{i}}{∂X_{j}} = (G_{i}G_{j})^{2} · \frac{∂P_{j}}{∂X_{i}}. This can be written

as a polynomial equality involving only F_{i}, F_{j}, G_{i}, G_{j} and their first order derivatives.

From [1, Theorem 1], the first derivatives of all F_{i}, G_{i}’s can be computed (in parallel) with nonscalar sequential time O(nL) and nonscalar parallel time O(ℓ). Thus the problem is reduced to checking equalities between polynomials given by straight-line programs. Hence corollary 1 asserts there exists an arithmetical network in the conditions of the theorem which performs this task. □

Next problem is to decide whether (P_{1}, …, P_{n}) – which is now supposed to be a gradient field – allows a rational potential function Q, i.e., whether there exist a potential function Q ∈ Q(X_{1}, …, X_{n}) for (P_{1}, …, P_{n}).

By means of an affine change of coordinates we can assume that the n-dimensional origin (0, …, 0) is in the domain of (P_{1}, …, P_{n}) and that G_{i}(X_{1}, …, X_{n}) is monic in X_{i} (the variable of integration) for i = 1, …, n. The coefficients of the matrix of this change of coordinates can be chosen from a correct test sequence of suitable size.

Since G_{i}(0, …, 0) ≠ 0 for every i = 1, …, n, there exists a positive real number r and a neighborhood D := \{\underline{α} ∈ Q^{n}/ ∥ \underline{α} ∥< r\} ⊆ Q^{n} of (0, …, 0) such that G_{i}(\underline{α}) ≠ 0 holds over D. This means that Q is defined over D.

As it is well known, Q can be computed over D by the formula:

Q(X_{1}, …, X_{n}) = ∑_{i=1}^{n} ∫_{0}^{X_{i}} P_{i}(X_{1}, …, X_{i−1}, T, 0, …, 0)dT  (1)

Remark 1 The property of having (P_{1}, …, P_{n}) a rational potential function Q(X_{1}, …, X_{n}) does not depend on the point we integrate around of, but on the formal integral of the P_{i}’s. In other words, if a rational function Q is a potential of (P_{1}, …, P_{n}) in a neighborhood of (0, …, 0), it follows that Q will be a potential over the whole domain of (P_{1}, …, P_{n}).

The following lemma simplifies the condition of rationality of the potential function:

Lemma 5 Let P_{1}, ⋯, P_{n} ∈ Q(X_{1}, …, X_{n}) such that (P_{1}, ⋯, P_{n}) is a gradient field. Then, there exists a rational potential function Q ∈ Q(X_{1}, …, X_{n}) for (P_{1}, ⋯, P_{n}) iff for every

i = 1, …, n there exists a rational primitive ∫ P_{i}(X_{1}, …, X_{i}, 0, …, 0)dX_{i}.

Proof Suppose first that there exists a rational potential Q. Since \frac{∂Q}{∂X_{i}} = P_{i} holds for

i = 1, …, n, then \frac{∂}{∂X_{i}} (Q(X_{1}, …, X_{i}, 0, …, 0)) = P_{i}(X_{1}, …, X_{i}, 0, …, 0). But this means

that Q(X_{1}, …, X_{i}, 0, …, 0) is the rational primitive required.

The converse is clearly true by equation (1) and remark 1. □

The next theorem solves the second question of this work: the estimation of upper bounds of the complexity of deciding whether our vectorial field allows a rational potential.

Theorem 7 Suppose (P_{1}, …, P_{n}) to be a gradient field. Then, there exists a randomized division-free arithmetic network of nonscalar size (Lnd)^{O(1)} and nonscalar depth O(ℓ + log^{3} d) which decides whether (P_{1}, …, P_{n}) allows a potential function Q ∈ Q(X_{1}, …, X_{n}). The network can be constructed by a probabilistic algorithm of nonscalar size (Lnd)^{O(1)} and nonscalar depth O(ℓ + log^{3} d).

Proof Let r be a positive real number such that (P_{1}, …, P_{n}) is defined over the open set D := \{\underline{α} ∈ Q^{n}/ ∥ \underline{α} ∥< r\}. Then Q can be computed over D as:

Q(X_{1}, …, X_{n}) = ∑_{i=1}^{n} ∫_{0}^{X_{i}} P_{i}(X_{1}, …, X_{i−1}, T, 0, …, 0)dT

From remark 1 and lemma 5, it is enough to check whether there exist rational primitives

∫ P_{i}(X_{1}, …, X_{i−1}, T, 0, …, 0)dT for every i = 1, …, n.

By lemma 4 we know that the rationality of an integral of a rational function depends on whether the residues at all its poles are zero. This latter condition can be analysed applying the method explained in section 3.4.

Let us fix an index i, 1 ≤ i ≤ n and an n-tuple \underline{α} := (α_{1}, …, α_{n}) ∈ D. We are going to study the nullity of the residues of P_{i}(α_{1}, …, α_{i−1}, T, 0, …, 0).

In order to simplify notations we set:

\underline{α}^{(i)} := (α_{1}, …, α_{i−1})

(\underline{X}, T) := (X_{1}, …, X_{i−1}, T)

F̃_{i}(\underline{X}, T) := F_{i}(X_{1}, ⋯, X_{i−1}, T, 0, …, 0)

G̃_{i}(\underline{X}, T) := G_{i}(X_{1}, ⋯, X_{i−1}, T, 0, …, 0)

P̃_{i}(\underline{X}, T) := P_{i}(X_{1}, ⋯, X_{i−1}, T, 0, …, 0)

Since F̃_{i}, G̃_{i} are represented by a straight-line program in Q[\underline{X}, T] of nonscalar size L and nonscalar depth ℓ, by lemma 1 we can compute their mixed representation with respect to T with nonscalar sequential time O(dL) and nonscalar parallel time ℓ.

Hence the conditions of proposition 2 hold, and the square-free factorisation of G̃_{i}(\underline{α}^{(i)}, T) can be computed for every \underline{α} ∈ D in nonscalar sequential time O(dL + d^{O(1)}) and nonscalar parallel time O(ℓ + log^{3} d).

Finally, the construction of the polynomial B(P̃_{i}(\underline{α}^{(i)}, T)) defined in section 7 (whose roots are the residues of P̃_{i}(\underline{α}^{(i)}, T) at all its poles) is performed by means of O(dL + d^{O(1)}) (nonscalar) arithmetic operations in O(ℓ + log^{3} d) nonscalar parallel steps.

We compute B(P̃_{i}(\underline{α}^{(i)}, T)) and check whether all their nonprincipal coefficients vanish in parallel for i = 1, …, n by means of a correct test sequence of polynomials produced by straight-line programs of nonscalar size O(dL + d^{O(1)}) and nonscalar depth O(ℓ + log^{3} d). Combining the results of proposition 3 and corollary 1 the theorem follows. □

It remains to answer the third question: the problem of computing a rational potential whenever it is possible. We solve it in the following theorem:

Theorem 8 If (P_{1}, …, P_{n}) allows a rational potential, there exists an arithmetic network computing and evaluating Q of nonscalar sequential complexity Lnd^{O(1)} and nonscalar parallel complexity O(ℓ + log^{3} d).

Proof With notations as in theorem 3.4, fix \underline{α} ∈ Q^{n}. We have to compute ∫_{0}^{α_{i}} P̃_{i}(\underline{α}^{(i)}, T)dT.

As it has shown, there exists a arithmetic network of nonscalar size O(dL + d^{O(1)}) and nonscalar depth (ℓ + log^{3} d) which computes the mixed representation of F̃_{i}, G̃_{i} and the square-free factorisation of G̃_{i}(\underline{α}^{(i)}, T).

Let G̃_{i}(\underline{α}^{(i)}, T) = ∏_{j=1}^{d}(g_{j}(\underline{α}^{(i)}, T))^{j} the square-free factorisation of G̃_{i}(\underline{α}^{(i)}, T).

By lemma 4, in (nonscalar) sequential time Ld^{O(1)} and parallel time O(ℓ+log^{3} d) we can obtain the decomposition in partial fraction of P̃_{i}(\underline{α}^{(i)}, T) with respect to the square-free fac-

torisation of G̃_{i}(\underline{α}^{(i)}, T), that is, the expression P̃_{i}(\underline{α}^{(i)}, T) = A_{0}(\underline{α}^{(i)}, T)+∑_{j=1}^{d} \frac{A_{j}(\underline{α}^{(i)}, T)}{(g_{j}(\underline{α}^{(i)}, T))^{j}}

where A_{j} ∈ Q(X_{1}, …, X_{i−1})[T] and deg_{T} (A_{j}(\underline{α}^{(i)}, T)) < deg_{T} (g_{j}(\underline{α}^{(i)}, T)).

Further, the rational decomposition of every \frac{A_{j}(\underline{α}^{(i)}, T)}{(g_{j}(\underline{α}^{(i)}, T))^{j}}, i.e.

∫ \frac{A_{j}(\underline{α}^{(i)}, T)}{(g_{j}(\underline{α}^{(i)}, T))^{j}} dT = \frac{B_{j}(\underline{α}^{(i)}, T)}{(g_{j}(\underline{α}^{(i)}, T))^{j−1}} + ∫ \frac{C_{j}(\underline{α}^{(i)}, T)}{g_{j}(\underline{α}^{(i)}, T)}dT

can be computed with (nonscalar) sequential complexity Ld^{O(1)} and parallel complexity O(ℓ + log^{3} d).

Since our integral is rational by lemma 5 and g_{j}(\underline{α}^{(i)}, T) is square-free, its logarithmic

part, ∫ \frac{C_{j}(\underline{α}^{(i)}, T)}{g_{j}(\underline{α}^{(i)}, T)}dT, is null. Therefore,

∫_{0}^{α_{i}} P̃_{i}(\underline{α}^{(i)}, T)dT = ∫_{0}^{α_{i}} A_{0}(\underline{α}^{(i)}, T)dT + ∑_{j=1}^{d} \frac{B_{j}(\underline{α}^{(i)}, T)}{(g_{j}(\underline{α}^{(i)}, T))^{j−1}} _{0}^{α_{i}}

First we observe that the computation of ∫_{0}^{α_{i}} A_{0}(\underline{α}^{(i)}, T)dT does not have cost in the

nonscalar model. Besides, the integrals ∫_{0}^{α_{i}} P̃_{i}(\underline{α}^{(i)}, T)dT can be computed in parallel

for every i = 1, …, n. Thus, this yields an arithmetic network with nonscalar sequential complexity Lnd^{O(1)} and nonscalar parallel complexity O(ℓ + log^{3} d) which computes Q(X_{1}, …, X_{n}). □

5 Conclusions

We have shown that integration on straight-line programs can be performed by means of well parallelizable algorithms if one allows polynomial-size degree growth of bounds. It can be seen that the mixed representation is a key model.

Let us observe that this is not an improvement of the known complexity bounds in the one-variate case, because there our methods consist on interpolation and classical techniques of dense integration. Nevertheless, the most interesting examples arise in this case.

Acknowledgments

The author is deeply indebted to Joos Heintz, for having strongly inspirated this work.

References

[1] Baur W., Strassen V.: The complexity of partial derivatives. Theoret. Comput. Sci. 22 (1982) 317–330.

[2] Berkowitz S.J.: On computing the determinant in small parallel time using a small number of processors. Information Processing Letter 18 (1984) 147–150.

[3] Borodin A., von zur Gathen J., Hopcroft J.: Fast parallel matrix and GCD computations. Information and Control 52 (1982) 241–256.

[4] Bronstein M.: Formulas for series computations. Applied Algebra in Engineering, Communication and Computing, AAECC 2, Springer-Verlag (1992) 195–206.

[5] Davenport J.H.: Intégration Formelle. IMAG Reserch Report No.375 (1983) 1–23.

[6] Fitchas N., Giusti M. and Smietanski F.: Sur la complexité du théorème des zéros. Preprint Ecole Polytechnique Palaiseau (1992).

[7] von zur Gathen J.: Parallel algorithms for algebraic problems. Proc. 13-th. Conf. MFCS, Springer LN Comput. Sci. 356 (1989) 269–300.

[8] Heintz J.: On the computational complexity of polynomials and bilinear mappings. A survey. Applied Algebra, Algebraic Algorithms and Error–Correcting Codes, 5th Intern. Conf. AAECC-5, Menorca 1987, L. Huguet and A. Poli, eds., Springer LN Comput. Sci. 356 (1989) 269–300.

[9] Heintz J. and Schnorr C.P.: Testing polynomials which are easy to compute, in : 12-th Ann. ACM Symp. Theory of Computing (1980) 262–280.

[10] Ibarra O.H. and Moran S.: Probabilistic algorithms for deciding equivalence of straight-line programs. J.ACM 30, 1 (1983) 217–228.

[11] Kaltofen E.: Greatest common divisors of polynomials given by Straight-line Programs. J.ACM 35 No. 1 (1988) 234–264.

[12] Lang S.: Algebra. Adisson-Wesley Publ. Comp., Reading, Massachusetts (1969).

[13] Stoss H.J.: On the representation of rational functions of bounded complexity. Theoret. Comput. Sci. 64 (1989) 1–13.

[14] Strassen V.: Berechnung und Programm I. Acta Inform.1 (1972) 320–334.

[15] Strassen V.: Vermeidung von Divisionen. J. reine u. angew. Math. vol. 264 (1973) 182–202.