4.1 Multiplying square matrices

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

4.1-1

Generalize MATRIX-MULTIPLY-RECURSIVE to multiple $n\times n$ matrices for which $n$ is not necessarily an exact power of 2. Give a recurrence describing its running time. Argue that it runs in $\Theta(n^3)$ time in the worst case.

MATRIX_MULTIPLY_RECURSIVE_GENERALIZE(A,B,C,n)
    if n is not exact power of 2
        new_n = next power of 2 of n//O(n)
    use 0 to extend A B C into new_n*new_n matrix//O(n^2)
        MATRIX_MULTIPLY_RECURSIVE(A,B,C,new_n)//Theta(n^3)
    choose the n*n part of C as result by index method//O(1)
    return 

running time = $\Theta(n^3)+O(n^2)+O(1)+O(n)=\Theta(n^3)$

4.1-2

How quickly can you multiply a $kn\times n$ matrix (kn rows and n columns) by an $n\times kn$ matrix, where $k\geq 1$ , using MATRIX-MULTIPLY-RECURSIVE as a subtoutine? Answer the same question for multiplying an $n\times kn$ matrix by a $kn\times n$ matrix. Which is asymptotically faster, and by how much?

• mulyiplying a $kn\times n$ matrix by an $n\times kn$ matrix needs $k^2$ times' call of MATRIX-MULTIPLY-RECURSIVE(A,B,C,n), taking $\Theta(k^2n^3)$ in total.
• mulyiple a $n\times kn$ matrix by an $kn\times n$ matrix needs $k$ times' call of MATRIX-MULTIPLY-RECURSIVE(A,B,C,n), and need $k-1$ times' addition, taking $\Theta(kn^3+kn^2)=\Theta(kn^3)$ in total.
• The latter is asympototicallt faster.

4.1-3

Suppose that instead of partitioning matrices by index calculation in MATRIX-MULTIPLY-RECURSIVE, you copy the appropriate elements of A,B,and C into separate $n/2\times n/2$ submarices $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. After the recursive calls, you copy the results from $C_{11},C_{12},C_{21}$, and $C_{22}$ back into the appropriate places in $C$. How does recurrence (4.9) change, and what is its solution?

$T(n)=8T(n/2)+\Theta(n^2)$

According to the master theorem, $T(n)=\Theta(n^3)$

4.1-4

Write pseudocode for a divide-and-conquer algorithm MATRIX-ADD-RECURSIVE that sums two $n\times n$ matrices $A$ and $B$ by partitioning each of them into four $n/2\times n/2$ submatrices and then recursively summing corresponding pairs of submatrices. Assume that matrix partitioning uses $\Theta(1)$-time index calculations. Write a recurrence for the worst-case running time of MATRIX-ADD-RECURSIVEE, and solve your recurrence. What happens if you use $\Theta(n^2)$-time copying to implement the partitioning instead of index calculations?

MATRIX_ADD_RECURSIVEE(A,B,C,n)
    if n==1
        c11=a11+b11
    partition A,B,C into n/2*n/2 submatrixs
        A11,A12,A21,A22;B11,B12,B21,B22;and C11,C12,C21,C22; 
    MATRIX_ADD_RECURSIVEE(A11,B11,C11,n/2)
    MATRIX_ADD_RECURSIVEE(A12,B12,C12,n/2)
    MATRIX_ADD_RECURSIVEE(A21,B21,C21,n/2)
    MATRIX_ADD_RECURSIVEE(A22,B22,C22,n/2)

$T(n)=4T(n/2)+\Theta(1)$

According to master theorem, $T(n)=\Theta(n^2)$

if use copying,$T(n)=4T(n/2)+\Theta(n^2)\implies T(n)=\Theta(n^2\lg n)$