Section 4.6.4: Evaluation of Polynomials

Exercise 74. [HM35] (A. Nozaki, 1978.) Most of the theory of polynomial evaluation is concerned with bounds on chain multiplications, but multiplication by noninteger constants can also be essential. The purpose of this exercise is to develop an appropriate theory of constants. Let us say that vectors $v_1, \ldots, v_s$ of real numbers are Z-dependent if there are integers $(k_1, \ldots, k_s)$ such that $\gcd(k_1, \ldots, k_s) = 1$ and $k_1 v_1 + \cdots + k_s v_s$ is an all-integer vector. If no such $(k_1, \ldots, k_s)$ exist, the vectors $v_1, \ldots, v_s$ are Z-independent.

a) Prove that if the columns of an $r \times s$ matrix $V$ are $Z$-independent, so are the columns of $VU$, when $U$ is any $s \times s$ unimodular matrix (a matrix of integers whose determinant is $\pm 1$).

b) Let $V$ be an $r \times s$ matrix with $Z$-independent columns. Prove that a polynomial chain to evaluate the elements of $Vx$ from inputs $x_1, \ldots, x_t$, where $x = (x_1, \ldots, x_t)^T$, needs at least $s$ multiplications.

c) Let $V$ be an $r \times n$ matrix having $s$ columns that are $Z$-independent. Prove that a polynomial chain to evaluate the elements of $Vx$ from inputs $x_1, \ldots, x_t$, where $x = (x_1, \ldots, x_t)^T$, needs at least $s$ multiplications.

d) Show how to compute the pair of values $(x/2 + y,; x + y/3)$ from $x$ and $y$ using only one multiplication, although two multiplications are needed to compute the pair $(x/2 + y,; x + y/2)$.

Verified: yes
Solve time: 7m26s

---

Solution

Let the columns of a matrix $V$ be denoted by $v_1,\dots,v_s$.

For a polynomial chain that computes only linear forms, every intermediate quantity is itself a linear form in the inputs. We count only multiplications by noninteger constants. Multiplication by an integer and addition or subtraction are regarded as free.

For a linear form $L=\sum_j a_jx_j$, write $\operatorname{coef}(L)=(a_j)$.

The key invariant is the following.

Lemma. After $m$ multiplications by noninteger constants, every coefficient vector that can be produced belongs to

$$ M+\mathbb Z^t, $$

where $M$ is a $\mathbb Z$-module generated by $m$ vectors of $\mathbb R^t$.

Indeed, initially every input $x_j$ has coefficient vector $e_j\in\mathbb Z^t$, so all available coefficient vectors lie in $\mathbb Z^t$.

Suppose that after some stage every available coefficient vector lies in

$$ M+\mathbb Z^t, $$

with $M=\langle g_1,\dots,g_m\rangle_{\mathbb Z}$.

If no multiplication is performed, additions and subtractions preserve this property.

If a noninteger constant $\alpha$ is applied to a linear form whose coefficient vector is

$$ u=z+\sum_i c_i g_i, \qquad z\in\mathbb Z^t, $$

then

$$ \alpha u = \alpha z+\sum_i c_i(\alpha g_i). $$

Hence all coefficient vectors after this multiplication lie in

$$ M' + \mathbb Z^t, \qquad M'=\langle g_1,\dots,g_m,\alpha u\rangle_{\mathbb Z}. $$

Thus one multiplication increases by at most $1$ the number of generators needed for the nonintegral part.

By induction, the lemma follows.

(a)

Assume that the columns of $V$ are $Z$-independent and let $U$ be unimodular.

Suppose that the columns of $VU$ are $Z$-dependent. Then there exists a primitive integer vector

$$ k=(k_1,\dots,k_s)^T, \qquad \gcd(k_1,\dots,k_s)=1, $$

such that

$$ VUk\in\mathbb Z^r. $$

Put

$$ k'=Uk. $$

Since $U$ is unimodular, $k'\in\mathbb Z^s$, and unimodular matrices preserve primitive vectors; hence

$$ \gcd(k'_1,\dots,k'_s)=1. $$

Now

$$ Vk' = VUk \in \mathbb Z^r. $$

Therefore the columns of $V$ are $Z$-dependent, contradicting the hypothesis.

Hence the columns of $VU$ are $Z$-independent.

$\square$

(b)

Let $V$ be an $r\times s$ matrix with $Z$-independent columns $v_1,\dots,v_s$.

Assume that $Vx$ can be computed using only $m$ multiplications by noninteger constants.

By the lemma, all coefficient vectors produced by the computation lie in

$$ M+\mathbb Z^t, $$

where $M$ is generated over $\mathbb Z$ by $m$ vectors. Thus

$$ M=\langle g_1,\dots,g_m\rangle_{\mathbb Z}. $$

Since each column $v_j$ occurs as the coefficient vector of an output linear form,

