슈트라센 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
3. 알고리즘
- 3.1. 슈트라센 알고리즘
- 3.2. 위노그라드 알고리즘
4. 개선된 알고리즘
- 4.1. 빅터 판의 알고리즘
- 4.2. 코퍼스미스-위노그라드 알고리즘
5. 점근적 복잡도
- 5.1. 계수 (Bilinear Complexity)
6. 캐시 동작
7. 구현 고려 사항
8. 관련 자료
참조

1. 개요

슈트라센 알고리즘은 1969년 볼커 슈트라센이 개발한 행렬 곱셈 알고리즘으로, 일반적인 행렬 곱셈 알고리즘보다 더 적은 연산 횟수로 계산할 수 있다. 이 알고리즘은 분할 정복 방식을 사용하여 2x2 행렬 곱셈을 7번의 곱셈으로 수행하며, 이를 재귀적으로 적용하여 시간 복잡도를 O(n^2.807)로 줄인다. 슈트라센 알고리즘은 수치적 안정성이 떨어지고 추가 메모리를 필요로 하지만, 특정 크기 이상의 행렬에 대해서는 기존의 행렬 곱셈보다 효율적이다. 위노그라드 알고리즘과 같은 개선된 알고리즘과 빅터 판, 코퍼스미스-위노그라드 알고리즘과 같은 더 발전된 알고리즘도 존재한다.

더 읽어볼만한 페이지

수치해석학 - 수학적 최적화
수학적 최적화는 주어진 집합에서 실수 또는 정수 변수를 갖는 함수의 최댓값이나 최솟값을 찾는 문제로, 변수 종류, 제약 조건, 목적 함수 개수에 따라 다양한 분야로 나뉘며 여러 학문 분야에서 활용된다.
수치해석학 - 선형대수학
선형대수학은 벡터, 벡터 공간, 행렬 등의 개념으로 선형 방정식과 선형 변환을 연구하는 수학 분야로, 선형성을 활용해 행렬로 표현 및 계산하며, 연립일차방정식 해법, 고유값/고유벡터를 통한 행렬 분석, 벡터 공간의 기저와 차원 등을 다루고 물리학, 공학, 컴퓨터 과학 등 다양한 분야에 응용된다.

슈트라센 알고리즘
개요
이름	슈트라센 알고리즘
분야	선형대수학, 알고리즘
문제	행렬 곱셈
발명가	폴커 슈트라센
발표 년도	1969년
시간 복잡도	O(n^2.8074)
공간 복잡도	O(n^2)
상세 정보
설명	슈트라센 알고리즘은 행렬 곱셈을 수행하는 알고리즘이다.
기존 알고리즘과의 비교	기존의 기본적인 행렬 곱셈 알고리즘의 시간 복잡도는 O(n^3)이다. 슈트라센 알고리즘은 이를 개선하여 O(n^2.8074)의 시간 복잡도를 가진다.
작동 방식	2x2 행렬 곱셈을 7번의 곱셈 연산으로 수행하도록 변환한다. 이 방식을 재귀적으로 적용하여 더 큰 행렬의 곱셈을 수행한다.
복잡도	시간 복잡도: O(n^log2(7)) ≈ O(n^2.8074) 공간 복잡도: O(n^2)
장점	큰 행렬의 곱셈에서 기존 알고리즘보다 더 빠르다.
단점	작은 행렬의 곱셈에서는 오버헤드가 발생하여 오히려 느릴 수 있다. 수치적 안정성이 떨어진다는 단점이 있다.
추가 정보
활용 분야	컴퓨터 그래픽스 신호 처리 과학 계산
관련 알고리즘	쿠퍼스미스-위노그라드 알고리즘 (Coppersmith–Winograd algorithm) 갤러거 알고리즘

2. 역사

볼커 슈트라센은 1969년에 이 알고리즘을 처음 발표했고, 이를 통해 $n^3$ 일반 행렬 곱셈 알고리즘이 최적이 아님을 증명했다.^[1] 슈트라센 알고리즘의 발표는 행렬 곱셈에 대한 더 많은 연구로 이어져 점근적으로 더 낮은 경계와 향상된 계산 상한을 이끌어냈다.

3. 알고리즘

