TAOCP 4.6.4 Exercise 3
Let u(x,y)=\sum_{i+j\le n}u_{ij}x^iy^j be a polynomial of total degree $n$ in two variables.
Section 4.6.4: Evaluation of Polynomials
Exercise 3. [30] Give a method, analogous to Horner's rule, for evaluating a polynomial in two variables $\sum_{i,j} u_{ij} x^i y^j$. (This polynomial has $(n+1)(n+2)/2$ coefficients, and its "total degree" is $n$.) Count the number of additions and multiplications you use.
Verified: yes
Solve time: 1m18s
Setup
Let
$$ u(x,y)=\sum_{i+j\le n}u_{ij}x^iy^j $$
be a polynomial of total degree $n$ in two variables. The number of coefficients is
$$ \sum_{k=0}^{n}(k+1)=\frac{(n+1)(n+2)}2. $$
The problem asks for a method analogous to Horner's rule and for a count of the additions and multiplications required.
Write
$$ u(x,y)=\sum_{j=0}^{n}a_j(x)y^j, $$
where
$$ a_j(x)=\sum_{i=0}^{n-j}u_{ij}x^i. $$
Each $a_j(x)$ is a polynomial in $x$ of degree at most $n-j$.
Solution
Apply Horner's rule first to each coefficient polynomial $a_j(x)$.
For fixed $j$, compute
$$ a_j(x) = (\cdots((u_{n-j,j}x+u_{n-j-1,j})x+u_{n-j-2,j})x+\cdots)x+u_{0j}. $$
Since $\deg a_j=n-j$, this requires
$$ n-j $$
multiplications and
$$ n-j $$
additions.
After all values $a_0(x),a_1(x),\ldots,a_n(x)$ have been obtained, evaluate
$$ u(x,y) = (\cdots((a_n(x)y+a_{n-1}(x))y+a_{n-2}(x))y+\cdots)y+a_0(x) $$
by Horner's rule in the variable $y$.
This second stage requires
$$ n $$
multiplications and
$$ n $$
additions.
Hence the total number of multiplications is
$$ \sum_{j=0}^{n}(n-j)+n = \sum_{k=0}^{n}k+n = \frac{n(n+1)}2+n = \frac{n(n+3)}2. $$
The total number of additions is the same:
$$ \sum_{j=0}^{n}(n-j)+n = \frac{n(n+3)}2. $$
Therefore the polynomial can be evaluated by a nested Horner scheme,
$$ u(x,y) = (\cdots((a_n(x)y+a_{n-1}(x))y+\cdots)y+a_1(x))y+a_0(x), $$
with each $a_j(x)$ itself evaluated by Horner's rule, using
$$ \frac{n(n+3)}2 $$
multiplications and
$$ \frac{n(n+3)}2 $$
additions.
Verification
The coefficient polynomial $a_j(x)$ contains exactly
$$ n-j+1 $$
terms. Horner's rule for a polynomial with $n-j+1$ coefficients uses exactly
$$ n-j $$
multiplications and
$$ n-j $$
additions.
Summing over all $j$ gives
$$ \sum_{j=0}^{n}(n-j) = \frac{n(n+1)}2. $$
The outer Horner evaluation in $y$ has degree $n$ and therefore contributes exactly $n$ multiplications and $n$ additions.
Adding the two contributions yields
$$ \frac{n(n+1)}2+n = \frac{n(n+3)}2 $$
operations of each type.
Since the polynomial has
$$ \frac{(n+1)(n+2)}2 $$
coefficients, the number of additions equals the number of coefficients minus $1$, which is consistent with combining all coefficient contributions into a single value.
Thus the count is correct.
Notes
The same idea extends recursively to any number of variables. One chooses an ordering of the variables and repeatedly regards the polynomial as a univariate polynomial whose coefficients are polynomials in the remaining variables, then applies Horner's rule at each level.
$$ \boxed{\text{Multiplications }=\frac{n(n+3)}2,\qquad \text{Additions }=\frac{n(n+3)}2.} $$