스트라센 알고리즘

선형대수학에서 볼커 스트라센의 이름을 딴 스트라센 알고리즘은 매트릭스 곱셈 알고리즘이다.순진한 알고리즘이 종종 더 작은 행렬에 더 낫지만, 큰 행렬에 대한 표준 행렬 곱셈 알고리즘보다 더 빠르고, 점증하지 않는 복잡성이 더 높다.Strassen 알고리즘은 매우 큰 행렬에 대해 알려진 가장 빠른 알고리즘보다 느리지만, 그러한 알고리즘은 실제 크기의 행렬에 훨씬 느리기 때문에 실제로는 유용하지 않다.

Strassen의 알고리즘은 플러스/멀티플라이와 같은 어떤 링에서도 작동하지만, 순진한 알고리즘이 여전히 작동하는 min-plus나 boolean 대수학 같은 모든 반향에 대해서는 작동하지 않으며, 소위 콤비네이터 행렬 곱셈이라고 불리는 것도 아니다.

역사

볼커 스트라센은 1969년에 이 알고리즘을 처음 발표했으며, $n^{3}$ 3 ${\$ 일반 $n^{3}$ 매트릭스 곱셈 알고리즘이 최적이 아님을 증명했다.^[1]Strassen 알고리즘은 그것보다 약간 더 낫지만, 그것의 출판은 Copersmith-Winograd 알고리즘과 같은 더 빠른 접근으로 이어진 매트릭스 곱셈에 대한 훨씬 더 많은 연구를 낳았다.

알고리즘.

왼쪽 열은 2x2 행렬 곱셈을 나타낸다.Nauve 행렬 곱셈은 왼쪽 열의 "1"마다 하나의 곱셈을 요구한다.다른 각 열은 알고리즘의 7배수 중 하나의 열을 나타내며, 열의 합은 왼쪽의 전체 행렬 곱셈을 나타낸다.

$A$ ${\displaystyle A$ $B$ $B$ 을(를) 링 ${\mathcal {R}}$ ${\$ 위에 있는 두 개의 제곱 행렬로 $B$ 두십시오 ${\mathcal {R}}$ 예를 들어, 항목이 정수 또는 실수인 행렬인 경우.We want to calculate the matrix product $C=AB$ . In the following exposition of the algorithm, we will assume that all of these matrices have sizes that are powers of two (i.e., $A,\,B,\,C\in \operatorname {Matr} _{2^{n}\times 2^{n}}({\mathcal {R$ $}}$ }) $A,\,B,\,C\in \operatorname {Matr} _{2^{n}\times 2^{n}}({\mathcal {R}})$ 그러나 이는 개념적으로만 필요한 사항이며, $행렬$ A ${\displaystyle$ A $A$ $B$ $B$ 이 $B$ (가) 유형 $2^{n}\times 2^{n}$ $2^{n}\times 2^{n}$ $2^{n}\times 2^{n}$ ${\$ 2^{ $n}\time$ 2 $^{n}}}}}}$ 에 해당되지 않는 경우, 행렬을 0으로 채우는 것은 개념적으로 생각할 수 있다 $2^{n}\times 2^{n}$ .물론 알고리즘의 삽입은 실제로 실제로 이것을 하지 않을 것이다.

그런 다음 $A$ ${\displaystyle A$ $B$ $B$ 및 $B$ $C$ $C$ 을(를) 동일한 크기의 블록 매트릭스로 $C$ 분할하십시오.

A={\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix},\quad B={\begin{bmatrix}B_{11}&B_{12}\\\B_{21}&B_{22}\end{bmatrix},\quad C={\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix},\quad }

$A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})$ i $A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})$ , B $A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})$ , $A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})$ i j ${$ $A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})$ 2 $A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})$ - 1 $A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})$ $A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})$ $A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})$ - $A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})$ $A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})$ ( R $A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})$ ) ${\displaystyle A_{ij},B_{ij},C_{ij}\in$ \in \ $matername$ { $Mat$ } $_{2^{$ n-1}\ $times{n-1}}}}{$ n-1 $A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})$ 순진한 알고리즘은 다음과 같다.

{\begin{bmatrix}C_{11}&C_{12}\\\C_{21}\C_{22}\end{bmatrix}={\begin{bmatrix}}A_{11}B_{11}+A_{12}B_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\A_{21}B_{11}+A_{22}B_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\end{bmatrix}}}.

