# On the parallel evaluation of rational functions

Laurent Hyafil

► To cite this version:

Laurent Hyafil. On the parallel evaluation of rational functions. IRIA-RR-258, IRIA. 1977, pp.8. hal-04837200

HAL Id: hal-04837200

https://inria.hal.science/hal-04837200v1

Submitted on 13 Dec 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
105 78150 - Le Chesnay
France
Tel: 954 90 20

laboratoire de recherche
en informatique
et automatique

ON THE
PARALLEL EVALUATION
OF RATIONAL FUNCTIONS

Laurent HYAFIL

Rapport de Recherche N° 258

Octobre 1977
ON THE PARALLEL EVALUATION OF RATIONAL FUNCTIONS

Laurent Hyafil

IRIA/LABORIA

Résumé :

Nous montrons dans cet article que n'importe quel polynôme P de degré d qui peut être calculé avec $C^*$ (P) multiplications/divisions peut être calculé en moins de $O(\log d \cdot \log C^* (P))$ étapes en parallèle, et moins de $O(\log d)$ étapes de multiplications en parallèle.

Abstratc :

In this paper we prove that any multivariate polynomial $P$ of degree $d$ that can be computed with $C^*$ (P) multiplications-divisions can be computed in less than $O(\log d \cdot \log C^* (P))$ parallel steps and less than $O(\log d)$ parallel multiplicative steps.
# 1. Introduction.

The interest of building large multiprocessors such that Illiac IV ([1]) or C.mmp ([7]) is mostly dependent on the ease to provide efficient parallel algorithms to perform computations. Even for every simple problems, theoretical limitations have been given ([4],[6]) which restrict the use of multi-processors. The result we show in this paper is, on the contrary, an optimistic result. Roughly speaking it says that any sequential computation can be parallelized in an almost optimal manner, the only limitations resulting from the degree and from the sequential complexity of the function; and this is an intrinsic complexity since we know a lower bound of $max(\log d, \log C^*(P))$ steps. Although the algorithm we give is not usable in practice, we could have foreseen the existence of a recent algorithm for the parallel solution of linear systems of size $n$ in $\log n^2$ steps ([2]).

The proof of the main Theorem is based on a decomposition which has been used previously to establish lower bounds in sequential complexity ([3],[5]). Furthermore, from this result we can deduce a relationship between the multiplicative and the total complexity of a function.
## 2. Definitions

- K will denote an infinite field

- $K[x_1, x_2, \dots, x_n]$ the ring extension of $K$ by the set of indeterminates
  $\{x_1, x_2, \dots, x_n\}$

- A program $\beta$ in $K[x_1, x_2, \dots, x_n]$ mod. $K\{x_1, x_2, \dots, x_n\}$ is a sequence
  $F = \{f_0, f_1, \dots, f_\ell\}$ of functions of $K[x_1, x_2, \dots, x_n]$ such that
  $f_i \in K\{x_1, x_2, \dots, x_n\}$ or $f_i = f_j \circ f_k$ with $j, k < i$ and $\circ \in \{+, -, x, \frac{1}{x}\}$.

- A program $\beta$ computes a function of $K[x_1, x_2, \dots, x_n]$ if $f \in F$ (we write
  by extension $f \in \beta$).

- $C^*(P_1, P_2, \dots, P_m)$ will denote the $*$-complexity of $P_1, P_2, \dots, P_m$ i.e. the minimum number of non scalar multiplications-divisions necessary to compute $P_1, P_2, \dots, P_m$ with a program $\beta$.

- A program $\beta$ will be called homogeneous of degree $d$ if:

a) For any additive operation of $\beta$, $P_i = Q_i \oplus R_i$ then $Q_i$ and $R_i$ are homogeneous and have a same degree $\le d$

b) $\beta$ has no division

c) For any multiplication $P_i = Q_i \times R_i$, $Q_i$ and $R_i$ are homogeneous and the degree of $P_i$ is $\le d$.

- $C_d^H(P_1, P_2, \dots, P_m)$ will denote the minimum number of non scalar multiplications necessary to compute $P_1, P_2, \dots, P_m$ with an homogeneous program of degree $d$.

