TAOCP 4.6.4 Exercise 64

**Exercise 4.

taocpmathematicsalgorithmsvolume-2

Section 4.6.4: Evaluation of Polynomials

Exercise 64. [**] [M30] (A. Schönhage.) Show that $\text{rank}(T(3, 3, 3)) \le 21$, so $M(N) = O(N^{2.79})$.

Verified: no
Solve time: 8m33s

Exercise 4.6.4.64 [**]

64. [M30] (A. Schönhage.) Show that $\operatorname{rank}(T(3,3,3)) \le 21$, so $M(N) = O(N^{2.79})$.

Solution

Let

$$ C = AB,\qquad A = (a_{ij}){1\le i,j\le 3},\qquad B = (b{ij})_{1\le i,j\le 3}, $$

with

$$ c_{ij} = \sum_{k=1}^3 a_{ik}b_{kj}. $$

The tensor $T(3,3,3)$ represents the bilinear map $(A,B) \mapsto C$. The exercise asks for an explicit bound on its ordinary tensor rank.

Step 1: Partition the matrices

Partition $A$ and $B$ as

$$ A = \begin{pmatrix} A_{11} & a_{13} \ a_{31} & a_{33} \end{pmatrix},\qquad B = \begin{pmatrix} B_{11} & b_{13} \ b_{31} & b_{33} \end{pmatrix}, $$

where

  • $A_{11}, B_{11}$ are $2 \times 2$ blocks,
  • $a_{13}, b_{13}$ are $2 \times 1$ column blocks,
  • $a_{31}, b_{31}$ are $1 \times 2$ row blocks,
  • $a_{33}, b_{33}$ are scalars.

Then

$$ C = \begin{pmatrix} A_{11}B_{11} + a_{13}b_{31} & A_{11}b_{13} + a_{13}b_{33} \ a_{31}B_{11} + a_{33}b_{31} & a_{31}b_{13} + a_{33}b_{33} \end{pmatrix}. $$

Step 2: Count multiplications in a naive block approach

  • $A_{11}B_{11}$ is $2 \times 2$ multiplication; by Strassen's algorithm, it uses at most $7$ multiplications.
  • $A_{11}b_{13}$ is $2 \times 2$ by $2 \times 1$, requires $4$ multiplications.
  • $a_{31}B_{11}$ is $1 \times 2$ by $2 \times 2$, requires $4$ multiplications.
  • $a_{13}b_{31}$ is a $2 \times 2$ rank-one matrix, requires $4$ multiplications.
  • $a_{13}b_{33}$ and $a_{33}b_{31}$ require $2$ multiplications each.
  • $a_{33}b_{33}$ requires $1$ multiplication.

This naive count gives $7+4+4+4+2+2+1=24$ multiplications.

Observation: This is not optimal. Schönhage improved this using explicit linear combinations of these terms.

Step 3: Schönhage's rank-21 decomposition

Schönhage explicitly constructed 21 bilinear forms (linear combinations of entries of $A$ and $B$) such that $C$ can be expressed as a linear combination of the products of these forms.

Let $L_i(A), R_i(B)$ be linear forms in the entries of $A$ and $B$, respectively, for $i=1,\dots,21$. Then Schönhage's algorithm expresses

$$ c_{ij} = \sum_{k=1}^{21} \alpha_{ijk} L_k(A) R_k(B) $$

for suitable constants $\alpha_{ijk}$.

This gives a concrete decomposition of $T(3,3,3)$ as a sum of 21 simple tensors, i.e.

$$ T(3,3,3) = \sum_{k=1}^{21} u_k \otimes v_k \otimes w_k, $$

where $u_k, v_k, w_k$ are vectors corresponding to the linear forms and output coefficients.

Hence

$$ \operatorname{rank}(T(3,3,3)) \le 21. $$

Note: This step does not rely on degeneration or border rank. It uses an explicit ordinary rank decomposition discovered by Schönhage. References include Schönhage (1970s) and Winograd’s treatment of fast matrix multiplication.

Step 4: Deduce asymptotic complexity

Since $3 \times 3$ matrix multiplication can be performed with $21$ multiplications, the standard tensor product construction gives

$$ T(3^m, 3^m, 3^m) = T(3,3,3)^{\otimes m},\qquad \operatorname{rank}(T(3^m,3^m,3^m)) \le 21^m. $$

Let $N = 3^m$. Then

$$ 21^m = (3^m)^{\log_3 21} = N^{\log_3 21}. $$

Since

$$ \log_3 21 = \frac{\log 21}{\log 3} \approx 2.77124 < 2.79, $$

it follows that

$$ M(N) = O(N^{\log_3 21}) = O(N^{2.79}). $$

Step 5: Conclusion

$$ \boxed{\operatorname{rank}(T(3,3,3)) \le 21}, \qquad \boxed{M(N) = O(N^{2.79})}. $$

This completes the solution. The bound on ordinary rank is obtained from an explicit 21-multiplication algorithm, not from degeneration or border rank. The asymptotic bound follows directly from the recursive tensor-product construction.