logo

슈트라센 알고리즘 증명 📂행렬대수

슈트라센 알고리즘 증명

알고리즘

k∈Nk \in \mathbb{N} 에 대해 n=2kn=2^{k} 이라고 하자. A,B∈Rn×nA, B \in \mathbb{R}^{n \times n} 에 대해 조던 블록 행렬 표현을 사용해 다음과 같은 8개의 n2×n2{{n} \over {2}} \times {{n} \over {2}} 행렬 AiA_{i}, BiB_{i} 들을 생각해보자. AB=[A1A2A3A4][B1B2B3B4]=[C1C2C3C4]=C AB= \begin{bmatrix} A_{1} & A_{2} \\ A_{3} & A_{4} \end{bmatrix} \begin{bmatrix} B_{1} & B_{2} \\ B_{3} & B_{4} \end{bmatrix} = \begin{bmatrix} C_{1} & C_{2} \\ C_{3} & C_{4} \end{bmatrix} = C C=ABC = AB 를 구하기 위해 다음을 계산한다. P1=A1(B2−B4)P2=(A1+A2)B4P3=(A3+A4)B1P4=A4(B3−B1)P5=(A1+A4)(B1+B4)P6=(A2−A4)(B3+B4)P7=(A3−A1)(B1+B2) P_{1} = A_{1} ( B_{2} - B_{4} ) \\ P_{2} = ( A_{1} + A_{2} ) B_{4} \\ P_{3} = ( A_{3} + A_{4} ) B_{1} \\ P_{4} = A_{4} ( B_{3} - B_{1} ) \\ P_{5} = (A_{1} + A_{4}) ( B_{1} + B_{4} ) \\ P_{6} = (A_{2} - A_{4}) ( B_{3} + B_{4} ) \\ P_{7} = (A_{3} - A_{1}) ( B_{1} + B_{2} )

C1=−P2+P4+P5+P6C2=P1+P2C3=P3+P4C4=P1−P3+P5+P7 C_{1} = -P_{2} + P_{4}+ P_{5} + P_{6} \\ C_{2} = P_{1} + P_{2} \\ C_{3} = P_{3} + P_{4} \\ C_{4} = P_{1} - P_{3} + P_{5} + P_{7} AiBjA_{i} B_{j} 를 계산할 때도 같은 방법을 반복하면 그 시간복잡도는 Θ(n2.807)\Theta ( n^{2.807} ) 이다.

  • 물론 n≠2kn \ne 2^{k} 라고 해서 쓸 수 없는 것은 아니고, 사이즈를 조정해서 그대로 적용시켜도 된다.

설명

상식적이고 곧바로 떠올릴 수 있는 행렬의 곱셈은 C1=A1B1+A2B3C2=A1B2+A2B4C3=A3B1+A4B3C4=A3B2+A4B4 C_{1} = A_{1}B_{1} + A_{2} B_{3} \\ C_{2} = A_{1}B_{2} + A_{2} B_{4} \\ C_{3} = A_{3}B_{1} + A_{4} B_{3} \\ C_{4} = A_{3}B_{2} + A_{4} B_{4} 이 계산을 계속 반복하면 되는데, 여기에 걸리는 시간이 Θ(n3)\Theta ( n^3 ) 라는 것은 의심의 여지가 없었다. 슈트라센이 태어나기 전까진 말이다.

이 알고리즘은 아주 아주 획기적인데, 본디 한 개의 CiC_{i} 을 계산하는데는 반드시 두 번의 행렬 곱셈이 필요하기 때문이다. 합쳐서 한번 계산할 때마다 8번을 계산해야하는데, 슈트라센은 이것을 7번으로 줄였다. 저 방법 외에 달리 방법이 있을까 고민한 것부터가 비범한 센스고, 정말 찾아낸 것은 불가사의하다고까지 말할 수 있을 정도다. 이 알고리즘의 개발로 인해서 행렬 계산에 쓰였을 자원들을 조금이나마, 아니 엄청나게 많이 아낄 수 있다.

증명

Part 1. 계산가능성

그냥 직접 계산해보는 수밖에 없다.

Part 1-1. C1=A1B1+A2B3C_{1} = A_{1}B_{1} + A_{2} B_{3}