슈트라센 알고리즘은 일반적인 행렬 곱셈보다 더 적은 곱셈 횟수로 행렬 곱을 계산하는 알고리즘이다. 핵심 아이디어는 2x2 블록 행렬로 분할된 행렬의 곱셈에서 곱셈 횟수를 8번에서 7번으로 줄이는 것이다.

이 과정에서 곱셈은 7번 수행되지만, 덧셈/뺄셈은 18번 수행된다. 큰 행렬에서는 곱셈 연산이 덧셈/뺄셈 연산보다 시간이 오래 걸리므로, 전체적인 연산 시간은 줄어들게 된다. 이 과정을 재귀적으로 반복하면, 최종적인 시간 복잡도는 약 O(n^2.807)이 된다.

하지만, 슈트라센 알고리즘은 작은 크기의 행렬에 대해서는 일반적인 행렬 곱셈보다 느릴 수 있다. 따라서 실제 구현에서는 일정 크기 이하의 행렬에 대해서는 일반적인 행렬 곱셈을 사용한다. 또한, 슈트라센 알고리즘은 수치 안정성이 떨어져 일반적인 행렬 곱셈보다 오차가 더 클 수 있다는 점을 유의해야 한다.^[14]

3. 1. 슈트라센 알고리즘

'''A'''와 '''B'''를 체 ''F''에 대한 정사각행렬이라고 할 때, 두 행렬의 곱 ''C''는 다음과 같이 정의된다.

:

\mathbf{C} = \mathbf{A} \mathbf{B} \qquad \mathbf{A},\mathbf{B},\mathbf{C} \in F^{2^n \times 2^n}

만약 ''A''와 ''B''가 2ⁿ × 2ⁿ 꼴의 크기가 아니라면, 먼저 모자라는 행과 열을 0으로 채워서 크기를 맞춘다. 이를 패딩(padding)이라고 한다. 행렬 곱셈이 끝난 뒤에는 행렬에서 필요한 부분만 다시 잘라 내면 된다.

이제 ''A'', ''B'', ''C''를 같은 크기의 정사각행렬 네 개로 나눈다. 이를 블록 행렬이라고 한다.

:

\mathbf{A} =\begin{bmatrix}\mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\\mathbf{A}_{2,1} & \mathbf{A}_{2,2}\end{bmatrix}\mbox { , }\mathbf{B} =\begin{bmatrix}\mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\\mathbf{B}_{2,1} & \mathbf{B}_{2,2}\end{bmatrix}\mbox { , }\mathbf{C} =\begin{bmatrix}\mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\\mathbf{C}_{2,1} & \mathbf{C}_{2,2}\end{bmatrix}

이 때,

:

\mathbf{A}_{i,j}, \mathbf{B}_{i,j}, \mathbf{C}_{i,j} \in F^{2^{n-1} \times 2^{n-1}}

그러면 다음과 같은 식이 성립한다.

:

\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1}

:

\mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2}

:

\mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1}

:

\mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2}

이 방식은 여전히 여덟 번의 곱셈과 네 번의 덧셈이 필요하여 연산 횟수를 줄이지 못한다.

슈트라센 알고리즘은 여기서 다음과 같은 새로운 행렬을 정의한다.

:

\mathbf{M}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})

:

\mathbf{M}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}

:

\mathbf{M}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})

:

\mathbf{M}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})

:

\mathbf{M}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}

:

\mathbf{M}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})

:

\mathbf{M}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})

이 ''M_k'' 행렬들을 이용하여 ''C_i,j'' 행렬을 다음과 같이 표현할 수 있다.

:

\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}

:

\mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}

:

\mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}

:

\mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}

이 과정에서는 7번의 곱셈과 18번의 덧셈/뺄셈으로 ''C''를 계산할 수 있다. 큰 행렬에 대해서는 행렬의 곱셈이 덧셈보다 더 많은 시간을 필요로 하므로, 덧셈을 더 하는 대신 곱셈을 덜 하는 것이 전체적으로 더 효율적이다.

이 과정을 재귀적으로 반복하면 총

7 \cdot n^{\log_2 7} - 6 \cdot n^2

번의 연산이 필요하다.

\log_2 7 = 2.807\cdots