## 3. Statement of the results

### Lemma 1

Let $P$ be a multivariate polynomial of degree $d$ and $P_1, P_2, \dots, P_d$ the homogeneous terms of $P$, then:

$$C_d^H(P_1, P_2, \dots, P_d) \le \left[ \frac{d(d-1)}{2} \right]^2 C^*(P).$$

*Proof:* let $P$ be a program which computes $P$ in $C^*(P)$ non scalar multiplications/divisions, apply to $P$ the transformation defined in [3] or [5].
### Lemma 2

Let $\mathcal{H}$ be an homogeneous program which computes homogeneous polynomials $P_1, P_2, \dots, P_m$ in $n$ indeterminates and of degrees $\le d$ with $C_d^H(P_1, P_2, \dots, P_m)$ multiplications. There exists a set of homogeneous polynomials $U_1, U_2, \dots, U_{n+l} \subseteq \mathcal{H}$ satisfying:

a) $\frac{d}{3} \le \deg(U_j) \le \frac{2d}{3}$ for $1 \le j \le n+l$,

b) for $f_i \in \mathcal{H}$ with $\frac{d}{3} < \deg(f_i) < d$ there exist homogeneous polynomials of degrees $\le \frac{2d}{3}$ of $V_i^j$ for $1 \le j \le n+l$ such that $f_i = \sum_{j=1}^{n+l} U_i V_i^j$, where $\sum_{j=1}^{n+d} C_d^H(P_1, P_2, \dots, P_m)$.

**Proof:**

The proof is by induction on $l(Hd/P_1, P_2, \dots, P_m)$ minimum length of an homogeneous program which computes $P_1, P_2, \dots, P_m$. The case $l(Hd/P_1, P_2, \dots, P_m)=0$ being obvious, assume that lemma 2 is true for $l(Hd/P_1, P_2, \dots, P_m)=1$ and consider the case $l(Hd/P_1, P_2, \dots, P_m)=\lambda+1$.

The homogeneous program $\mathcal{H}$ which computes $P_1, P_2, \dots, P_m$ in $\lambda+1$ instructions has a last instruction which can be assumed to be $P_1 = f \circ f'$ without loss of generality.

**Case 1 :** $P_1 = f + f'$

$l(Hd/f, f', P_2, \dots, P_m) = 1$ and we prove the case by applying the induction hypothesis to $f, f', P_2, \dots, P_m$.

**Case 2 :** $P_1 = f \circ f'$

$l(Hd/f, f', P_2, \dots, P_m) = 1$ and if we set $C_d^H(P_1, P_2, \dots, P_m)$ then $P_1(f, f', P_2, \dots, P_m) = -1$.
According to the induction hypothesis there exists a set of homogeneous
polynomials $U_1, U_2, \dots, U_{n+\ell}$ satisfying the previous conditions a) and b). So,
all we need to prove is the existence of an homogeneous polynomial $U_{n+\ell+1}$

with

$$ - \frac{d}{3} \le \deg(U_{n+\ell+1}) \le \frac{2d}{3}, $$

$$ - P_1 = \sum_{j=1}^{n+\ell+1} U_j V_1^j \quad \text{for a set of homogeneous polynomials } V_1^j. $$

For $1 \le j \le n+\ell$ there exist homogeneous polynomials $V_j, V_j'$ such that :

$$ - \text{if } \deg(f) \ge \frac{d}{3} : f = \sum_{j=1}^{n+\ell} U_j V_j, $$

$$ - \text{if } \deg(f') \ge \frac{d}{3} : f' = \sum_{j=1}^{n+\ell} U_j V_j'. $$

So we can distinguish 3 cases :

$$ \alpha) \deg(P_1) < \frac{d}{3} \text{ we choose } U_{n+\ell+1} = 0 $$

