TAOCP 4.6.4: Evaluation of Polynomials
Section 4.6.4 exercises: 72/74 solved.
Section 4.6.4. Evaluation of Polynomials
Exercises from TAOCP Volume 2 Section 4.6.4: 72/74 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [15] | simple | verified | 1m12s |
| 2 | ▶ [M20] | math-medium | verified | 1m13s |
| 3 | [30] | hard | verified | 1m18s |
| 4 | [M20] | math-medium | solved | 4m06s |
| 5 | [M15] | math-simple | verified | 2m28s |
| 6 | [22] | medium | verified | 2m32s |
| 7 | [M25] | math-medium | verified | 1m09s |
| 8 | [M20] | math-medium | verified | 4m25s |
| 9 | [M25] | math-medium | - | - |
| 10 | [M31] | math-hard | verified | 1m59s |
| 11 | [M46] | math-research | solved | 4m03s |
| 12 | [M50] | math-research | solved | 6m16s |
| 13 | [M23] | math-medium | verified | 1m16s |
| 14 | ▶ [HM28] | hm-hard | verified | 1m35s |
| 15 | ▶ [HM28] | hm-hard | verified | 1m40s |
| 16 | [M22] | math-medium | verified | 1m11s |
| 17 | [M20] | math-medium | verified | 1m13s |
| 18 | [M20] | math-medium | verified | 3m07s |
| 19 | ▶ [M21] | math-medium | verified | 1m09s |
| 20 | ▶ [21] | medium | verified | 4m11s |
| 21 | [**] | solved | 15m43s | |
| 22 | [**] | verified | 3m59s | |
| 23 | [**] | verified | 8m37s | |
| 24 | ▶ [**] | solved | 8m35s | |
| 25 | [**] | verified | 8m11s | |
| 26 | ▶ [**] | verified | 4m37s | |
| 27 | [**] | verified | 8m33s | |
| 28 | [HM20] | hm-medium | verified | 4m37s |
| 29 | ▶ [M20] | math-medium | solved | 10m46s |
| 30 | ▶ [M28] | math-hard | verified | 11m58s |
| 31 | [M23] | math-medium | verified | 7m16s |
| 32 | [M2] | math-simple | solved | 9m09s |
| 33 | ▶ [M25] | math-medium | verified | 9m03s |
| 34 | [M26] | math-hard | solved | 5m12s |
| 35 | ▶ [M25] | math-medium | solved | 6m52s |
| 36 | [M27] | math-hard | verified | 5m57s |
| 37 | [M21] | math-medium | verified | 4m56s |
| 38 | ▶ [**] | verified | 6m56s | |
| 39 | [**] | solved | 10m16s | |
| 40 | [**] | verified | 1m59s | |
| 41 | [**] | verified | 4m25s | |
| 42 | [**] | verified | 6m33s | |
| 43 | [**] | - | - | |
| 44 | ▶ [**] | solved | 9m30s | |
| 45 | ▶ [HM22] | hm-medium | verified | 7m06s |
| 46 | [M28] | math-hard | verified | 5m12s |
| 47 | [M25] | math-medium | solved | 10m07s |
| 48 | [M21] | math-medium | verified | 5m03s |
| 49 | [HM25] | hm-medium | verified | 57s |
| 50 | [HM20] | hm-medium | verified | 3m05s |
| 51 | ▶ [M24] | math-medium | verified | 6m44s |
| 52 | [M25] | math-medium | verified | 6m46s |
| 53 | [HM40] | hm-project | verified | 1m57s |
| 54 | [M23] | math-medium | verified | 1m40s |
| 55 | [HM22] | hm-medium | verified | 18m49s |
| 56 | [M32] | math-hard | verified | 1m41s |
| 57 | [M20] | math-medium | verified | 4m31s |
| 58 | [M28] | math-hard | verified | 11m18s |
| 59 | ▶ [M40] | math-project | verified | 2m20s |
| 60 | [M27] | math-hard | verified | 1m13s |
| 61 | [**] | solved | 6m11s | |
| 62 | [**] | solved | 6m15s | |
| 63 | [**] | verified | 2m39s | |
| 64 | [**] | solved | 8m33s | |
| 65 | ▶ [**] | verified | 3m18s | |
| 66 | [HM35] | hm-hard | verified | 1m37s |
| 67 | [HM40] | hm-project | verified | 7m06s |
| 68 | [M45] | math-project | verified | 3m45s |
| 69 | ▶ [HM27] | hm-hard | verified | 1m23s |
| 70 | ▶ [HM25] | hm-medium | verified | 6m13s |
| 71 | [HM30] | hm-hard | verified | 3m53s |
| 72 | [M48] | math-research | solved | 7m10s |
| 73 | [HM25] | hm-medium | verified | 6m03s |
| 74 | [HM35] | hm-hard | verified | 7m26s |
TAOCP 4.6.4 Exercise 1
Write the polynomial in the form u(x)=x\bigl(u_{2n+1}x^{2n}+u_{2n-1}x^{2n-2}+\cdots+u_1\bigr).
TAOCP 4.6.4 Exercise 2
Let $u(x) = u_n x^n + u_{n-1} x^{n-1} + \cdots + u_1 x + u_0$ be a polynomial over a ring $R$, and suppose we wish to compute $u(x)$ where $x$ itself is a polynomial, or more generally an element of a...
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.
TAOCP 4.6.4 Exercise 4
Let u(z) = u_n z^n + u_{n-1} z^{n-1} + \cdots + u_1 z + u_0, \qquad z, u_k \in \mathbb{C}, be a polynomial of degree $n$ with **complex coefficients**, evaluated at a complex number $z = x + iy$.
TAOCP 4.6.4 Exercise 5
Let u(x)=u_nx^n+u_{n-1}x^{n-1}+\cdots+u_1x+u_0 .
TAOCP 4.6.4 Exercise 6
Let $u(x) = \sum_{k=0}^n u_k x^k$ be a polynomial of degree $n$, and let $x_0$ be the point at which we wish to evaluate $u(x_0)$ and its derivatives.
TAOCP 4.6.4 Exercise 7
We wish to compute $\beta_0, \ldots, \beta_r$ so that the polynomial $u(x_0 + kh) = \beta_0 + \beta_1 k + \cdots + \beta_r k^r \eqno(6)$ for all integers $k$.
TAOCP 4.6.4 Exercise 8
Let P(x)=u_nx^{\underline n}+u_{n-1}x^{\underline{n-1}}+\cdots+u_1x^{\underline1}+u_0, where
TAOCP 4.6.4 Exercise 10
Let $X = (x_{ij})$ be an $n \times n$ matrix.
TAOCP 4.6.4 Exercise 11
Yes.
TAOCP 4.6.4 Exercise 12
Let S=\sum_{\epsilon_1,\ldots,\epsilon_n} (-1)^{\epsilon_1+\cdots+\epsilon_n} \prod_{1\le i\le n} \sum_{1\le j\le n}\epsilon_jx_{ij},
TAOCP 4.6.4 Exercise 13
Let the general discrete Fourier transform (37) be f(s_1,\ldots,s_n) = \sum_{t_1=0}^{m_1-1} \cdots
TAOCP 4.6.4 Exercise 14
Let $N=2^n,\qquad \omega=e^{2\pi i/N},$ and consider the discrete Fourier transform \qquad 0\le s<N.
TAOCP 4.6.4 Exercise 15
Let f[x_0]=f(x_0), and for $n>0$ define the divided differences recursively by
TAOCP 4.6.4 Exercise 16
Newton's interpolation polynomial (42) has the form u_n(x) = a_0 +a_1(x-x_0)
TAOCP 4.6.4 Exercise 17
We are asked to simplify the interpolation formula (45) when the nodes are equally spaced, that is, when $x_k = x_0 + kh, \qquad 0 \le k \le n.$ Formula (45) in Section 4.
TAOCP 4.6.4 Exercise 18
The scheme as printed in the exercise, u(x)=((y-a_2)y+a_3)x a_4, cannot represent a general quartic polynomial, because substituting
TAOCP 4.6.4 Exercise 19
The proposed solution does **not** answer the exercise that was stated.
TAOCP 4.6.4 Exercise 20
Let P(x)=u_0x^5+u_1x^4+u_2x^3+u_3x^2+u_4x+u_5.
TAOCP 4.6.4 Exercise 21
The reviewer's criticism is directed at the previous writeup, but it does not resolve the underlying problem: the exercise as presented here is missing the two definitions on which the computation dep...
TAOCP 4.6.4 Exercise 22
**Exercise 4.
TAOCP 4.6.4 Exercise 23
f(z)=a_nz^n+a_{n-1}z^{n-1}+\cdots+a_0, \qquad f(z)=g(z)+h(z), where $g$ is the even part and $h$ is the odd part:
TAOCP 4.6.4 Exercise 24
**Exercise 4.
TAOCP 4.6.4 Exercise 25
In the proof of Theorem M, the numbers $\beta_j$ are not introduced as “constant terms” by interpretation.
TAOCP 4.6.4 Exercise 26
Let the coefficients of a cubic polynomial be denoted by $\beta_1,\beta_2,\beta_3,\beta_4$.
TAOCP 4.6.4 Exercise 27
**Corrected Solution.
TAOCP 4.6.4 Exercise 28
Let f_0(\alpha_1,\ldots,\alpha_s),\; f_1(\alpha_1,\ldots,\alpha_s),\; \ldots,\; f_r(\alpha_1,\ldots,\alpha_s)
TAOCP 4.6.4 Exercise 29
Let $R_1, R_2, \ldots, R_m$ be sets of $(n+1)$-tuples of real numbers, each having at most $t$ degrees of freedom.
TAOCP 4.6.4 Exercise 30
**Exercise 4.
TAOCP 4.6.4 Exercise 31
Let a polynomial chain be capable of computing every monic polynomial p(x)=x^n+u_{n-1}x^{n-1}+\cdots+u_1x+u_0, where $u_0,\ldots,u_{n-1}$ are arbitrary parameters.
TAOCP 4.6.4 Exercise 32
**Corrected Solution for Exercise 4.
TAOCP 4.6.4 Exercise 33
Let n=2r+1 \qquad (r\ge 1).
TAOCP 4.6.4 Exercise 34
Let $\lambda_0, \lambda_1, \ldots, \lambda_r$ be a polynomial chain in which all addition and subtraction steps are parameter steps, and in which there is at least one parameter multiplication.
TAOCP 4.6.4 Exercise 35
Let u(x) = u_4 x^4 + u_3 x^3 + u_2 x^2 + u_1 x + u_0 be a general quartic polynomial with $u_4 \neq 0$.
TAOCP 4.6.4 Exercise 36
Let $A(n,m)$ denote the maximum number of independent parameters that can occur in any polynomial obtainable by a polynomial chain with $n$ addition-subtractions and $m$ multiplications.
TAOCP 4.6.4 Exercise 37
Let R(x)=\frac{P_0(x)}{Q_0(x)} =\frac{a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0} {x^n+b_{n-1}x^{\,n-1}+\cdots+b_0},
TAOCP 4.6.4 Exercise 38
**Solution.
TAOCP 4.6.4 Exercise 39
Let w_1=x(x+\alpha_1)+\beta_1=x^2+\alpha_1x+\beta_1, and for $k>1$,
TAOCP 4.6.4 Exercise 40
The lower bound given in Theorem C, $\lfloor n/2 \rfloor + 1$, is tight for general polynomials of degree $n$.
TAOCP 4.6.4 Exercise 41
Let us write $(a + bi)(c + di) = (ac - bd) + i(ad + bc)$.
TAOCP 4.6.4 Exercise 42
**Exercise 4.
TAOCP 4.6.4 Exercise 44
**Exercise 4.
TAOCP 4.6.4 Exercise 45
Let ${t_{ijk}}$ be an $m \times n \times s$ tensor of rank $r$, meaning that there exist vectors $a^{(p)} \in \mathbb{R}^m$, $b^{(p)} \in \mathbb{R}^n$, $c^{(p)} \in \mathbb{R}^s$ for $p = 1, \ldots,...
TAOCP 4.6.4 Exercise 46
Let \begin{aligned} z_1&=a_{11}x_1y_1+a_{12}x_1y_2+a_{21}x_2y_1+a_{22}x_2y_2,\\ z_2&=b_{11}x_1y_1+b_{12}x_1y_2+b_{21}x_2y_1+b_{22}x_2y_2, \end{aligned}
TAOCP 4.6.4 Exercise 47
Let $V=\mathbb F^{m\times n\times s}$ be the vector space of all $m\times n\times s$ tensors over a field $\mathbb F$.
TAOCP 4.6.4 Exercise 48
Let t_{ijk}=\sum_{\alpha=1}^{r} a_{\alpha i} b_{\alpha j} c_{\alpha k}, \qquad t'_{i'j'k'}=\sum_{\beta=1}^{r'} a'_{\beta i'} b'_{\beta j'} c'_{\beta k'},
TAOCP 4.6.4 Exercise 49
Let ${t_{ijk}}$ be an $m \times n \times s$ tensor over a field $F$.
TAOCP 4.6.4 Exercise 50
Let $T={t_{ijk}}$ be the $mn\times n\times m$ tensor corresponding to multiplication of an $m\times n$ matrix by an $n\times1$ column vector.
TAOCP 4.6.4 Exercise 51
Let A(x)=a_0+a_1x+\cdots+a_nx^n,\qquad B(x)=b_0+b_1x+\cdots+b_nx^n, and define the cyclic convolution
TAOCP 4.6.4 Exercise 52
Let $n = n'n''$ with $\gcd(n',n'')=1$, and let - a normal scheme for cyclic convolution of degree $n'$ use $m'$ chain multiplications, $p'$ parameter multiplications, and $a'$ additions, - a normal sc...
TAOCP 4.6.4 Exercise 53
Let f(s)=\sum_{t=1}^{m}F(t)\omega^{st}, \qquad 1\le s\le m, where $\omega$ is a primitive $m$th root of unity.
TAOCP 4.6.4 Exercise 54
Theorem W in Section 4.
TAOCP 4.6.4 Exercise 55
Let T(P) = \sum_{i,j=1}^{n} p_{ij}\, e_i \otimes e_j \otimes e_{ij}, where ${e_i}$, ${e_j}$, and ${e_{ij}}$ are the standard bases of the three tensor factors.
TAOCP 4.6.4 Exercise 56
Let Q_k(x_1,\ldots,x_n)=\sum_{i=1}^n\sum_{j=1}^n \tau_{ijk}x_i x_j, \qquad 1\le k\le s, be a family of quadratic forms.
TAOCP 4.6.4 Exercise 57
Let x(u)=\sum_{j=0}^{n}x_j u^j,\qquad y(u)=\sum_{j=0}^{n}y_j u^j, and let
TAOCP 4.6.4 Exercise 58
We consider the polynomial multiplication tensor $T$ defined in (55), corresponding to the bilinear map that sends a pair of polynomials of degrees at most $3$ and $2$ respectively to their product of...
TAOCP 4.6.4 Exercise 59
Let $(x_0, x_1, \ldots, x_{n-1})$ and $(y_0, y_1, \ldots, y_{n-1})$ be sequences of integers with $n = 2^m$.
TAOCP 4.6.4 Exercise 60
Let $T(m, n, s)$ denote the $(mn \times ns \times ms)$ tensor corresponding to $(m \times n)$ times $(n \times s)$ matrix multiplication over a commutative ring, with entries t_{(i,j')(j,k)(i,k)} = \b...
TAOCP 4.6.4 Exercise 61
\text{Let } r_k(T)=\operatorname{rank}_k(T).
TAOCP 4.6.4 Exercise 62
Let T=\begin{pmatrix}1&0\\0&1\end{pmatrix} denote the tensor with nonzero entries
TAOCP 4.6.4 Exercise 63
For (a), the trilinear form corresponding to $T(m,n,s)$ is \sum_{i,j,k} x_{ij}y_{jk}z_{ki}.
TAOCP 4.6.4 Exercise 64
**Exercise 4.
TAOCP 4.6.4 Exercise 65
Let A=\{x_1,\ldots,x_m\},\qquad B=\{y_1,\ldots,y_n\}, and introduce auxiliary variables $X_{ij},Y_{ij}$ $(1\le i\le m,\ 1\le j\le n)$ subject to
TAOCP 4.6.4 Exercise 66
Let $M(N)=\operatorname{rank}(T(N,N,N))$, and let $\omega$ denote the exponent of matrix multiplication.
TAOCP 4.6.4 Exercise 67
Let $T(m,n,s)$ denote the matrix-multiplication tensor.
TAOCP 4.6.4 Exercise 68
Let $x_1, \ldots, x_n$ be variables and consider the polynomial $S_n = \sum_{1 \le i < j \le n} x_i x_j = x_1 x_2 + x_1 x_3 + \cdots + x_{n-1} x_n.$ We are asked whether $S_n$ can be evaluated using f...
TAOCP 4.6.4 Exercise 69
Let $D_n(X)=\det(X), \qquad X=(x_{ij})_{1\le i,j\le n},$ where $D_n(X)$ is the determinant polynomial of degree $n$ in the $n^2$ variables $x_{ij}$.
TAOCP 4.6.4 Exercise 70
Write X= \begin{pmatrix} x & u\\ v & Y
TAOCP 4.6.4 Exercise 71
Let $f(x_1,\ldots,x_n)$ be a function computed by a quasipolynomial chain using the operations $+,-,\times,\div$.
TAOCP 4.6.4 Exercise 72
Let $T=(t_{ijk})$ be a finite tensor with rational entries.