이므로 전체 수행 시간은 약 O(n^2.807)이다. 다만, ''n''이 작을 경우에는 일반적인 행렬 곱셈이 더 빠를 수 있으므로, 작은 ''n''에 대해서는 일반적인 방법으로 곱셈을 하도록 구현하는 것이 일반적이다.

슈트라센 알고리즘은 속도가 빠른 대신 수치 안정성이 떨어진다는 단점이 있다. 일반적인 행렬 곱셈보다 오차가 더 클 수 있다.^[14]

3. 2. 위노그라드 알고리즘

1980년에 슈무엘 위노그라드가 개발한 알고리즘으로, 슈트라센 알고리즘을 변형한 것이다. 점근적 복잡도는 슈트라센 알고리즘과 동일하지만, 덧셈 횟수를 15번으로 줄였다. 위노그라드 알고리즘에서 사용되는 변수는 다음과 같다.

변수	식
$\mathbf{S}_1$	$\mathbf{A}_{21} + \mathbf{A}_{22}$
$\mathbf{S}_2$	$\mathbf{S}_1 - \mathbf{A}_{11}$
$\mathbf{S}_3$	$\mathbf{B}_{12} - \mathbf{B}_{11}$
$\mathbf{S}_4$	$\mathbf{B}_{22} - \mathbf{S}_3$
$\mathbf{M}_1$	$\mathbf{S}_2 \mathbf{S}_4$
$\mathbf{M}_2$	$\mathbf{A}_{11} \mathbf{B}_{11}$
$\mathbf{M}_3$	$\mathbf{A}_{12} \mathbf{B}_{21}$
$\mathbf{M}_4$	$(\mathbf{A}_{11} - \mathbf{A}_{21}) (\mathbf{B}_{22} - \mathbf{B}_{12})$
$\mathbf{M}_5$	$\mathbf{S}_1 \mathbf{S}_3$
$\mathbf{M}_6$	$(\mathbf{A}_{12} - \mathbf{S}_2) \mathbf{B}_{22}$
$\mathbf{M}_7$	$\mathbf{A}_{22} (\mathbf{S}_4 - \mathbf{B}_{21})$
$\mathbf{T}_1$	$\mathbf{M}_1 + \mathbf{M}_2$
$\mathbf{T}_2$	$\mathbf{T}_1 + \mathbf{M}_4$

이 때 행렬 곱셈의 결과는 다음과 같이 계산된다.

: $\mathbf{C}_{11} = \mathbf{M}_2 + \mathbf{M}_3$

: $\mathbf{C}_{12} = \mathbf{T}_1 + \mathbf{M}_5 + \mathbf{M}_6$

: $\mathbf{C}_{21} = \mathbf{T}_2 - \mathbf{M}_7$

: $\mathbf{C}_{22} = \mathbf{T}_2 + \mathbf{M}_5$

4. 개선된 알고리즘

슈무엘 위노그라드는 1980년에 슈트라센 알고리즘을 변형한 '''위노그라드 알고리즘'''을 개발하였다. 이 알고리즘은 점근적으로 슈트라센 알고리즘과 동일한 복잡도를 가지지만, 행렬 덧셈 횟수를 18회에서 15회로 줄였다.^[3] 위노그라드 알고리즘에서 사용하는 변수 및 행렬 곱셈 결과는 다음과 같다.

$\mathbf{S}_1 = \mathbf{A}_{21} + \mathbf{A}_{22}$	$\mathbf{S}_2 = \mathbf{S}_1 - \mathbf{A}_{11}$
$\mathbf{S}_3 = \mathbf{B}_{12} - \mathbf{B}_{11}$	$\mathbf{S}_4 = \mathbf{B}_{22} - \mathbf{S}_3$
$\mathbf{M}_1 = \mathbf{S}_2 \mathbf{S}_4$	$\mathbf{M}_2 = \mathbf{A}_{11} \mathbf{B}_{11}$
$\mathbf{M}_3 = \mathbf{A}_{12} \mathbf{B}_{21}$	$\mathbf{M}_4 = (\mathbf{A}_{11} - \mathbf{A}_{21}) (\mathbf{B}_{22} - \mathbf{B}_{12})$
$\mathbf{M}_5 = \mathbf{S}_1 \mathbf{S}_3$	$\mathbf{M}_6 = (\mathbf{A}_{12} - \mathbf{S}_2) \mathbf{B}_{22}$
$\mathbf{M}_7 = \mathbf{A}_{22} (\mathbf{S}_4 - \mathbf{B}_{21})$
$\mathbf{T}_1 = \mathbf{M}_1 + \mathbf{M}_2$	$\mathbf{T}_2 = \mathbf{T}_1 + \mathbf{M}_4$