$$ \beta) \deg(f) \ge \frac{d}{3} \text{ (resp. } \deg(f') \ge \frac{d}{3}\text{)} $$

$$ P_1 = f \times f' = \sum_{j=1}^{n+\ell} U_j (V_j f') $$

So we choose $U_{n+\ell+1} = 0$.

$$ \gamma) \deg(f) < \frac{d}{3} \text{ and } \deg(f') < \frac{d}{3} $$

Then we have $\frac{d}{3} < \deg(P_1) < \frac{2d}{3}$ and we choose $U_{n+\ell+1} = P_1$. ∎
Theorem :

A polynomial $P$ of degree $\le d$ in $n$ indeterminates which can be computed
with $C^*(P)$ multiplications can be computed with no more than :
than :

$$
- \left[ \frac{1}{\log_2 3 - 1} \log_2 d \right] \text{ parallel multiplicative steps,}
$$

$$
- \left[ \frac{\log_2 d}{[\log_2 3-1]} \right] \left[ \log_2 \left[ \left( \frac{d(d-1)}{2} \right)^2 C^*(P)+n \right]+1 \right] + \left[ \log_2 d \right] \text{ parallel steps.}
$$

Proof :

To compute $P$, we compute in parallel each of the $d$ homogeneous polynomials, the sum of which is $P$.

Let $Q$ be an homogeneous polynomial of degree $\le d$

$$
Q = \sum_{j=1}^{n+\ell} U_j V_j \quad \text{where the } U_j\text{'s satisfy the above conditions a)} \\
\text{and b)} \text{ and with } \ell \le C_d^H(Q).
$$

To compute $Q$ we use the following parallel algorithm :

. Compute in parallel the U_j's and the V_j's (use this algorithm recursively)

. Multiply in parallel U_j x V_j

. Compute $Q$ from the above formula in $\left[ \log[C_d^H(Q)+n] \right]$ steps

By lemma 2 we know that each of the $U_j$ and $V_j$ has a degree $\le \frac{2d}{3}$ and furthermore each of the $U_j$'s is computed with less than $C_d^H(Q)$ multiplications since it is computed by the program which computes $Q$. To complete the proof of the theorem we show that each of the $V_j$ can be computed by an homogeneous program in less than $C_d^H(Q)$ steps (by lemma 1 we know that

$$
C_d^H(Q) < \left\lfloor \frac{d(d-1)}{2} \right\rfloor^2 C^*(P).
$$

Let $H$ be the homogeneous program which computes $Q$. Each of the $U_j$ is the
result of a multiplication. Let $\alpha_i$ be the integer such that the multiplication
generating $U_i$ is $f_{\alpha_i} + f_r \times f_s$ for some $r$ and $s$. Assume we substitute in $H$
$f_{\alpha_i}$ by $0$ for $i \neq j$ and $f_{\alpha_i}$ by $1$ every time they appear on the right side of
an instruction. It is obvious to check that this new program computes $V_i$. []
**Corollary :**

A polynomial $P$ of degree $\le d$ in $n$ indeterminates, which can be computed
with $C^*(P)$ multiplications-divisions can be computed in less than
$O([C^*(P)]^{\alpha \log_2 d})$ total number of operations ($\alpha \le 2$).

3. Acknowledgements.

Many thanks to A. Borodin for helpful corrections on the first draft
of this paper.

4. References

[1] Barnes G. et. al., The Illiac IV computer, _IEFE Trans. Comp._, vol c-17,
1968, 746-757.

[2] Csansky L., Fast parallel matrix inversion algorithms, 15th Symposium F.O.C.S Proc., 1975, 11-12.

[3] Hyafil L., The power of commutativity, 18th F.O.C.S. Conference Proc., 1977.

[4] Hyafil L., Kung H.T., The complexity of parallel evaluation of linear recurrences, JACM, vol 24, n°3, 1977.

[5] Hyafil L., Van de Wiele J.P., Bornes inférieures pour la complexité des polynômes à coefficients 0-1, Rapport Laboria n° 192, 1976.

[6] Kung H.T., New algorithms and lower bounds for the parallel evaluation of certain rational expressions and recurrences, JACM, vol 23 n°2, 1976, 252-261.

[7] Wulf W., Bell C., C.mmp - A multi-mini-processor, AFIPS Conference Proc. vol 41, part II, FJCC, 1972, 765-777.