brain

We are given a power series $U(z) = z + U_2 z^2 + U_3 z^3 + \cdots$ with power matrix $U = (u_{nk})$, where $u_n = u_{n1} = n U_n$.

**Exercise 4.

Let V(z) = V_1 z + V_2 z^2 + V_3 z^3 + \cdots, \quad V_1 \neq 0, and let

Let $U(z) = U_0 + U_1 z + U_2 z^2 + \cdots, \qquad U_0 \ne 0,$ and define the _odd induced function_ $U^{(o)}(z)$ to be the power series $V(z)$ satisfying V(z) = U(z V(z)^o).

Let the power (coefficient) matrices of $U$, $V$, and $W$ be $U=(u_{jk})$, $V=(v_{nj})$, and $W=(w_{nk})$, where these matrices encode the action of the corresponding formal power series operators as...

We continue from the definitions in exercise 17.

We are asked to prove that the poweroids $V_n(x)$ satisfy xV_n(x+y) = (x+y)\sum_{k=1}^{n} \binom{n-1}{k-1} V_k(x)V_{n-k}(y), continuing from Exercise 17.

Let $U^{[n]}(z)$ denote the $n$-fold composition of $U(z)$ with itself, as in Section 4.

**Problem.

Let F(z)=W_0+W_1z+\cdots+W_{N-1}z^{N-1}, the truncation of $W(z)$ modulo $z^N$.

We are asked: > For what functions $U(z)$ does $U^{[n]}(z)$ have the simple form $z^k$ in (27)?

We are asked to compute the first $N$ coefficients of the composed power series $W(z) = U(V(z)) = U_0 + U_1 V(z) + U_2 V(z)^2 + U_3 V(z)^3 + \cdots.$ Since $V(z)$ has no constant term, $V_0 = 0$, it f...

We are asked to connect **polynomial division** with **power series division**.

We are asked to extend Algorithm L to handle the more general situation in which $W(z) = G(t) = G_1 t + G_2 t^2 + G_3 t^3 + \cdots, \qquad z = V_1 t + V_2 t^2 + V_3 t^3 + \cdots, \quad V_1 \ne 0,$ and...

We are asked to find the coefficients in the expansion x = y^{1/a} + b_2 y^{1/a + 1} + b_3 y^{1/a + 2} + \cdots, given that

For the reversion of $z = t - t^2,$ Algorithm T is applied to the general form $U_1 z + U_2 z^2 + \cdots = t + V_2 t^2 + V_3 t^3 + \cdots,$ so here $U_1 = 1,\quad U_n = 0 \ (n \ge 2), \qquad V_2 = -1,...

Let $f(x) = x^{-1} - V(z).$ We seek a power series $x = W(z)$ such that $f(x)=0$, hence $W(z)^{-1} = V(z)$.

The solution directly constructs a bilinear algorithm that expresses all entries $c_{ij}$ of $C=AB$ as linear combinations of exactly 21 bilinear products of linear forms in the entries of $A$ and $B$...

Formula (9) expresses $W_n$ for $n \ge 1$ in terms of the coefficients $V_k$ and the previously computed $W_{n-k}$, and it contains an explicit factor $1/n$.

Let the original relation be $z = t + V_2 t^2 + V_3 t^3 + \cdots,$ and let its reversion be $t = z + W_2 z^2 + W_3 z^3 + \cdots.$ Reversion constructs the compositional inverse in the sense that subst...

The solution directly constructs a bilinear algorithm that expresses all entries $c_{ij}$ of $C=AB$ as linear combinations of exactly 21 bilinear products of linear forms in the entries of $A$ and $B$...

**2.