이 공사로 우리는 승수의 수를 줄이지 않았다. $C_{ij}$ 는 $C_{ij}$ j $C_{ij}$ {\ $displaystyle C_{ij}$ 행렬을 $C_{ij}$ 계산하기 위해 여전히 8배의 행렬 블록이 필요하며, 이는 표준 행렬 곱셈을 사용할 때 우리가 필요로 하는 것과 동일한 수의 곱이다.

Strassen 알고리즘은 대신 새로운 행렬을 정의한다.

{\reasoned}M_{1}&=(A_{11}+A_{22})(B_{11}+B_{22});\\M_{2}&=(A_{21}+A_{22})B_{11};\M_{3}&=A_{11}(B_{12}-B_{22});\\M_{4}&=A_{22}(B_{21}-B_{11});\\\M_{5}&=(A_{11}+A_{12})B_{22};\\M_{6}&=(A_{21}-A_{11})(B_{11}+B_{12});\\M_{7}&=(A_{12}-A_{22})(B_{21}+B_{22})\\\end{aigned}}}

8 대신 7배수( $M_{k}$ $M_{k}$ ${\$ 만 사용한다 $M_{k}$ $C_{ij}$ C i $C_{ij}$ ${\$ 을(를) $M_{k}$ $M_{k}$ ${\$ 의 관점에서 표현할 $C_{ij}$ 수 있다 $M_{k}$

{\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}}={\begin{bmatrix}M_{1}+M_{4}-M_{5}+M_{7}&M_{3}+M_{5}\\M_{2}+M_{4}&M_{1}-M_{2}+M_{3}+M_{6}\end{bmatrix}}.

하위 행렬이 숫자로 전락할 때까지 이 분할 ${\mathcal {R}}$ 를 반복한다 $(링$ R {\ $displaystyle {\$ mathcal { $R}).$ 위에서 언급한 바와 같이 원래의 매트릭스가 2의 힘이 아닌 크기를 가졌다면, 결과 $A$ 은 A $A$ 과 $A$ B{\ $displaystyle B}$ 처럼 행과 열이 0이 될 것이고 $B$ 그 다음 이러한 것들은 우리가 진정으로 원하는 $C$ (더 작은) $매트릭스$ C ${\displaystystyle C}$ 를 얻기 위해 이 시점에서 벗겨질 것이다.

Strassen의 알고리즘의 실제 구현은 충분히 작은 하위 메트릭스를 위한 매트릭스 곱셈의 표준 방법으로 전환하며, 그 알고리즘이 더 효율적이다.Strassen의 알고리즘이 더 효율적인 특정한 교차점은 구체적인 구현과 하드웨어에 달려 있다.이전의 저자들은 최적화된 구현을 위해 32에서 128까지의 폭을 가진 행렬의 경우 Strassen의 알고리즘이 더 빠르다고 추정했었다.^[2]그러나, 이러한 교차점이 최근 몇 년 동안 증가하고 있다는 것이 관찰되었고, 2010년 한 연구에서는 매트릭스 크기가 1000을 초과할 때까지, 그리고 심지어 여러 매트릭스 크기에도, 고도로 최적화된 전통적인 곱셈에 비해, 스트라센 알고리즘의 단 한 단계도 현재 아키텍처에 이롭지 않은 경우가 많다는 것을 발견했다.1000의 이익은 일반적으로 기껏해야 미미하다(약 10% 이하).^[3]좀 더 최근의 연구(2016년)는 512개 정도의 매트릭스에 대한 ^[4]편익과 약 20%의 편익을 관찰했다.

점근 복잡성

위의 알고리즘의 개요는 매트릭스의 하위 블록에 대한 기존의 8개의 매트릭스 곱셈 대신 7개의 매트릭스만으로 벗어날 수 있다는 것을 보여주었다.반면에 블록의 추가 및 소급 작업을 수행해야 하지만 이는 전체 복잡성에 대해서는 전혀 문제가 되지 않는다. $N/2$ / 2 $N/2$ 매트릭스 $N/2$ 를 추가하면 $(N/2)^{2}$ ( $(N/2)^{2}$ $(N/2)^{2}$ ) 2 ${\$ 연산만 $(N/2)^{2}$ 필요한 $N/2$ 반면, 곱셈은 상당히 더 비싸다( $2(N/2)^{3}$ 으로 $2(N/2)^{3}$ 2 ( $2(N/2)^{3}$ $2(N/2)^{3}$ 2) $2(N/2)^{3}$ ) 3 ${\$ 또는 $2(N/2)^{3}$ 곱셈 연산.

그렇다면 문제는 Strassen의 알고리즘에 정확히 몇 개의 연산이 필요한지, 그리고 이것이 약 $2N^{3}$ ${\$ 여기서 $N=2^{n}$ = $N=2^{n}$ ${\$ N= $2^{n$ 산술 연산, 즉 점증적 복잡성 $\Theta (N^{3})$ $\Theta (N^{3})$ $){\displaystate$ )을 필요로 하는 표준 매트릭스 곱셈과 어떻게 비교하는가에 대한 것이다. $yle \Teta(N^{3$

Strassen 알고리즘에 필요한 추가 및 승수의 수는 $f(n)$ 과 같이 계산할 수 있다: f $f(n)$ ( $f(n)$ ) $f(n)$ 는 $2^{n}\times 2^{n}$ $2^{n}\times 2^{n}$ $2^{n}\times 2^{n}$ ${\$ 행렬에 $2^{n}\times 2^{n}$ 대한 연산 수입니다 $f(n)$ .그런 다음 Strassen 알고리즘의 재귀적 적용을 통해 알고리즘의 각 적용에서 수행되는 추가 횟수에 따라 달라지는 $l$ 일부 $상수$ l ${\displaystyle f$ $(n){$ $}$ 에 $f(n)=7f(n-1)+l4^{n}$ f $f(n)=7f(n-1)+l4^{n}$ ( $f(n)=7f(n-1)+l4^{n}$ $f(n)=7f(n-1)+l4^{n}$ $f(n$ = 7f(n-1)+ $l4^{n$ 를 확인할 수 있다. $f(n)=(7+o(1))^{n}$ $f(n)=(7+o(1))^{n}$ ( $f(n)=(7+o(1))^{n}$ n ) $f(n)=(7+o(1))^{n}$ = $f(n)=(7+o(1))^{n}$ ( 7 $f(n)=(7+o(1))^{n}$ + $f(n)=(7+o(1))^{n}$ $f(n)=(7+o(1))^{n}$ 1 $f(n)=(7+o(1))^{n}$ ) $f(n)=(7+o(1))^{n}$ n ${\$ $^{n}}$ , i.e., the asymptotic complexity for multiplying matrices of size $N=2^{n}$ using the Strassen algorithm is $O([7+o(1)]^{n})=O(N^{\log _{2}7+o(1)})\approx O(N^{2.8074})$ .그러나 산술 연산수의 감소는 다소 감소된 수치적 안정성의 가격으로 이루어지며,^[5] 알고리즘도 순진한 알고리즘에 비해 훨씬 많은 메모리를 요구한다.초기 매트릭스 두 개 모두 다음 동력인 2까지 치수를 확장해야 하며, 이는 원소의 최대 4배까지 저장되며, 7개의 보조 매트릭스는 각각 확장된 매트릭스 내 원소의 4분의 1을 포함한다.

Strassen의 알고리즘은 하위 블록의 7배수 대신 8배가 필요한 매트릭스 곱셈을 하는 "즐거운" 방법과 비교할 필요가 있다.그러면 표준 접근법에서 기대하는 복잡성이 발생한다: $O(8^{\log _{2}n})=O(N^{\log _{2}8})=O(N^{3})$ ( $O(8^{\log _{2}n})=O(N^{\log _{2}8})=O(N^{3})$ $O(8^{\log _{2}n})=O(N^{\log _{2}8})=O(N^{3})$ $O(8^{\log _{2}n})=O(N^{\log _{2}8})=O(N^{3})$ ⁡ $O(8^{\log _{2}n})=O(N^{\log _{2}8})=O(N^{3})$ ) $O(8^{\log _{2}n})=O(N^{\log _{2}8})=O(N^{3})$ = $O(8^{\log _{2}n})=O(N^{\log _{2}8})=O(N^{3})$ ( $O(8^{\log _{2}n})=O(N^{\log _{2}8})=O(N^{3})$ $O(8^{\log _{2}n})=O(N^{\log _{2}8})=O(N^{3})$ $O(8^{\log _{2}n})=O(N^{\log _{2}8})=O(N^{3})$ $O(8^{\log _{2}n})=O(N^{\log _{2}8})=O(N^{3})$ $O(8^{\log _{2}n})=O(N^{\log _{2}8})=O(N^{3})$ ) $O(8^{\log _{2}n})=O(N^{\log _{2}8})=O(N^{3})$ = $O(8^{\log _{2}n})=O(N^{\log _{2}8})=O(N^{3})$ ( $O(8^{\log _{2}n})=O(N^{\log _{2}8})=O(N^{3})$ $O(8^{\log _{2}n})=O(N^{\log _{2}8})=O(N^{3})$ ) ${\displaystyle O (8^{\log _{2}n}}=O(N^{2}8})=O($ N^{ $3$ 이 두 알고리즘의 비교를 보면 증상 없이 Strassen의 알고리즘이 더 빠르다는 것을 알 수 있다.N $N_{\text{threshold}}$ 임계값 ${\$ 이 존재하므로 $N_{\text{threshold}}$ , "전통적인" 방법보다 더 큰 행렬을 Strassen의 알고리즘과 더 효율적으로 곱한다.그러나 이 점증적 진술은 스트라센의 알고리즘이 작은 행렬에도 항상 더 빠르다는 것을 의미하지는 않으며, 실제로 이것은 사실 다음과 같은 경우가 아니다.작은 행렬의 경우, 매트릭스 블록의 추가 추가에 따른 비용이 곱셈의 수 절감을 능가한다.또한 위의 분석에서 포착되지 않은 다른 요소들이 있는데, 예를 들어 메모리에서 프로세서로 데이터를 로드하는 것과 이 데이터에 대한 실제 작업을 수행하는 것의 비용 사이의 오늘날의 하드웨어의 비용 차이 등이다.이러한 종류의 고려사항의 결과로, Strassen의 알고리즘은 일반적으로 "큰" 행렬에만 사용된다.이러한 종류의 효과는 코퍼스미스와 위노그라드의 알고리즘과 같은 대체 알고리즘에서 더욱 뚜렷하게 나타난다.점증상으로는 훨씬 더 빠르지만 $N_{\text{threshold}}$ N ${\$ 은 너무 $N_{\text{threshold}}$ 커서 실제로 마주치는 행렬에는 알고리즘이 일반적으로 사용되지 않는다.

순위 또는 이선형 복잡성

이선형 지도의 이선형 복잡성 또는 순위는 행렬 곱셈의 점증적 복잡성에서 중요한 개념이다.필드 F에 대한 $\phi :\mathbf {A} \times \mathbf {B} \rightarrow \mathbf {C}$ 이선형 지도 $\phi :\mathbf {A} \times \mathbf {B} \rightarrow \mathbf {C}$ : $\phi :\mathbf {A} \times \mathbf {B} \rightarrow \mathbf {C}$ $\phi :\mathbf {A} \times \mathbf {B} \rightarrow \mathbf {C}$ B $\phi :\mathbf {A} \times \mathbf {B} \rightarrow \mathbf {C}$ → C ${\$ 순위는 (표기법 일부 남용)로 정의된다.

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\}

즉, 이선형 지도의 순위는 최단 이선형 연산의 길이인 것이다.^[6]Strassen의 알고리즘의 $2\times 2$ 는 2 $2\times 2$ $[\displaystyle$ 2\ $times 2}$ 행렬 $2\times 2$ 곱셈의 순위가 7을 넘지 않는다는 것을 보여준다.이를 보려면 이 알고리즘을 (표준 알고리즘과 함께) 이러한 이선 계산으로 표현해 봅시다.행렬의 경우 이중 공간 A*와 B*는 스칼라 이중 도트 제품이 유도한 필드 F로 된 지도(즉, 이 경우 Hadamard 제품의 모든 입력의 합계)로 구성된다.

	표준 알고리즘			스트라센 알고리즘
$(\displaystyle i}$	$f_{i}(\mathbf {a} )$	$g_{i}(\mathbf {b} )$	$w_{i}$	$f_{i}(\mathbf {a} )$	$g_{i}(\mathbf {b} )$	$w_{i}$
1	${\bmatrix}1&0\\0&0\end{bmatrix}:\mathbf {a}$	${\bmatrix}1&0\\0&0\end{bmatrix}:\mathbf {b}$	${\bmatrix}1&0\\0&0\end{bmatrix}$	${\bmatrix}1&0\\0&1\end{bmatrix}:\mathbf {a}$	${\bmatrix}1&0\\0&1\end{bmatrix}:\mathbf {b}$	${\bmatrix}1&0\\0&1\end{bmatrix}$
2	${\bmatrix}0&1\\0&0\end{bmatrix}:\mathbf {a}$	${\bmatrix}0&0\\1&0\end{bmatrix}:\mathbf {b}$	${\bmatrix}1&0\\0&0\end{bmatrix}$	${\bmatrix}0&0\\1&1\end{bmatrix}:\mathbf {a}$	${\bmatrix}1&0\\0&0\end{bmatrix}:\mathbf {b}$	${\bmatrix}0&0\\\1&-1\end{bmatrix}$
3	${\bmatrix}1&0\\0&0\end{bmatrix}:\mathbf {a}$	${\bmatrix}0&1\\0&0\end{bmatrix}:\mathbf {b}$	${\bmatrix}0&1\\0&0\end{bmatrix}$	${\bmatrix}1&0\\0&0\end{bmatrix}:\mathbf {a}$	${\bmatrix}0&1\\0&-1\end{bmatrix}:\mathbf {b}$	${\bmatrix}0&1\\0&1\end{bmatrix}$
4	${\bmatrix}0&1\\0&0\end{bmatrix}:\mathbf {a}$	${\bmatrix}0&0\\\0&1\end{bmatrix}:\mathbf {b}$	${\bmatrix}0&1\\0&0\end{bmatrix}$	${\bmatrix}0&0\\\0&1\end{bmatrix}:\mathbf {a}$	${\bmatrix}-1&0\1&0\end{bmatrix}:\mathbf {b}$	${\bmatrix}1&0\\1&0\end{bmatrix}$
5	${\bmatrix}0&0\\1&0\end{bmatrix}:\mathbf {a}$	${\bmatrix}1&0\\0&0\end{bmatrix}:\mathbf {b}$	${\bmatrix}0&0\\1&0\end{bmatrix}$	${\bmatrix}1&#1\\0&0\end{bmatrix}:\mathbf {a}$	${\bmatrix}0&0\\\0&1\end{bmatrix}:\mathbf {b}$	${\bmatrix}-1&1\\0&0\end{bmatrix}$
6	${\bmatrix}0&0\\\0&1\end{bmatrix}:\mathbf {a}$	${\bmatrix}0&0\\1&0\end{bmatrix}:\mathbf {b}$	${\bmatrix}0&0\\1&0\end{bmatrix}$	${\bmatrix}-1&0\1&0\end{bmatrix}:\mathbf {a}$	${\bmatrix}1&#1\\0&0\end{bmatrix}:\mathbf {b}$	${\bmatrix}0&0\\\0&1\end{bmatrix}$
7	${\bmatrix}0&0\\1&0\end{bmatrix}:\mathbf {a}$	${\bmatrix}0&1\\0&0\end{bmatrix}:\mathbf {b}$	${\bmatrix}0&0\\\0&1\end{bmatrix}$	${\bmatrix}0&1\\0&-1\end{bmatrix}:\mathbf {a}$	${\bmatrix}0&0\\1&1\end{bmatrix}:\mathbf {b}$	${\bmatrix}1&0\\0&0\end{bmatrix}$
8	${\bmatrix}0&0\\\0&1\end{bmatrix}:\mathbf {a}$	${\bmatrix}0&0\\\0&1\end{bmatrix}:\mathbf {b}$	${\bmatrix}0&0\\\0&1\end{bmatrix}$
	${\displaystyle \mathbf {a} \mathbf {b} =\sum _{i=1}^{8f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}}}}}}{i}}}}}.$			${\displaystyle \mathbf {a} \mathbf {b} =\sum _{i=1}^{7f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}}}}}{i}}}}}.$

It can be shown that the total number of elementary multiplications $L$ required for matrix multiplication is tightly asymptotically bound to the rank $R$ , i.e. $L=\Theta (R)$ , or more specifically, since the constants are known, ${\displaystyle R$ $/2$ $\$ $leq L\leq R}$ 등급의 유용한 속성 중 하나는 텐서 제품에 대한 하위 속성이며, 이를 통해 $2^{n}\times 2^{n}\times 2^{n}$ $2^{n}\times 2^{n}\times 2^{n}$ $2^{n}\times 2^{n}\times 2^{n}$ ${\$ $displaystyle$ $2^{n}\time$ 2 $^{n}\time 2^{$ $n}}}$ 매트릭스 $2^{n}\times 2^{n}\times 2^{n}$ 곱셈을 $7n$ 이하의 $7n$ 기본 $7n$ 으로 수행할 수 있음을 알 수 있다. $n$ $n$ . ( $2\times 2\times 2$ $n$ ${\displaystyle$ $n$ $}$ -fold $n$ tensor 제품은 2 × 2 $2\times 2\times 2$ $2\times 2\times 2$ $(\displaystyle$ 2 $\time 2\time 2}$ 매트릭스 곱셈 $2\times 2\times 2$ 맵 자체 - $n$ ${\displaysty n}$ -th $n$ tensor power)는 표시된 알고리즘의 재귀적 단계를 통해 실현된다.)

캐시 동작

Strassen의 알고리즘은 망각된 캐시다.캐쉬 동작 알고리즘 분석 결과 발생 가능

\theta \left(1+{\frac{n^{2}}:{b}+{n^{\log_{2}7}{b{\sqrt{M}}}\오른쪽)

$크기$ M {\ $displaystyle$ M $}$ 의 이상적인 캐시( $예$ $M/b$ $M$ 길이 $M/b$ b {\ $displaystyle$ M $/b}$ 행의 $M/b$ b $M/b$ ${\displaystyle b})$ ^[7]^{: 13}를 가정하는 실행 중에 캐시가 누락됨.

구현 고려 사항

위의 설명은 행렬이 정사각형이며, 크기는 2의 힘이며, 필요하면 패딩을 사용해야 한다고 기술하고 있다.이 제한은 메스커 곱셈의 한계에 도달할 때까지 행렬을 재귀적으로 반으로 나눌 수 있게 한다.이 제한은 복잡성에 대한 설명과 분석을 단순화하지만 실제로 필요한 것은 아니다.^[8] 실제로 설명한 대로 매트릭스를 채우면 계산 시간이 증가하며 애초에 방법을 사용함으로써 얻는 상당히 좁은 시간 절약 효과를 쉽게 제거할 수 있다.

좋은 구현은 다음을 준수한다.

스칼라의 한계까지 스트라센 알고리즘을 사용할 필요는 없고 바람직하지도 않다.기존 매트릭스 곱셈에 비해 알고리즘은 추가/수축에 상당한 $O(n^{2})$ $){\displaystyle O(n^{2})$ 워크로드를 $O(n^{2})$ 추가하므로, 일정한 크기 이하에서는 기존의 곱셈을 사용하는 것이 좋을 것이다.따라서 예를 들어 $1600\times 1600$ $1600\times 1600$ $(\displaystyle 1600\time 1600)$ 은 $25\times 25$ $2048\times 2048$ × $2048\times 2048$ ${\displaystyle 2048\time 2048}($ 으 $25\times 25$ )로 패딩할 필요가 $1600\times 1600$ 없다. 25 $25\times 25$ $25\times 25$ $25\time 25$ 매트릭스로 세분화되고 그 수준에서 기존의 곱셈을 사용할 수 있기 때문이다 $2048\times 2048$
그 방법은 실제로 어떤 차원의 사각 행렬에도 적용될 수 있다.^[3]치수가 짝수일 경우 기술한 대로 반으로 갈라진다.치수가 홀수일 경우, 1행, 1열씩 0패딩이 먼저 적용된다.이러한 패딩은 즉석에서, 나른하게 적용할 수 있으며, 그 결과 생성되는 대로 여분의 행과 컬럼이 버려진다.예를 들어 행렬이 $199\times 199$ $199\times 199$ $199\times 199$ $199\time 199$ 이라고 가정합시다 $199\times 199$ 왼쪽 상단 부분이 $100\times 100$ $100\times 100$ $[\displaystyle 100\time 100}$ 이고 $100\times 100$ , 오른쪽 하단 $99\times 99$ 이 99 $99\times 99$ × $[\displaystyle 99\time 99}$ 이 되도록 분할할 수 있다 $99\times 99$ 작업에 필요한 곳이면 어디든 $99$ $99$ 의 치수는 먼저 $100$ $100$ $100$ 에 0으로 패딩된다 $99$ .예를 들어, 제품 $M_{2}$ 2 ${\$ }는 출력의 아래쪽 행에서만 사용되므로 $M_{2}$ , $99$ {\ $displaystyle 99$ } 행 높이만 되어야 하며, 따라서 이를 생성하기 위해 $A_{21}+A_{22}$ 사용되는 왼쪽 $A_{21}+A_{22}$ $A_{21}+A_{22}$ 21 + A $A_{21}+A_{22}$ {\ $displaystyle A_{21}+A_{22}}$ 는 99{\ $style 99}$ 행 높이만 $99$ 되어야 한다.100개의 행에 $합한$ 패드를 붙일 필요가 없으며, A $A_{21}$ ${\$ 에서 $A_{22}$ $100$ $100$ $100$ 열만 패딩하면 A $A_{21}$ ${\$ 과 일치한다 $A_{21}$

게다가, 행렬이 정사각형일 필요는 없다.비제곱 행렬은 동일한 방법을 사용하여 반으로 나눌 수 있으며, 더 작은 비제곱 행렬을 산출할 수 있다.행렬이 정사각형이 아닌 경우, 예를 들어 다음과 같은 $O(n^{2})$ ( $O(n^{2})$ 2 $O(n^{2})$ ) {\ $displaystyle O(n^{$ 2 $O(n^{2})$ 와 같은 간단한 방법을 사용하여 초기 작업을 더 정사각형 제품으로 줄일 가치가 있을 것이다.

A product of size $[2N\times N]\ast [N\times 10N]$ can be done as 20 separate $[N\times N]\ast [N\times N]$ operations, arranged to form the result;
A product of size $[N\times 10N]\ast [10N\times N]$ can be done as 10 separate $[N\times N]\ast [N\times N]$ operations, summed to form the result.

이러한 기법들은 단순히 2의 제곱으로 채워지는 것에 비해 구현을 더 복잡하게 만들 것이다. 그러나, 전통적인 곱하기보다는 Strassen의 구현을 수행하는 모든 사람이 구현의 단순성보다는 계산 효율성에 더 높은 우선순위를 둘 것이라는 것은 합리적인 가정이다..

실제로 스트라센의 알고리즘은 작은 행렬에도 기존 곱셈보다 더 나은 성능을 얻기 위해 구현될 수 있으며, 전혀 사각형이 아닌 행렬에도 구현될 수 있으며, 이미 고성능 재래식 곱셈에 필요한 버퍼 이상의 작업공간을 요구하지 않는다.^[4]

참고 항목

수학 연산의 계산 복잡성
가우스-요르단 제거
코퍼스미스-위노그라드 알고리즘
Z 순서 행렬 표현
Karatsuba 알고리즘, N 자리 $O(n^{2})$ 를 $O(n^{\log _{2}3})$ ( $O(n^{\log _{2}3})$ $O(n^{\log _{2}3})$ 2 $O(n^{\log _{2}3})$ ⁡ 3 ) ${\displaystyle O(n^{\log _{2$ }})에서 $O(n^{\log _{2}3})$ $O(n^{2})$ ( $O(n^{\log _{2}3})$ 2 $O(n^{2})$ ) ${\displaystyle O(n^{2}})$ 가 $O(n^{2})$ 아닌 O $($ n })로 곱하기 위한 기능
Toom-Cook 알고리즘, 한 번에 2개 이상의 블록으로 재귀 분할-컨커밍 분해를 허용하는 카라츠바 알고리즘의 보다 빠른 일반화
가우스의 복잡한 곱셈 알고리즘은 4가 아닌 3개의 실제 곱셈을 사용하여 두 개의 복잡한 숫자를 곱한다.

참조

^ Strassen, Volker (1969). "Gaussian Elimination is not Optimal". Numer. Math. 13 (4): 354–356. doi:10.1007/BF02165411. S2CID 121656251.
^ Skiena, Steven S. (1998), "§8.2.3 Matrix multiplication", The Algorithm Design Manual, Berlin, New York: Springer-Verlag, ISBN 978-0-387-94860-7.
^ ^a ^b D'Alberto, Paolo; Nicolau, Alexandru (2005). Using Recursion to Boost ATLAS's Performance (PDF). Sixth Int'l Symp. on High Performance Computing.
^ ^a ^b Huang, Jianyu; Smith, Tyler; Henry, Greg; van de Geijn, Robert (2016). Strassen's Algorithm Reloaded. International Conference for High Performance Computing, Networking, Storage and Analysis (SC'16).
^ Webb, Miller (1975). "Computational complexity and numerical stability". SIAM J. Comput. 4 (2): 97–107. doi:10.1137/0204009.
^ Burgisser; Clausen; Shokrollahi (1997). Algebraic Complexity Theory. Springer-Verlag. ISBN 3-540-60582-7.
^ Frigo, M.; Leiserson, C. E.; Prokop, H.; Ramachandran, S. (1999). Cache-oblivious algorithms (PDF). Proc. IEEE Symp. on Foundations of Computer Science (FOCS). pp. 285–297.
^ Higham, Nicholas J. (1990). "Exploiting fast matrix multiplication within the level 3 BLAS" (PDF). ACM Transactions on Mathematical Software. 16 (4): 352–368. doi:10.1145/98267.98290. hdl:1813/6900. S2CID 5715053.

토마스 H. 코멘, 찰스 E. Leiserson, Ronald L. Rivest, Clifford Stein.알고리즘 소개, Second Edition.MIT 프레스 앤 맥그로우 힐, 2001.ISBN 0-262-03293-7제28장: 제28.2절: Strassen의 행렬 곱셈 알고리즘, 페이지 735–741.

외부 링크

Weisstein, Eric W. "Strassen's Formulas". MathWorld. (빠른 행렬 반전 공식도 포함)
Tyler J. Negin, Strassen의 셀 광대역 엔진 알고리즘

[1] Strassen, Volker (1969). "Gaussian Elimination is not Optimal". Numer. Math. 13 (4): 354–356. doi:10.1007/BF02165411. S2CID 121656251.

[2] Skiena, Steven S. (1998), "§8.2.3 Matrix multiplication", The Algorithm Design Manual, Berlin, New York: Springer-Verlag, ISBN 978-0-387-94860-7.

[dalberto-3] D'Alberto, Paolo; Nicolau, Alexandru (2005). Using Recursion to Boost ATLAS's Performance (PDF). Sixth Int'l Symp. on High Performance Computing.

[huang_et_al.-4] Huang, Jianyu; Smith, Tyler; Henry, Greg; van de Geijn, Robert (2016). Strassen's Algorithm Reloaded. International Conference for High Performance Computing, Networking, Storage and Analysis (SC'16).

[5] Webb, Miller (1975). "Computational complexity and numerical stability". SIAM J. Comput. 4 (2): 97–107. doi:10.1137/0204009.

[6] Burgisser; Clausen; Shokrollahi (1997). Algebraic Complexity Theory. Springer-Verlag. ISBN 3-540-60582-7.

[prokop-7] Frigo, M.; Leiserson, C. E.; Prokop, H.; Ramachandran, S. (1999). Cache-oblivious algorithms (PDF). Proc. IEEE Symp. on Foundations of Computer Science (FOCS). pp. 285–297.

[8] Higham, Nicholas J. (1990). "Exploiting fast matrix multiplication within the level 3 BLAS" (PDF). ACM Transactions on Mathematical Software. 16 (4): 352–368. doi:10.1145/98267.98290. hdl:1813/6900. S2CID 5715053.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

v t 수치 선형대수학
주요개념	부동소수점 수치안정성
문제	선형 방정식 체계 매트릭스 분해 행렬 곱하기(알고리즘) 행렬 분할 희소성 문제
하드웨어	CPU 캐시 TLB 캐시-관심 알고리즘 심드 다중 처리
소프트웨어	매트랩 기본 선형 대수 하위 프로그램(BLAS) 라팩 전문 라이브러리 범용 소프트웨어

Search