Matrix Product Algorithm   행렬 곱셈 알고리즘

1. 행렬 곱셈 알고리즘

  ㅇ 수학적 표현
      
[# C = AB = \begin{bmatrix}
                  a_{11} & a_{12} & \cdots & a_{1m} \\
                  a_{21} & a_{22} & \cdots & a_{2m} \\
                  \vdots & \vdots & \ddots & \vdots \\
                  a_{n1} & a_{n2} & \cdots & a_{nm}
                  \end{bmatrix}
                  \begin{bmatrix}
                  b_{11} & b_{12} & \cdots & b_{1p} \\
                  b_{21} & b_{22} & \cdots & b_{2p} \\
                  \vdots & \vdots & \ddots & \vdots \\
                  b_{m1} & b_{m2} & \cdots & b_{mp}
                  \end{bmatrix} 
                = \begin{bmatrix}
                  c_{11} & c_{12} & \cdots & c_{1p} \\
                  c_{21} & c_{22} & \cdots & c_{2p} \\
                  \vdots & \vdots & \ddots & \vdots \\
                  c_{n1} & c_{n2} & \cdots & c_{np}
                  \end{bmatrix} #]
       
[# \begin{matrix} A & B & = & C \\
                          (n \times m) & (m \times p) & & (n \times p) \end{matrix} #]
     - (A의 열의 수 m = B의 행의 수 m) 

  ㅇ 연산 수
       
[# c_{ij} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{im}b_{mj}
                 = \sum_{k=1}^m a_{ik}b_{kj} #]
     - C의 원소 수  :  n x p
     - C의 원소 마다 내부 연산 수
        . 곱셈 수  :  m번  (aik·bkj)
        . 덧셈 수  :  (m - 1)번  (m개를 더하므로)
     - 전체 연산 수
        . 전체 곱셈 수  :  n·p·m
        . 전체 덧셈 수  :  n·p·(m−1)

  ㅇ 계산 복잡도
     - 두 행렬  :  A ∈ Rn×m, B ∈ Rm×p
     - 행렬 곱셈  :  C = AB ∈ Rn×p
     - 각 원소  :  {#C_{ij} = \sum_{k=1}^{m} A_{ik} B_{kj}#}
     - 연산 수  
        . 곱셈 수  :  n·p·m
        . 덧셈 수  :  n·p·(m−1)
     - 시간 복잡도
        . 일반 행렬 (n×m)(m×p)  :  O(nmp)
        . 정방행렬 (n×n)  :  O(n3)

  ㅇ 정방행렬 곱셈의 경우, 단순하게 알고리즘으로 표현하면,
      
Input   : int n, A[n,n], B[n,n]
Ouptput : C[n,n]

void matrix_multiplication (n, A[,], B[,], C[,]) {
    int i, j, k
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            C[i,j] = 0;
            for (k = 1; k <= n; k++)
                C[i,j] = C[i,j] + A[i,k] * B[k,j];
        }
    }
}


2. 효율적 행렬곱셈 알고리즘 例)

  ㅇ 1969년 독일 수학자 폴커 스트라센(Volker Strassen)
     - 분할정복법에 기반하여 효율적인 행렬곱셈 알고리즘을 만듬
        . 시간 복잡도  :  O(n2.81)