Skip to content

4.2 Strassen’s algorithm for matrix multiplication

Note: You may wish to read Section 4.5 before attempting some of these exercises.

4.2-1

Use Strassen’s algorithm to compute the matrix product

$$ \begin{pmatrix} 1 & 3\cr 7 & 5 \end{pmatrix} \begin{pmatrix} 6 & 8\cr 4 & 2 \end{pmatrix} $$

Show your work.

$$ \begin{aligned} S_1 & = B_{12} - B_{22} = 8 - 2 = 6\cr S_2 & = A_{11} + A_{12} = 1 + 3 = 4\cr S_3 & = A_{21} + A_{22} = 7 + 5 = 12\cr S_4 & = B_{21} - B_{11} = 4 - 6 = -2\cr S_5 & = A_{11} + A_{22} = 1 + 5 = 6\cr S_6 & = B_{11} + B_{22} = 6 + 2 = 8\cr S_7 & = A_{12} - A_{22} = 3 - 5 = -2\cr S_8 & = B_{21} + B_{22} = 4 + 2 = 6\cr S_9 & = A_{11} - A_{21} = 1 - 7 = -6\cr S_{10} & = B_{11} + B_{12} = 6 + 8 = 14\cr P_1 & = A_{11} \cdot S_1 = 1 * 6 = 6\cr P_2 & = S_2 \cdot B_{22}=4 * 2 = 8\cr P_3 & = S_3 \cdot B_{11} = 12 * 6 = 72\cr P_4 & = A_{22} \cdot S_{4} = 5 * (-2) = -10\cr P_5 & = S_5 \cdot S_6 = 6 * 8 = 48\cr P_6 & = S_7 \cdot S_8 = -2 * 6 = -12\cr P_7 & = S_9 \cdot S_10 = -6 * 14 = -84\cr C_{11} & = C_{11} + P_5 + P_4 - P_2 + P_6 = 48 + (-10) - 8 + (-12) = 18\cr C_{12} & = C_{12} + P_1 + P_2 = 6 + 8 = 14\cr C_{21} & = C_{21} + P_3 + P_4 = 72 + (-10) = 62\cr C_{22} & =C_{22} + P_5 + P_1 - P_3 - P_7 = 48 + 6 - 72 - (-84) = 66\cr C & = \begin{pmatrix} 18 & 14\cr 62 & 66\cr \end{pmatrix} \end{aligned} $$

4.2-2

Write pseudocode for Strassen’s algorithm.

Strassen(A,B,C,n)
    if n ==1
        c11=c11+a11*b11
    partition A,B,C into (n/2)*(n/2) submatrixs
    A11,A12,A21,A22;B11,B12,B21,B22;C11,C12,C21,C22
    //get S O(n^2)
    S1=B12-B22
    S2=A11+A12
    S3=A21+A22
    S4=B21-B11
    S5=A11+A22
    S6=B11+B22
    S7=A12-A22
    S8=B21+B22
    S9=A11-A21
    S10=B11+B12
    //creat P O(n^2)
    creat P1...7
    //recursion
    Strassen(A11,S1,P1,n/2)
    Strassen(S2,B22,P2,n/2)
    Strassen(S3,B11,P3,n/2)
    Strassen(A22,S4,P4,n/2)
    Strassen(S5,S6,P5,n/2)
    Strassen(S7,S8,P6,n/2)
    Strassen(S9,S10,P7,n/2)
    //conquer O(n^2)
    C11=C11+P5+P4-P2+P6
    C12=C12+P1+P2
    C21=C21+P3+P4
    C22=C22+P5+P1-P3-P7

4.2-3

What is the largest $k$ such that if you can multiply $3\times 3$ matrices using $k$ multiplications (not assuming commutativity of multiplication), then you can multiply $n\times n$ matrices in $o(n^{\lg 7})$ time? What is the running time of this algorithm?

$$ \begin{aligned} T(n)=kT(n/3)+O(1)=o(n^{\lg 7})\cr \implies T(n)=\Theta(n^{\log_{3} k})=o(n^{\lg 7})\cr \implies \log_{3} k < \lg 7\cr \implies k < 21.8\cr \implies \max(k) = 21\cr \text{running time }= n^{\log_{3} 21}\cr \end{aligned} $$

4.2-4

V. Pan discovered a way of multiplying $68\times 68$ matrices using 132,464 multiplications, a way of multiplying $70\times 70$ matrices using 143,640 multiplications, and a way of multiplying $72\times 72$ matrices using 155,424 multiplications. Which method yields the best asymptotic running time when used in a divide-and-conquer matrix-multiplication algorithm? How does it compare with Strassen’s algorithm?

$n^{\log_{68}132464}=n^{2.79513};n^{\log_{70} 143640}=n^{2.79512};n^{\log_{72} 155424}=n^{2.79515};n^{\lg 7}=n^{2.80735}$

the second method is the best; better than Strassen's algorithm.

4.2-5

Show how to multiply the complex numbers $a+bi$ and $c+di$ using only three multiplications of real numbers. The algorithm should take $a,b,c$, and $d$ as input and produce the real component $ac-bd$ and the imaginary component $ad+bc$ separately.

$$ \begin{aligned} S_1=a(c-d)=ac-ad\cr S_2=b(c+d)=bc+bd\cr S_3=d(a-b)=ad-bd\cr S_1+S_3=ac-bd\cr S_2+S_3=ad+bc\cr \end{aligned} $$

4.2-6

Suppose that you have a $\Theta(n^{\alpha})$-time algorithm for squaring $n \times n$ matrices, where $\alpha \geq 2$. Show how to use that algorithm to multiply two different $n \times n$ matrices in $\Theta(n^{\alpha})$ time.

$$ \begin{aligned} A\cdot B=\frac{(A+B)^{2}-(A-B)^2}{4} \end{aligned} $$