Multiplying two matrices using a recursive algorithm

1.1k Views Asked by At

I'd like to step thru the algorithm below to see if I understand how it works.

 MATRIX-MULTIPLY-RECURSIVE(A, B, C, n)
   if n == 1
   // Base case.
      c_11 = c_11 + a_11 · b_11
      return
   // Divide.
   partition A, B, and C into n/2 × n/2 submatrices A_11, A_12, A_21, A_22; B_11, B_12, B_21, B_22; 
       and C_11, C_12, C_21, C_22; respectively
   // Conquer.
   MATRIX-MULTIPLY-RECURSIVE(A_11, B_11, C_11, n/2)
   MATRIX-MULTIPLY-RECURSIVE(A_11, B_12, C_12, n/2)
   MATRIX-MULTIPLY-RECURSIVE(A_21, B_11, C_21, n/2)
   MATRIX-MULTIPLY-RECURSIVE(A_21, B_12, C_22, n/2)
   MATRIX-MULTIPLY-RECURSIVE(A_12, B_21, C_11, n/2)
   MATRIX-MULTIPLY-RECURSIVE(A_12, B_22, C_12, n/2)
   MATRIX-MULTIPLY-RECURSIVE(A_22, B_21, C_21, n/2)
   MATRIX-MULTIPLY-RECURSIVE(A_22, B_22, C_22, n/2)

Consider $A = \begin{pmatrix}1 & 2 & 1 & 2 \\\ 3 & 8 & 2 & 2 \\ 5 & 1 & 4 & 9 \\\ 6 & 2 & 5 & 0\end{pmatrix}$ and $B = \begin{pmatrix}1 & 2 & 5 & 6 \\\ 3 & 4 & 7 & 8 \\ 9 & 1 & 4 & 5 \\\ 2 & 3 & 6 & 7\end{pmatrix}$. I'll use $\text{ MATRIX-MULTIPLY-RECURSIVE(MMR) }$ algo to multiply $A$ and $B$.

Since $n > 1$, we break $A, B$ into eight $\displaystyle{\frac n2}$ matrices: $$A_{11} = \begin{pmatrix}1 & 2\\\ 3 & 8 \end{pmatrix}, \ A_{12} = \begin{pmatrix}1 & 2 \\\ 2 & 2 \end{pmatrix}, \ A_{21} = \begin{pmatrix}5 & 1\\\ 6 & 2\end{pmatrix}, \ A_{22} = \begin{pmatrix} 4 & 9 \\\ 5 & 0\end{pmatrix} \\\ B_{11} = \begin{pmatrix}1 & 2\\\ 3 & 4\end{pmatrix}, \ B_{12} = \begin{pmatrix}5 & 6 \\\ 7 & 8\end{pmatrix}, \ B_{21} = \begin{pmatrix}9 & 1 \\\ 2 & 3\end{pmatrix}, \ B_{22} = \begin{pmatrix}4 & 5 \\\ 6 & 7\end{pmatrix}$$

Now $\text{MMR}(A_{11}, B_{11}, C_{11}, 2)$ produces eight matrices which are integers. I'll use $\color{red}{\text{ red }}$ indices to distinguish these matrices from the forgoing ones: $$A_{\color{red}{11}} = 1, A_{\color{red}{12}} = 2, A_{\color{red}{21}} = 3, A_{\color{red}{22}} = 8 \\\ B_{\color{red}{11}} = 1, B_{\color{red}{12}} = 2, B_{\color{red}{21}} = 3, B_{\color{red}{22}} = 4$$

Applying the matrix-multiplication procedure on the integers above, we have $$C_{\color{red}{11}} = 1 \cdot 1 + 2 \cdot 3 = 7 \\\ C_{\color{red}{12}} = 1 \cdot 2 + 2 \cdot 4 = 10 \\\ C_{\color{red}{21}} = 3 \cdot 1 + 8 \cdot 3 = 24 \\\ C_{\color{red}{22}} = 3 \cdot 2 + 8 \cdot 4 = 38$$ which give us $C_{11} = \text{MMR}(A_{11}, B_{11}, C_{11}, 2) = \begin{pmatrix}7 & 10\\\ 24 & 38\end{pmatrix}$.

Similarly, we compute $$C_{12} = \text{ MMR}(A_{11}, B_{12}, C_{12}, 2), \\\ C_{21} = \text{ MMR}(A_{21}, B_{11}, C_{21}, 2), \\\ \ldots, \\\ C_{22} = \text{ MMR}(A_{22}, B_{22}, C_{22}, 2)$$

Computing $C_{11} = \text{ MMR}(A_{12}, B_{21}, C_{11}, 2)$, we have $$A_{\color{blue}{11}} = 1, A_{\color{blue}{12}} = 2, A_{\color{blue}{21}} = 2, A_{\color{blue}{22}} = 2 \\\ B_{\color{blue}{11}} = 9, B_{\color{blue}{12}} = 1, B_{\color{blue}{21}} = 2, B_{\color{blue}{22}} = 3$$ followed by $$C_{\color{blue}{11}} = 1 \cdot 9 + 2 \cdot 2 = 13 \\\ C_{\color{blue}{12}} = 1 \cdot 1 + 2 \cdot 3 = 7 \\\ C_{\color{blue}{21}} = 2 \cdot 9 + 2 \cdot 2 = 22 \\\ C_{\color{blue}{22}} = 2 \cdot 1 + 2 \cdot 3 = 8$$ which give us $C_{11} = \text{ MMR}(A_{12}, B_{21}, C_{11}, 2) = \begin{pmatrix}13 & 7\\\ 22 & 8\end{pmatrix}$.

Applying the matrix multiplication rule again, the sum $$\color{green}{\text{MMR}(A_{11}, B_{11}, C_{11}, 2) + \text{ MMR}(A_{12}, B_{21}, C_{11}, 2)} \\\ = \begin{pmatrix}7 & 10\\\ 24 & 38\end{pmatrix} + \begin{pmatrix}13 & 7\\\ 22 & 8\end{pmatrix} \\\ = \begin{pmatrix}20 & 17\\\ 46 & 46\end{pmatrix}$$

fills in the first quarter of the resultant matrix $A \cdot B = C = \begin{pmatrix}20 & 17 & x & x \\\ 46 & 46 & x & x \\\ x & x & x & x \\\ x & x & x & x\end{pmatrix}$. We fill in the rest of $C$ in a similar manner.

My question has to do with the part in $\color{green}{\text{green}}$ above. Where in the algorithm $\text{MMR}$ above does the highlighted $\color{green}{\text{green}}$ part occur? I added the part in $\color{green}{\text{green}}$ because addition like that is part of a matrix multiplication process.

edit: If it's any help the given algorithm occurs on p 128 of "Introduction To Algorithms"(4th ed) by Cormen, Leiserson, Rivest, Stein.