: $\mathbf{C}_{11} = \mathbf{M}_2 + \mathbf{M}_3$

: $\mathbf{C}_{12} = \mathbf{T}_1 + \mathbf{M}_5 + \mathbf{M}_6$

: $\mathbf{C}_{21} = \mathbf{T}_2 - \mathbf{M}_7$

: $\mathbf{C}_{22} = \mathbf{T}_2 + \mathbf{M}_5$

1971년 위노그라드는 다음 형식을 사용하여 행렬 덧셈 횟수를 줄일 수 있음을 보였다.

$\begin{bmatrix}a & b \\c & d\end{bmatrix}\begin{bmatrix}A & C \\B & D\end{bmatrix}=\begin{bmatrix}t + b{\color{red}\times}B & w + v + (a + b - c - d){\color{red}\times}D \\w + u + d{\color{red}\times}(B + C - A - D) & w + u + v\end{bmatrix}$

여기서 $t = a{\color{red}\times}A, \; u = (c - a){\color{red}\times}(C - D), \; v = (c + d){\color{red}\times}(C - A), \; w = t + (c + d - a){\color{red}\times}(A + D - C)$ 이다.

이 알고리즘은 2017년에 단계별 행렬 덧셈 횟수를 12회로 줄이는 방식으로 더욱 최적화되었고,^[4] 2023년에도 다시 최적화되었다.^[5]

4. 1. 빅터 판의 알고리즘

빅터 판은 슈트라센 알고리즘에서 행렬을 더 잘게 나누어 O(n^2.795)의 시간 안에 행렬을 곱하는 방법을 개발했다. 그는 68×68 행렬은 132,464번, 70×70 행렬은 143,640번, 72×72 행렬은 155,424번의 곱셈으로 계산이 가능함을 보였다.

4. 2. 코퍼스미스-위노그라드 알고리즘

돈 코퍼스미스와 슈무엘 위노그라드는 1987년에 '''코퍼스미스-위노그라드 알고리즘'''(Coppersmith–Winograd algorithm)을 개발했다. 이 알고리즘은 슈트라센 알고리즘처럼 재귀적 발상에서 나온 것으로, 시간 복잡도는

O(n^{2.376})

이다. 2010년에 Stother가

O(n^{2.3737})

로 개선할 때까지 가장 빠른 알고리즘이었다. 이듬해 월리엄스가

O(n^{2.3727})

로 개선한 알고리즘이 현재까지 가장 빠른 알고리즘이다. 2005년에는 이 알고리즘을 군론적 구성을 사용해 유도한 논문이 발표되었다.

5. 점근적 복잡도

슈트라센 알고리즘은 일반적인 행렬 곱셈(8번의 곱셈과 4번의 덧셈)과 달리, 7번의 곱셈과 18번의 덧셈/뺄셈으로 행렬 곱셈을 수행한다. 이 과정을 재귀적으로 반복하면 총 연산 횟수는 $7 \cdot n^{\log_2 7} - 6 \cdot n^2$ 가 된다. $\log_2 7 \approx 2.807$ 이므로, 전체 수행 시간은 약 O(n^2.807)이다.

하지만 슈트라센 알고리즘은 수치 안정성이 떨어진다는 단점이 있으며, 실제 오차는 일반적인 행렬 곱셈보다 크다.^[14] 또한 초기 행렬의 크기를 2의 거듭제곱으로 맞추기 위해 0을 채우는 과정에서 단순 알고리즘보다 더 많은 메모리를 사용한다.

1969년에 처음 발표된 슈트라센 알고리즘은 $n^3$ 복잡도의 일반 행렬 곱셈 알고리즘이 최적이 아님을 증명했다.^[1] 이후 점근적으로 더 낮은 경계와 향상된 계산 상한을 가진 행렬 곱셈에 대한 연구가 활발히 진행되었다.