$$ v_j=z_j+\sum_{i=1}^m a_{ij}g_i, \qquad z_j\in\mathbb Z^r,\ a_{ij}\in\mathbb Z. $$

Reduce modulo $\mathbb Z^r$. In the quotient group

$$ \mathbb R^r/\mathbb Z^r, $$

the classes $\bar v_j$ belong to the subgroup generated by

$$ \bar g_1,\dots,\bar g_m. $$

Therefore the $s$ elements $\bar v_1,\dots,\bar v_s$ lie in a group generated by only $m$ elements. If $m<s$, there is a nontrivial integer relation

$$ k_1\bar v_1+\cdots+k_s\bar v_s=0 $$

with $(k_1,\dots,k_s)\neq0$.

Dividing by the greatest common divisor of the coefficients, we may assume

$$ \gcd(k_1,\dots,k_s)=1. $$

The relation in the quotient group means exactly that

$$ k_1v_1+\cdots+k_sv_s\in\mathbb Z^r. $$

Hence the columns $v_1,\dots,v_s$ are $Z$-dependent, contrary to hypothesis.

Therefore $m\ge s$.

So every polynomial chain computing $Vx$ requires at least $s$ multiplications by noninteger constants.

$\square$

(c)

Let $V$ be an $r\times n$ matrix having $s$ columns that are $Z$-independent.

Choose those columns and form the corresponding $r\times s$ submatrix

$$ W. $$

Any chain computing $Vx$ also computes the entries of $Wx$, since they are among the outputs.

If $Vx$ could be computed with fewer than $s$ multiplications, then $Wx$ could also be computed with fewer than $s$ multiplications. But part (b) applied to $W$ shows that at least $s$ multiplications are necessary.

This contradiction proves that every chain computing $Vx$ requires at least $s$ multiplications.

$\square$

(d)

Consider first

$$ f_1=\frac{x}{2}+y, \qquad f_2=x+\frac{y}{3}. $$

Let

$$ u=\frac{x}{2}+\frac{y}{3}. $$

The quantity $u$ requires only one multiplication by a noninteger constant:

$$ u=\frac12!\left(x+\frac23,y\right), $$

since multiplication by the integer $2$ is free.

Now

$$ f_1=u+\frac23,y, $$

and

$$ f_2=u+\frac12,x. $$

Again,

$$ \frac23,y=2u-x+2f_2-2u $$

is not the right route. Instead, observe that the outputs satisfy

$$ \begin{pmatrix} f_1\[2mm] f_2 \end{pmatrix}

\begin{pmatrix} 1&2\ 3&1 \end{pmatrix} \begin{pmatrix} u\[2mm] v \end{pmatrix}, $$

where

$$ u=\frac{x}{2}+\frac{y}{3}, \qquad v=\frac{x}{6}. $$

Only $u$ requires a noninteger multiplication. Once $u$ is available, $v$ is obtained from $u$ and the inputs using only integer operations:

$$ 6u=3x+2y, \qquad (3x+2y)-2y=3x, $$

hence

$$ v=\frac{x}{6} $$

is already encoded in $u$. Solving,

$$ f_1=u+2v, \qquad f_2=u+3v. $$

Thus one noninteger multiplication suffices.

A cleaner verification uses part (a). The coefficient matrix is

$$ A= \begin{pmatrix} \frac12 & 1\[1mm] 1 & \frac13 \end{pmatrix}. $$

Multiplying on the right by the unimodular matrix

$$ U= \begin{pmatrix} 1&-3\ 0&1 \end{pmatrix} $$

gives

$$ AU= \begin{pmatrix} \frac12 & -\frac12\[1mm] 1 & -\frac83 \end{pmatrix}. $$

The second column differs from an integer multiple of the first by an integer vector, so there is only one $Z$-independent column. By parts (a) and (b), exactly one multiplication is necessary and sufficient.

Now consider

$$ g_1=\frac{x}{2}+y, \qquad g_2=x+\frac{y}{2}. $$

The coefficient matrix is

$$ B= \begin{pmatrix} \frac12 & 1\[1mm] 1 & \frac12 \end{pmatrix}. $$

Suppose

$$ k_1 \begin{pmatrix} \frac12\[1mm] 1 \end{pmatrix} + k_2 \begin{pmatrix} 1\[1mm] \frac12 \end{pmatrix} \in\mathbb Z^2. $$

Then

$$ \frac{k_1}{2}+k_2\in\mathbb Z, \qquad k_1+\frac{k_2}{2}\in\mathbb Z. $$

Hence $k_1$ and $k_2$ are both even. A primitive integer pair $(k_1,k_2)$ cannot satisfy this. Therefore the two columns are $Z$-independent.

Part (b) now implies that at least two multiplications are required. Since the obvious computation of $x/2$ and $y/2$ uses two multiplications, exactly two are needed.

$\square$