Strassen's Matrix Multiplication Algorithm (no example)

1. Problem

- 두 개의 n*n 행렬의 곱을 해보자. 여기서 n은 2의 거듭제곱이다.

- 슈트라센은 행렬을 4개로 나눠서 계산하는 방식을 택했다.

 

2. Input

1) 행렬의 길이 n

2) n*n 행렬 A
3) n*n 행렬 B

 

3. Output

1) A와 B의 곱이 담긴 행렬 C

 

4. PseudoCode

void strassen(int n, matrix A, matrix B, matrix C){
    if(n<=threshold)
        compute C = A * B using the standard algorithm;
    else{
        partition A into 4 submatrices A11, A12, A21, A22;
        partition B into 4 submatrices B11, B12, B21, B22;
        compute C = A * B using the standard algorithm;
        // example recursive call
        // strassen(n/2, A11+A22, B11+B22, M1);
    }
}