슈트라센 알고리즘은 "점근적으로" 더 빠르지만, 작은 크기의 행렬에서는 일반적인 행렬 곱셈이 더 효율적일 수 있다. 따라서 실제 구현에서는 일정 크기 이상의 행렬에만 슈트라센 알고리즘을 적용하고, 작은 행렬은 일반적인 방법으로 곱셈을 수행한다. 코퍼스미스-위노그라드 알고리즘과 같이 점근적으로 더 빠른 알고리즘도 있지만, 실제 사용에는 제약이 따르기도 한다.

5. 1. 계수 (Bilinear Complexity)

쌍선형 맵의 쌍선형 복잡도 또는 '''계수'''는 행렬 곱셈의 점근적 복잡도에서 중요한 개념이다. '''F''' 필드에 대한 쌍선형 맵

\phi:\mathbf A \times \mathbf B \rightarrow \mathbf C

의 계수는 다음과 같이 정의된다.^[7]

:

R(\phi/\mathbf F) = \min \left\{r\left|\exists f_i\in \mathbf A^*,g_i\in\mathbf B^*,w_i\in\mathbf C , \forall \mathbf a\in\mathbf A, \mathbf b\in\mathbf B, \phi(\mathbf a,\mathbf b) = \sum_{i=1}^r f_i(\mathbf a)g_i(\mathbf b)w_i \right.\right\}

다시 말해, 쌍선형 맵의 계수는 가장 짧은 쌍선형 계산의 길이이다.^[7] 슈트라센 알고리즘은

2 \times 2

행렬 곱셈의 계수가 7 이하임을 보여준다. 이를 확인하기 위해 이 알고리즘(표준 알고리즘과 함께)을 이러한 쌍선형 계산으로 표현하면 다음과 같다. 행렬의 경우, 쌍대 공간 '''A'''*와 '''B'''*는 스칼라 이중 점 곱에 의해 유도된 필드 '''F'''로의 맵으로 구성된다(즉, 이 경우 아다마르 곱의 모든 항목의 합).