C1=−P2+P4+P5+P6=(−A1B4−A2B4)+P4+(A1B1+A1B4+A4B1+A4B4)+P6=−A2B4+(A4B3−A4B1)+A1B1+A4B1+A4B4+P6=−A2B4+A4B3+A1B1+A4B4+(A2B3+A2A4−A4B3−A4B4)=A1B1+A2B3 \begin{align*} C_{1} =& -P_{2} + P_{4} + P_{5} + P_{6} \\ =& ( {\color{red}- A_{1} B_{4}} - A_{2} B_{4} ) + P_{4} + ( A_{1}B_{1} + {\color{red} A_{1}B_{4} } + A_{4} B_{1} + A_{4}B_{4} ) + P_{6} \\ =& - A_{2} B_{4} + (A_{4} B_{3} {\color{red}- A_{4} B_{1} }) + A_{1}B_{1} + {\color{red} A_{4} B_{1} } + A_{4}B_{4} + P_{6} \\ =& {\color{red} - A_{2} B_{4} } + \color{blue}{A_{4} B_{3} } + A_{1}B_{1} + \color{green}{A_{4}B_{4}} + ( A_{2} B_{3} + {\color{red} A_{2} A_{4} } \color{blue}{ - A_{4} B_{3} }- \color{green}{A_{4} B_{4}}) \\ =& A_{1}B_{1} + A_{2} B_{3} \end{align*}

Part 1-2. C2=A1B2+A2B4C_{2} = A_{1}B_{2} + A_{2} B_{4}

C2=P1+P2=(A1B2−A1B4)+(A1B4+A2B4)=A1B2+A2B4 \begin{align*} C_{2} =& P_{1} + P_{2} \\ =& (A_{1}B_{2} {\color{red}- A_{1} B_{4}}) + ( {\color{red}A_{1} B_{4}} + A_{2} B_{4}) \\ =& A_{1}B_{2} + A_{2} B_{4} \end{align*}

Part 1-3. C3=A3B1+A4B3C_{3} = A_{3}B_{1} + A_{4} B_{3}

C3=P3+P4=(A3B1+A4B1)+(A4B3−A4B1)=A3B1+A4B3 \begin{align*} C_{3} =& P_{3} + P_{4} \\ =& (A_{3}B_{1} + {\color{red} A_{4}B_{1}}) + (A_{4}B_{3} {\color{red}- A_{4}B_{1}}) \\ =& A_{3}B_{1} + A_{4} B_{3} \end{align*}

Part 1-4. C4=A3B2+A4B4C_{4} = A_{3}B_{2} + A_{4} B_{4}

C4=P1−P3+P5+P7=(A1B2−A1B4)−P3+(A1B1+A1B4+A4B1+A4B4)+P7=A1B2+(−A3B1−A4B1)+A1B1+A4B1+A4B4+P7=A1B2−A3B1+A1B1+A4B4+(A3B1+A3B2−A1B1−A1B2)=A3B2+A4B4 \begin{align*} C_{4} =& P_{1} - P_{3} + P_{5} + P_{7} \\ =& (A_{1}B_{2} {\color{red} - A_{1} B_{4} } ) - P_{3} + ( A_{1}B_{1} + {\color{red} A_{1}B_{4} } + A_{4}B_{1} + A_{4}B_{4}) + P_{7} \\ =& A_{1}B_{2} + (- A_{3}B_{1} - {\color{red}A_{4}B_{1}}) + A_{1}B_{1} + {\color{red}A_{4}B_{1}} + A_{4}B_{4} + P_{7} \\ =& {\color{red} A_{1}B_{2}} - \color{blue}{A_{3}B_{1}} + \color{green}{A_{1}B_{1}}+ A_{4}B_{4} + ( \color{blue}{A_{3}B_{1}} + A_{3}B_{2} - \color{green}{A_{1}B_{1}} {\color{red}- A_{1}B_{2}}) \\ =& A_{3}B_{2} + A_{4} B_{4} \end{align*}

Part 2. 시간복잡도

본질적으로 원래의 계산법이 Θ(n3)\Theta ( n^3 ) 이라는 것을 증명한 방법과 같다. 한번 계산하는데 걸리는 시간이 T(n)T(n) 이고 반복 외의 수행시간을 cc 라고 하면 T(n)=7T(n2)+c\displaystyle T(n) = 7 T \left( {{n} \over {2}} \right) + c 이므로

T(n)=7T(n2)+c=7[7T(n4)+c]+c=7[49T(n8)+7c+c]+c=73T(n8)+(1+7+72)c=73T(n8)+73−17−1c⋮≈7log⁡2n(T(1)+c)=nlog⁡27(T(1)+c)=n2.807(T(1)+c)=Θ(n2.807) \begin{align*} T(n) =& 7 T \left( {{n} \over {2}} \right) + c \\ =& 7 \left[ 7 T \left( {{n} \over {4}} \right) + c \right] + c \\ =& 7 \left[ 49 T \left( {{n} \over {8}} \right) + 7 c + c \right] + c \\ =& 7^3 T \left( {{n} \over {8}} \right) + (1+7+7^2)c \\ =& 7^3 T \left( {{n} \over {8}} \right) + {{7^3 - 1} \over {7 - 1}}c \\ & \vdots & \\ \approx& 7^{\log_{2} n} ( T(1) + c ) \\ =& n^{\log_{2} 7} ( T(1) + c ) \\ =& n^{2.807} ( T(1) + c ) \\ =& \Theta \left( n^{2.807} \right) \end{align*}

■