Let $V_m$ be the first nonzero coefficient of $V(z)$; thus $V(z)=z^m\widehat V(z),\qquad \widehat V_0=V_m\ne0.$ If $U(z)=z^r\widehat U(z),\qquad \widehat U_0=U_r\ne0,$ then $\frac{U(z)}{V(z)}=z^{\,r-m...

Let $N = m_1 \cdots m_k$ and consider a polynomial chain computing the discrete Fourier transform as a linear transformation $y = Fx,$ where $F$ is the $N \times N$ Fourier matrix with entries $\omega...

**Solution.

Let $T=(t_{ijk})$ be an $m\times n\times s$ tensor with rational entries.

Let a quasipolynomial chain compute $f(x_1,\ldots,x_n).$ Write the chain values as $v_1,\ldots,v_N,$ where each $v_i$ is either an input variable, a constant, or is obtained from earlier values by one...

X=\begin{pmatrix} x&u\\ e&Y \end{pmatrix},

Let $f(x_1,\ldots,x_n)=\sum_{1\le i<j\le n} x_i x_j.$ We count arithmetic complexity in the sense of straight-line programs: each multiplication is one operation, each addition is one operation, and i...

No.

Let $M(n) = \operatorname{rank}(T(n,n,n))$ denote the rank of the $n \times n$ matrix multiplication tensor.

**Statement.

Let $T(m,n,s)$ denote the tensor associated with multiplying an $m \times n$ matrix by an $n \times s$ matrix.

We restart from the correct structural facts about matrix multiplication tensors and tensor rank, and avoid any assumptions about multiplicativity of rank beyond what is valid: subadditivity under dec...

Let A=(a_{ij})_{1\le i,j\le 3}, \qquad B=(b_{ij})_{1\le i,j\le 3}, and let

We first restate the structure in a precise way consistent with the exercise.

Let $V$ be a $2$-dimensional vector space over a field $\mathbb{F}$ with basis ${e_1, e_2}$.

The original solution fails because it incorrectly attributes a Karatsuba-style recurrence $M(n)=3M(n/2)$ to the algorithm, which destroys the required bound on multiplications.

Let $T(m,n,s)$ denote the trilinear tensor corresponding to the $(m \times n)$ times $(n \times s)$ matrix multiplication problem, defined by $t_{(i,j')(j,k)(i,k)} = 1 \iff i' = i,\, j' = j,\, k' = k,...

We consider Exercise 4.

Let $u(x)=\sum_{i=0}^{n} a_i x^i,\qquad y(x)=\sum_{j=0}^{n} b_j x^j.$ Their product is $z(x)=u(x)y(x)=\sum_{k=0}^{2n} c_k x^k,$ where $c_k=\sum_{i+j=k} a_i b_j.$

**Exercise 4.

Let $P$ be an arbitrary $n \times n$ matrix, and consider the tensor defined in equation (74), which is the $n \times n \times n$ tensor $T = \bigl(t_{ijk}\bigr) \quad \text{with} \quad t_{ijk} = \del...

In §4.

Let $n = n'n''$ with $\gcd(n', n'') = 1$.

Unusual activity has been detected from your device.

We redo the construction cleanly and explicitly, giving full Winograd decompositions and verifying correctness.

Let $V$ be the space of $m\times n$ matrices and let $W$ be the space of $n\times1$ column vectors.

The key error in the previous solution is the incorrect step that an arbitrary rank-one term in the flattened matrix decomposition corresponds, after reshaping, to a rank-one $m\times n$ matrix.

Let ${t_{ijk}}$ be an $m \times n \times s$ tensor of rank $r = \text{rank}(t_{ijk})$, and let ${t'_{ijk}}$ be an $m' \times n' \times s'$ tensor of rank $r' = \text{rank}(t'_{ijk})$.

Let $V=F^{m}\otimes F^{n}\otimes F^{s}$, the vector space of all $m\times n\times s$ tensors over a field $F$.

Let u(x) = x^n + u_{n-1} x^{n-1} + \cdots + u_1 x + u_0 be a **monic polynomial** of degree $n$, with coefficients $u_{n-1}, \dots, u_0$.

Let the two bilinear forms be z_1(x,y)=x^\top A y,\qquad z_2(x,y)=x^\top B y, where $A,B\in \mathbb{F}^{2\times 2}$.

Let $\rho(T)$ denote the rank of a tensor $T={t_{ijk}}$, where rank means the least integer $r$ for which t_{ijk}=\sum_{\nu=1}^{r} a_{i\nu} b_{j\nu} c_{k\nu}.

Let $u(x)$ be a polynomial of degree $n$ over the integers.

Let S_n(x)=1+x+x^2+\cdots+x^n.

Let $M(n)$ denote the minimum number of multiplications needed to evaluate some polynomial of degree $n$, with arbitrary coefficients, when no preliminary adaptation of the coefficients is allowed.

We wish to compute the real and imaginary parts of the product of two complex numbers $(a + bi)(c + di)$ using only three real multiplications and five real additions, with two of the additions involv...

The previous solution fails because it tries to control Euclidean remainders and ignores the integrality constraints.

Let P(x;w_0,\ldots ,w_n) = \sum_{i=0}^{m} \Bigl(a_{i0}w_0+\cdots +a_{in}w_n+b_i\Bigr)x^i,

Let $R(x)=\frac{x^2+10x+29}{x^2+8x+19}.$ Since numerator and denominator have the same degree, divide polynomials: (x^2+10x+29)-(x^2+8x+19)=2x+10.

Assume that a polynomial chain computes a general fourth-degree polynomial with three multiplications and four addition-subtractions.

Exercise 35 established that a general fourth-degree polynomial cannot be computed with three multiplications and fewer than five addition-subtractions.

Let P(x) = u_1 x^3 + u_2 x^2 + u_0, where $u_0, u_1, u_2$ are independent parameters.

The previous solution fails because it never defines a correct model of computation and therefore cannot justify any dimension or “independent parameter” count.

Let $\lambda_0, \lambda_1, \ldots, \lambda_r$ be a polynomial chain in which all addition and subtraction steps are **parameter steps**, and suppose there is at least one **parameter multiplication**.

Let a **polynomial chain** be defined as in Section 4.

A polynomial chain computes expressions from the variable $x$ and parameters using additions, subtractions, and multiplications.

Let $R_1, \dots, R_m \subset \mathbb{R}^{n+1}$, and assume each $R_i$ has at most $t$ degrees of freedom.

Let $f_0, \ldots, f_r$ be multivariate polynomials with integer coefficients in the variables $\alpha_1, \ldots, \alpha_s$.

Let $R$ be the set of all $(n+1)$-tuples $(q_n,\ldots,q_0)$ of real numbers with $q_n \ne 0$.

The construction in Theorem M is a straight-line program for a polynomial, and the associated coefficients $\beta_i$ are obtained by the reverse propagation rule for the final value $\lambda_{10}$.

Let u(x) = u_3 x^3 + u_2 x^2 + u_1 x + u_0 be a cubic polynomial with real coefficients.

Let f(z) = a_n z^n + a_{n-1} z^{n-1} + \cdots + a_0 be a polynomial of degree $n$ with real coefficients, having at least $n-1$ roots with nonnegative real part.

We restart from the structural requirement of Theorem E.

Restart from the goal: construct a Pan-style evaluation scheme (16), meaning a straight-line program that minimizes multiplications by first generating needed powers of $x$ via a short addition chain,...

Solution to TAOCP 4.6.4 Exercise 21.

We are asked to write a MIX program that evaluates a fifth-degree polynomial according to scheme (11) in Section 4.

The proof of Ryser's identity is correct and complete.

Let the scheme (11) represent the nested evaluation form for a fifth-degree polynomial $u(x)=u_5x^5+u_4x^4+u_3x^3+u_2x^2+u_1x+u_0,$ rewritten in adapted Horner form with coefficients $a_0,\ldots,a_5$...

Let $x_0, x_1, \ldots, x_n$ be distinct real numbers.

Yes, the inequality $\nu(n) \le 2^{l(n) - \lambda(n)}$ holds for all positive integers $n$.

We are asked to show that the interpolation formula (45) reduces to a simple expression involving binomial coefficients when the nodes are in an arithmetic progression, namely $x_k = x_0 + kh, \qquad...

Let $N = 2^n$ and write $\omega = e^{2\pi i/N}$.

**Solution to Exercise 4.

Let $A,B \in F^{n\times n}$ and let $C=AB$.

Let $X = (x_{ij})$ be an $n \times n$ matrix.

Let $X = (x_{ij})$ be an $n \times n$ matrix.

Let R(X)=(-1)^n\sum_{\epsilon\in\{0,1\}^n} (-1)^{\epsilon_1+\cdots+\epsilon_n} \prod_{i=1}^n\sum_{j=1}^n \epsilon_jx_{ij}.

We are asked to improve steps S1, .

The clean way to remove the confusion is to derive the evaluation recurrence directly from the structure of the falling factorial basis, and then count operations in a single unified loop.

**Exercise 4.

Let $u(z) = u_n z^n + u_{n-1} z^{n-1} + \cdots + u_1 z + u_0$ be a polynomial of degree $n$, where each coefficient $u_k$ is complex and $z = x + iy$ is a complex variable.

Let $n$ be given and write $u(x)=u_n x^n+u_{n-1}x^{n-1}+\cdots+u_1x+u_0.$ Define the even and odd parts with respect to $x^2$: $E(x)=\sum_{k\ge 0} u_{2k} x^{2k}, \qquad O(x)=\sum_{k\ge 0} u_{2k+1} x^{...

Let $u(x,y)=\sum_{i+j\le n} u_{ij} x^i y^j$ be a bivariate polynomial of total degree $n$.

Let $u(x) = u_n x^n + u_{n-1} x^{n-1} + \cdots + u_1 x + u_0$ be a polynomial with coefficients in a ring $\mathcal{R}$, and suppose we wish to evaluate $u(x)$ when $x$ itself is a polynomial over $\m...

Let the chains in Exercise 34 be written in the standard form determined by the exponents \[ e_0>e_1>\cdots, \] and recall that two addition chains are regarded as equivalent when they have the same p...

Let $u(x)=u_{2n+1}x^{2n+1}+u_{2n-1}x^{2n-1}+\cdots+u_1x.$ Factor out $x$: $u(x)=x\left(u_{2n+1}x^{2n}+u_{2n-1}x^{2n-2}+\cdots+u_1\right).$ Introduce the substitution $y=x^2$.

We are asked to consider two addition chains for an integer n = 2^{e_0} + 2^{e_1} + \cdots + 2^{e_t}, \quad e_0 > e_1 > \cdots > e_t \ge 0, and to determine whether the **S-and-X chain** and the **Alg...

Let the addition chain be 1=a_1<a_2<\cdots<a_m=n,\qquad a_i=a_j+a_k\ (j,k<i), and assign cost $a_j a_k$ to step $a_i=a_j+a_k$.