표준 알고리즘				슈트라센 알고리즘
$i$	$f_i (\mathbf{a})$	$g_i (\mathbf{b})$	$w_i$		$f_i (\mathbf{a})$	$g_i (\mathbf{b})$	$w_i$
1	$\begin{bmatrix}1&0\\0&0\end{bmatrix}:\mathbf a$	$\begin{bmatrix}1&0\\0&0\end{bmatrix}:\mathbf b$	$\begin{bmatrix}1&0\\0&0\end{bmatrix}$	\|	$\begin{bmatrix}1&0\\0&1\end{bmatrix}:\mathbf a$	$\begin{bmatrix}1&0\\0&1\end{bmatrix}:\mathbf b$	$\begin{bmatrix}1&0\\0&1\end{bmatrix}$
2	$\begin{bmatrix}0&1\\0&0\end{bmatrix}:\mathbf a$	$\begin{bmatrix}0&0\\1&0\end{bmatrix}:\mathbf b$	$\begin{bmatrix}1&0\\0&0\end{bmatrix}$	\|	$\begin{bmatrix}0&0\\1&1\end{bmatrix}:\mathbf a$	$\begin{bmatrix}1&0\\0&0\end{bmatrix}:\mathbf b$	$\begin{bmatrix}0&0\\1&-1\end{bmatrix}$
3	$\begin{bmatrix}1&0\\0&0\end{bmatrix}:\mathbf a$	$\begin{bmatrix}0&1\\0&0\end{bmatrix}:\mathbf b$	$\begin{bmatrix}0&1\\0&0\end{bmatrix}$	\|	$\begin{bmatrix}1&0\\0&0\end{bmatrix}:\mathbf a$	$\begin{bmatrix}0&1\\0&-1\end{bmatrix}:\mathbf b$	$\begin{bmatrix}0&1\\0&1\end{bmatrix}$
4	$\begin{bmatrix}0&1\\0&0\end{bmatrix}:\mathbf a$	$\begin{bmatrix}0&0\\0&1\end{bmatrix}:\mathbf b$	$\begin{bmatrix}0&1\\0&0\end{bmatrix}$	\|	$\begin{bmatrix}0&0\\0&1\end{bmatrix}:\mathbf a$	$\begin{bmatrix}-1&0\\1&0\end{bmatrix}:\mathbf b$	$\begin{bmatrix}1&0\\1&0\end{bmatrix}$
5	$\begin{bmatrix}0&0\\1&0\end{bmatrix}:\mathbf a$	$\begin{bmatrix}1&0\\0&0\end{bmatrix}:\mathbf b$	$\begin{bmatrix}0&0\\1&0\end{bmatrix}$	\|	$\begin{bmatrix}1&1\\0&0\end{bmatrix}:\mathbf a$	$\begin{bmatrix}0&0\\0&1\end{bmatrix}:\mathbf b$	$\begin{bmatrix}-1&1\\0&0\end{bmatrix}$
6	$\begin{bmatrix}0&0\\0&1\end{bmatrix}:\mathbf a$	$\begin{bmatrix}0&0\\1&0\end{bmatrix}:\mathbf b$	$\begin{bmatrix}0&0\\1&0\end{bmatrix}$	\|	$\begin{bmatrix}-1&0\\1&0\end{bmatrix}:\mathbf a$	$\begin{bmatrix}1&1\\0&0\end{bmatrix}:\mathbf b$	$\begin{bmatrix}0&0\\0&1\end{bmatrix}$
7	$\begin{bmatrix}0&0\\1&0\end{bmatrix}:\mathbf a$	$\begin{bmatrix}0&1\\0&0\end{bmatrix}:\mathbf b$	$\begin{bmatrix}0&0\\0&1\end{bmatrix}$	\|	$\begin{bmatrix}0&1\\0&-1\end{bmatrix}:\mathbf a$	$\begin{bmatrix}0&0\\1&1\end{bmatrix}:\mathbf b$	$\begin{bmatrix}1&0\\0&0\end{bmatrix}$
8	$\begin{bmatrix}0&0\\0&1\end{bmatrix}:\mathbf a$	$\begin{bmatrix}0&0\\0&1\end{bmatrix}:\mathbf b$	$\begin{bmatrix}0&0\\0&1\end{bmatrix}$	colspan="3" \|
$\mathbf a\mathbf b = \sum_{i=1}^8 f_i(\mathbf a)g_i(\mathbf b)w_i$			$\mathbf a\mathbf b = \sum_{i=1}^7 f_i(\mathbf a)g_i(\mathbf b)w_i$

행렬 곱셈에 필요한 총 기본 곱셈 수 $L$ 은 계수 $R$ 에 점근적으로 밀접하게 묶여 있다. 즉, $L = \Theta(R)$ 이며, 더 구체적으로 $R / 2 \le L \le R$ 이다. 계수의 한 가지 유용한 속성은 텐서 곱에 대해 곱셈 가능성이 있다는 것이며, 이를 통해 모든 $n$ 에 대해 $2^n \times 2^n \times 2^n$ 행렬 곱셈을 $7^n$ 개 이하의 기본 곱셈으로 수행할 수 있다. (이 $2 \times 2 \times 2$ 행렬 곱셈 맵의 $n$ 겹 텐서 곱, 즉 $n$ 번째 텐서 거듭제곱은 알고리즘의 재귀적 단계에 의해 실현된다.)

6. 캐시 동작

슈트라센 알고리즘은 캐시를 고려하지 않는 알고리즘이다. 이상적인 크기 $M$ 의 캐시 (즉, 길이 $b$ 인 $M / b$ 개의 라인을 가짐)를 가정할 때, 이 알고리즘의 캐시 동작 분석에 따르면 다음과 같은 수의 캐시 미스가 발생한다.^[8]

: $\Theta \left(1 + \frac{n^2}{b} + \frac{n^{\log_2 7}}{b\sqrt{M}} \right)$

7. 구현 고려 사항

슈트라센 알고리즘은 행렬의 크기가 2의 거듭제곱이 아니거나 정사각 행렬이 아닌 경우에도 적용할 수 있다.^[9] 하지만, 실제 구현에서는 다음과 같은 사항들을 고려해야 한다.

