스트라센 행렬 곱셈 알고리즘이란?
스트라센(Strassen) 알고리즘은 분할 정복(Divide and Conquer) 기법에 기반한 행렬 곱셈 알고리즘입니다. 이 알고리즘은 크기가 같은 두 행렬을 곱하는 데 사용되며, 기존의 일반적인 행렬 곱셈(O(n³))보다 적은 곱셈 연산으로 결과를 얻을 수 있어 효율적입니다.
두 행렬의 일반적인 곱셈 과정은 다음과 같습니다.
스트라센 알고리즘은 곱셈 과정을 단순화하여 연산 오버헤드를 크게 줄여줍니다. 스트라센 알고리즘을 적용하면 다음과 같이 계산할 수 있습니다.
스트라센 공식 (M1 ~ M7)
M1 = a × (f − h)
M2 = (a + b) × h
M3 = (c + d) × e
M4 = d × (g − e)
M5 = (a + d) × (e + h)
M6 = (b − d) × (g + h)
M7 = (a − c) × (e + f)
공식을 쉽게 암기하는 6가지 규칙
위 공식들은 몇 가지 규칙만 기억하면 쉽게 암기할 수 있으며, 이를 바탕으로 알고리즘 코드도 자연스럽게 작성할 수 있습니다. 먼저 다음 6가지를 기억해 두세요.
- AHED 활용: M의 처음 네 값(M1~M4)은 'AHED'라는 키워드로 기억합니다.
- 대각선 곱셈: 다섯 번째 값(M5)은 대각선 요소끼리의 곱셈으로 구합니다.
- 마지막 CR: 여섯 번째 값(M6)은 마지막 CR, 즉 행렬 1의 마지막 열(Column)과 행렬 2의 마지막 행(Row)을 사용합니다.
- 첫 번째 CR: 일곱 번째 값(M7)은 첫 번째 CR, 즉 행렬 1의 첫 번째 열과 행렬 2의 첫 번째 행을 사용합니다.
- 행은 더하고, 열은 뺀다: 행(Row)의 요소를 다룰 때는 더하고, 열(Column)의 경우에는 뺍니다.
- 인접 값으로 갱신: 마지막으로 인접한 값들을 이용해 결과를 갱신합니다.
이러한 규칙들을 활용하면 스트라센 알고리즘의 복잡해 보이는 공식들도 손쉽게 기억하고, 실제 코드 구현 시에도 빠르게 떠올릴 수 있습니다.