패딩의 최적화: 행렬의 크기가 2의 거듭제곱이 아닐 때 0으로 채우는(패딩) 방식은 계산 시간을 늘릴 수 있다. 따라서, 패딩을 최소화하고 필요한 부분만 계산하는 효율적인 구현이 필요하다.^[10] 예를 들어, 1600 x 1600 행렬은 2048 x 2048로 패딩하는 대신 25 x 25 행렬로 분할하여 기존 곱셈을 사용할 수 있다.
임의의 차원: 임의의 차원을 가진 정방 행렬에 대해서도 슈트라센 알고리즘을 적용할 수 있다.^[10] 차원이 홀수인 경우, 먼저 한 행과 한 열을 0으로 패딩한다. 이 패딩은 즉석에서 게으르게 적용될 수 있으며, 결과가 형성될 때 추가 행과 열은 폐기된다.
비정방 행렬: 비정방 행렬의 경우에도 슈트라센 알고리즘을 적용할 수 있다. 행렬이 충분히 비정방 행렬이면, 간단한 방법을 사용하여 초기 연산을 더 정방형 곱으로 줄이는 것이 좋다.
크기가 $[2N \times N] \ast [N \times 10N]$ 인 곱은 20개의 $[N \times N] \ast [N \times N]$ 연산으로 수행할 수 있다.
크기가 $[N \times 10N] \ast [10N \times N]$ 인 곱은 10개의 $[N \times N] \ast [N \times N]$ 연산으로 수행할 수 있다.
기존 곱셈과의 비교: 슈트라센 알고리즘은 작은 크기의 행렬에 대해서는 기존 곱셈보다 비효율적일 수 있다. 따라서, 특정 크기 이하에서는 기존 곱셈을 사용하는 것이 좋다. 이 교차점은 구현 및 하드웨어에 따라 다르지만, 최근 연구에서는 512와 같은 작은 행렬에서도 슈트라센 알고리즘이 이점을 보일 수 있다고 보고되었다.^[11]
수치 안정성: 슈트라센 알고리즘은 일반적인 행렬 곱셈보다 더 큰 오차를 가질 수 있다.^[14]

결론적으로, 슈트라센 알고리즘은 이론적으로 효율적이지만, 실제 구현에서는 위와 같은 사항들을 고려하여 최적화해야 한다.

8. 관련 자료

Huang, J., Smith, T. M., Henry, G. M., & van de Geijn, R. A. (2016, 11월). Strassen's algorithm reloaded. 고성능 컴퓨팅, 네트워킹, 스토리지 및 분석 국제 회의 회보 (59페이지). IEEE Press.
Gates, A. Q., & Kreinovich, V. (2001). Strassen's Algorithm Made (Somewhat) More Natural: A Pedagogical Remark. Bulletin of the EATCS, 73, 142-145.
Grochow, J. A., & Moore, C. (2017). Designing Strassen's algorithm. arXiv preprint arXiv:1708.09398.
Ikenmeyer, C., & Lysikov, V. (2017). Strassen's 2x2 matrix multiplication algorithm: A conceptual perspective. arXiv preprint arXiv:1708.08083.

참조

_[1] 저널 Gaussian Elimination is not Optimal
_[2] Citation The Algorithm Design Manual Springer-Verlag
_[3] 저널 On multiplication of 2 × 2 matrices https://linkinghub.e[...] 1971-10
_[4] 서적 Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures ACM 2017-07-24
_[5] 저널 Pebbling Game and Alternative Basis for High Performance Matrix Multiplication https://epubs.siam.o[...] 2023-12-31
_[6] 저널 Computational complexity and numerical stability
_[7] 서적 Algebraic Complexity Theory Springer-Verlag
_[8] conference Cache-oblivious algorithms http://supertech.csa[...]
_[9] 저널 Exploiting fast matrix multiplication within the level 3 BLAS http://www.maths.man[...]
_[10] conference Using Recursion to Boost ATLAS's Performance https://www.ics.uci.[...]
_[11] conference Strassen's Algorithm Reloaded https://www.research[...] IEEE Press 2022-11-01
_[12] 서적 C言語による最新アルゴリズム事典技術評論社
_[13] 문서 Gaussian Elimination is not Optimal
_[14] 문서 Adaptive Strassen and ATLAS’s DGEMM: A Fast Square-Matrix Multiply for Modern High-Performance Systems

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com