매트릭스 곱셈

매트릭스 곱셈은 많은 숫자 알고리즘의 중심 연산이기 때문에 매트릭스 곱셈 알고리즘을 효율적으로 만드는 데 많은 작업이 투자되어 왔다.계산 문제에서 매트릭스 곱셈의 적용은 과학 컴퓨팅과 패턴 인식을 포함한 많은 분야와 그래프를 통해 경로를 계산하는 것과 같은 겉보기에는 관련이 없어 보이는 문제에서 발견된다.^[1]많은 다른 알고리즘은 병렬 및 분산 시스템을 포함하여 다양한 유형의 하드웨어에 매트릭스를 곱하기 위해 설계되었으며, 계산 작업은 여러 프로세서에 걸쳐(아마도 네트워크를 통해) 분산된다.null

행렬 곱셈의 수학적 정의를 직접 적용하면 해당³ 필드 위에 n × n $행렬$ $2개$ 를 곱하는 데 시간이 걸리는 알고리즘(빅 O 표기법에서 in $(n 3))$ 이 나온다.행렬의 곱셈에 필요한 시간에 대한 더 좋은 무증상 한계는 1960년대 스트라센의 알고리즘 이후 알려져 왔지만, 최적의 시간이 무엇인지(즉, 행렬 곱셈의 계산 복잡성이 무엇인지)는 여전히 알려져 있지 않다.2020년^[update] 12월 현재, 최상의 무증상 복잡성을 가진 매트릭스 곱셈 알고리즘은 조시 앨먼과 버지니아 바실레프스카 윌리엄스가 제공한 $O(n 2.3728596)$ 시간에 실행되지만,^[2]^[3] 이 알고리즘은 상수가 크기 때문에 은하 알고리즘이며, 현실적으로 실현될 수 없다.null

반복 알고리즘

행렬 곱셈의 정의는 $C$ = $n$ × $m$ 행렬 $A$ 와 $m$ × p $행렬$ $B$ 에 대한 $AB이면$ C는 $항목$ 이 있는 $n$ × p $행렬$ 이라는 것이다.

c_{ij}=\sum _{k=1}^{m}a_{ik}b_{kj}}

이를 통해 1에서 $n$ 까지, $1$ 에서 $j$ 까지 지수 $i$ 를 반복하는 간단한 알고리즘을 구성할 수 있으며, 중첩된 루프를 사용하여 위 사항을 계산할 수 있다.

$입력$ : 행렬 A $및$ B
$C$ 를 적절한 크기의 새 행렬로 설정
$1$ 에서 $n$ 까지 i의 경우:
- $1$ 부터 $p$ 까지 j의 경우:
  - $합$ = $0$ 으로 설정
  - $1$ 에서 $m$ 까지 k인 경우:
    - $합계$ ← $합계$ + $A ik$ × $B$ 를_kj 설정
  - $C ij$ ← $sum$ 설정
$리턴$ C

이 알고리즘은 $θ(nmp)$ (증상 기호) 시간이 걸린다.^[1]알고리즘 분석의 목적을 위한 일반적인 단순화는 입력들이 모두 크기 $n$ × $n$ 의 제곱 행렬이라고 가정하는 것이다. 이 경우 실행 시간은 $θ(n 3),$ 즉 치수 크기의 세제곱이다.^[4]null

캐시 동작

행 및 열 주계열 순서 그림

반복적 매트릭스 곱셈의 세 루프는 정확성이나 점증적 실행 시간에 영향을 주지 않고 임의로 서로 교환할 수 있다.그러나 알고리즘의 메모리 액세스 패턴과 캐시 사용으로 인해 순서가 실제 성능에 상당한 영향을 미칠 수 있다.^[1] 행렬이 행 주 순서, 열 주 순서 또는 둘 다 혼합된 순서로 저장되는지에 따라 가장 좋은 순서도 달라진다.null

특히 캐시 라인당 $M바이트$ 와 $b바이트$ 로 구성된 완전 연관 캐시의 이상화된 경우(즉, 캐시 라인당 mbyte)M/b 캐시 라인), 위의 알고리즘은 $A$ 와 $B$ 가 행 주계열 순서로 저장되는 것에 대해 차선책이다. $n$ > $M / b일$ 때, 내부 루프( $A행$ 과 $B행$ 열을 동시에 스윕)가 반복될 때마다 $B$ 의 요소에 접근할 때 캐시 미스(cache miss)가 발생한다.이는 알고리즘이 최악의 경우 $θ(n 3)$ 캐시 누락을 발생시킨다는 것을 의미한다.2010년^[update] 현재, 프로세서의 그것과 비교한 기억의 속도는 캐시가 실제 계산보다는 상당량의 매트릭스의 실행 시간을 지배하는 것과 같다.^[5]

$행-주요$ 레이아웃에서 A와 $B$ 에 대한 반복 알고리즘의 최적 변형은 타일 버전이며, 여기서 매트릭스는 크기 $mM$ 의 사각 타일로 암시적으로 구분된다.^[5]^[6]

$입력$ : 행렬 A $및$ B
$C$ 를 적절한 크기의 새 행렬로 설정
타일 $크기$ T = $θ(\sqrt M)$ 선택
$T$ 단계에서 1부터 $n$ 까지 $I$ 의 경우:
- $T$ 단계 1에서 $p$ 까지 J의 경우:
  - $T$ 단계에서 1 ~ $m$ 의 K인 경우:
    - $A$ 와_{I:I+T, K:K+T} $B$ 를_{K:K+T, J:J+T} $C$ 로_{I:I+T, J:J+T} 곱하면 다음과 같다.
    - $I$ 에서 $Min까지(I$ + $T,$ $n):$
      - $J$ 에서 $최소까지(J$ + $T,$ p $):$
        $합$ = $0$ 으로 설정
        
        $K$ 에서 $최소로 k$ 인 $경우 (K$ + T $,$ m):
        $합계$ ← $합계$ + $A ik$ × $B$ 를_kj 설정
        
        $C ij ij$ ← C + $sum$ 설정
$리턴$ C

이상화된 캐시 모델에서, 이 알고리즘은 오직 $((n 3 / b mM)$ 캐시 미스만을 유발한다. divisor $b$ $\sqrt M$ 은 현대 기계에서 몇 순서에 달하므로, 캐시 미스보다는 실제 계산이 실행 시간을 지배한다.^[5]null

분할 및 재무 알고리즘

반복 알고리즘의 대안은 매트릭스 곱셈을 위한 분할 및 분할 알고리즘이다.이는 블록 파티셔닝에 의존한다.

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

치수가 2인 모든 제곱 행렬에 대해 작동한다. 즉, $모양$ 은 일부 n의 경우 $2 n$ × $2$ 이다ⁿ.매트릭스 제품은 지금

{\begin{pmatrix}C_{11}&C_{12}\\\c_{21}\C_{22}\end{pmatrix}}={\begin{pmatrix}}A_{11}&A_{12}\\A_{21}&A_{22}\\end{pmatrix}}{\begin{pmatrix}B_{11}&B_{12}\\\B_{21}&B_{22}\\end{pmatrix}={\begin{pmatrix}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_{21}&A_{21}B_{12}+A_{22}B_{22}\\end{pmatrix}}}}}}

8쌍의 하위 행렬로 구성되며, 그 뒤에 추가 단계가 뒤따른다.분할 및 변환 알고리즘은 스칼라 곱셈 $c 11$ = $ab$ 을₁₁₁₁ 기본 사례로 사용하여 더 작은 곱셈을 반복적으로 계산한다.null

$n$ 의 함수로서 이 알고리즘의 복잡성은 재발에^[4] 의해 주어진다.

[\displaystyle T(1)=\theta(1);}

[\displaystyle T(n)=8T(n/2)+\세타(n^{2}),}

4쌍의 결과 행렬을 요소별로 합하기 위해 $n /2$ 와 $θ(n 2)$ 크기의 행렬에 대한 8개의 재귀 호출을 고려한다.분할 및 재무 재발을 위한 마스터 정리의 적용은 이 재귀가 반복 알고리즘과동일한 솔루션 $θ(n 3$ )을 갖는 것을 보여준다.^[4]null

비제곱 행렬

임의모형의 행렬에 대해 작동하며 실제^[5] 속도가 더 빠른 이 알고리즘의 변형은 다음과 같이 행렬을 4개의 하위모형이 아닌 2개로 분할한다.^[7]지금 행렬을 분할한다는 것은 행렬을 크기가 같은 두 부분으로 나누거나, 홀수 치수의 경우 가능한 한 동일한 크기에 가깝게 나누는 것을 의미한다.null

입력: $n$ × $m$ 크기의 행렬 $A$ , $m$ × p $크기$ 의 $B$ .
베이스 케이스: $max(n,$ $m,$ $p)$ 가 일부 임계값 미만일 경우 반복 알고리즘의 롤링되지 않은 버전을 사용하십시오.
재귀 사례:

$max(n,$ $m,$ $p)가 n이면$ $A$ 를 수평으로 분할:

C={\begin{pmatrix}A_{1}\\A_{2}\end{pmatrix}}{{pmatrix}}{{{pmatrix}}}}{{pB}={\begin{pmatrix}A_{1}B\\A_{2}B\end{pmatrix}

$그렇지$ 않은 경우, $max (n,$ $m,$ p) = $p$ 인 경우, B를 $수직$ 으로 분할:

C=A{\begin{pmatrix}B_{1}&B_{2}\end{pmatrix}={\begin{pmatrix}}AB_{1}&AB_{2}\end{pmatrix}}

그렇지 않으면 $max(n,$ $m,$ $p)$ = $m$ . 수직 분할 A 및 $수평$ $분할$ B:

{\displaystyle C={\begin{pmatrix}A_{1}&A_{2}\end{pmatrix}{\begin{pmatrix}B_{1}\\B_{2}\end{pmatrix}}=A_{1}B_{1}+A_{2}}B_{2}}:

캐시 동작

재귀적 매트릭스 곱셈 연산에서도 캐시 아가씨률은 타일을 깔아 놓은 반복 버전지만 그 알고리즘과는 달리, 재귀적 알고리즘:[7] 없튜닝 매개 변수 최적의 캐시 성능을 내기 위해 필요하다cache-oblivious 있는 캐시 크기 효과적으로 인해 동적인 다중 프로그래밍 환경의 행동 거지 같다.로캐시 공간을 차지하는 다른 프로세스.^[5](단순 반복 알고리즘도 캐쉬에 민감하지만, 매트릭스 레이아웃이 알고리즘에 적응되지 않으면 실제로는 훨씬 느리다.)null

이상적인 캐시의 $M$ 라인이 있는 시스템에서 이 알고리즘에 의해 발생한 캐시 누락의 수(각각 $b바이트$ 크기)는^[7]^{: 13}

\theta \left(m+n+p+{\frac {mn+np+mp}{b}}{\frac {mnp}{b{\sqrt {M}}\오른쪽)

하위 큐빅 알고리즘

매트릭스 곱셈

O(n^{\omega })

(

O(n^{\omega })

O(n^{\omega })

)

O(n^{\omega })

{\

displaystyle O(n^{\omega }})

의 계산 복잡성에 대한 시간 경과에 따른 지수

Ω

추정치의 개선

O(n^{\omega })

직설적인 것보다 더 좋은 가동 시간을 제공하는 알고리즘이 존재한다.가장 먼저 발견된 것은 1969년 볼커 스트라센에 의해 고안된 스트라센의 알고리즘으로, 종종 "빠른 매트릭스 곱셈"이라고 일컬어진다.그것은 몇 번의 추가 및 뺄셈 작업을 희생하면서 (일반적으로 8이 아닌) 7번만 필요로 하는 2 x 2-매트릭스 2개를 곱하는 방법에 기초한다.적용 이 재귀적으로. O(n로그 2⁡ 7)≈ O(n2.807){O(n^{\log_{2}7})\approx O(n^{2.807})\displaystyle}의 승법의 비용으로 알고리즘을 슈트라 센의 알고리즘이 더 많고 수리적 안정성은 순진한 algorithm,[8]에 비해 감소되지만 빠른 거 어디서 n을 경우에, 100또는 so[1]a복잡하다nd appeaBLAS와 같은 몇몇 도서관에서 rs.^[9]수치적 안정성은 문제가 되지 않는 유한한 분야와 같은 정확한 영역에 걸쳐 큰 행렬에 매우 유용하다.null

Strassen의 알고리즘이 무증상 복잡성 측면에서 얼마나 잘 개선될 수 있는가는 이론 컴퓨터 과학에서 공공연한 문제다.일반적으로 $\omega$ 으로 표시되는 행렬 곱셈 지수는 필드 위에 있는 n $\omega$ $n\times n$ $n\times n$ $n\times n$ 행렬을 $n\times n$ $n^{\omega +o(1)}$ $n^{\omega +o(1)}$ + $n^{\omega +o(1)}$ ( $n^{\omega +o(1)}$ ) ${\$ n $^{\omega +o(1)}$ 필드 $n^{\omega +o(1)}$ 연산을 사용하여 함께 곱할 수 있는 가장 작은 실제 수입니다.현재 $\omega$ ${\displaystyle \omega$ $}$ 의 최고 경계는 조시 앨먼과 버지니아 바실레브스카 윌리엄스의 < $2$ $2.3728596>$ 이다 $\omega$ $\omega <2.3728596$ ^[2]이 알고리즘은 이 연구 계열의 다른 모든 최근의 알고리즘과 마찬가지로 1990년 돈 코퍼스미스와 슈무엘 위노그라드가 부여한 코퍼스미스-위노그라드 알고리즘의 일반화다.^[10]이러한 알고리즘의 개념적 개념은 스트라센의 알고리즘과 유사하다: 2 $k$ × k-매트릭스에 $k 3$ 곱하기 위해 고안된 방법이며, 이 기법은 재귀적으로 적용된다.그러나 Big O 표기법에 의해 숨겨져 있는 상수계수는 너무 커서 이러한 알고리즘은 오늘날의 컴퓨터에서는 다루기 힘든 행렬에만 가치가 있다.^[11]^[12]null

Freivalds' 알고리즘은 주어진 $행렬$ A, $B$ , $C$ 가 $AB$ = $C$ 인 $경우 ((n 2)$ 시간에서 확인하는 간단한 몬테카를로 알고리즘이다.

병렬 및 분산 알고리즘

공유메모리병렬주의

앞에서 스케치한 분할 및 분할 알고리즘은 공유 메모리 멀티프로세서를 위해 두 가지 방법으로 병렬화할 수 있다.이것들은 8개의 재귀행렬 매트릭스 승수가

{\pmatrix}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_{21}&A_{21}B_{12}+A_{22}B_{22}\\end{pmatrix}}}}}}

4개의 합계가 그렇듯이 서로 독립적으로 수행될 수 있다(알고리즘은 합계를 수행하기 전에 승수를 "계산"해야 한다).문제의 완전한 병렬화를 이용하여 포크-조인 스타일 유사점(fork-join style philoscode)으로 표현할 수 있는 알고리즘을 얻는다.^[13]

절차 $곱하기(C,$ $A,$ $B):$

베이스 케이스: $n$ = $1$ 인 경우 $c 11 a 11$ a × $b 11$ (또는 작은 블록 매트릭스를 곱함)를 설정하십시오.
그렇지 않은 경우, $형상 n$ × n의 새 행렬 $T$ 에 공간을 할당하고, 다음 작업을 수행하십시오.
- $A$ 를 $A 11$ , A, $A 12 21$ , $A$ 로₂₂ 분할한다.
- $B$ 를 $B 11$ , B, $B 12 21$ , $B$ 로₂₂ 분할한다.
- $C$ 를 $C 11$ , C, $C 12 21$ , $C$ 로₂₂ 분할한다.
- $T$ 를 $T 11$ , T, $T 12 21$ , $T$ 로₂₂ 분할한다.
- 병렬 실행:
  - 포크 $곱셈(C 11,$ $A 11,$ $B 11)$
  - 포크 $곱셈(C 12,$ $A 11,$ $B 12)$
  - 포크 $곱셈(C 21,$ $A 21,$ $B 11)$
  - 포크 $곱셈(C 22,$ $A 21,$ $B 12)$
  - 포크 $곱셈(T 11,$ $A 12,$ $B 21)$
  - 포크 $곱셈(T 12,$ $A 12,$ $B 22)$
  - 포크 $곱셈(T 21,$ $A 22,$ $B 21)$
  - 포크 $곱셈(T 22,$ $A 22,$ $B 22)$
- 조인하십시오(병렬 포크가 완료될 때까지 대기).
- $add(C,$ $T)$
- $T$ 의 할당을 해제하십시오.

절차 $추가(C,$ $T)$ 는 $요소별$ 로 $C$ 에 T를 추가한다.

base $case : n$ = 1인 $경우 11$ c $t 11 11$ c + t를 설정한다(또는 짧은 루프를 한다, 아마도 연마되지 않았다).
그렇지 않은 경우:null
- $C$ 를 $C 11$ , C, $C 12 21$ , $C$ 로₂₂ 분할한다.
- $T$ 를 $T 11$ , T, $T 12 21$ , $T$ 로₂₂ 분할한다.
- 병렬로:
  - 포크 $추가(C 11,$ $T 11)$
  - 포크 $추가(C 12,$ $T 12)$
  - 포크 $추가(C 21,$ $T 21)$
  - 포크 $추가(C 22,$ $T 22)$
- 가입하다.

여기서 포크는 이전에 "포크된" 모든 연산이 완료되기를 기다리는 동안 나머지 함수 호출과 병렬로 연산이 실행될 수 있다는 신호를 보내는 키워드다. $파티션$ 은 포인터 조작만으로 목적을 달성한다.null

이 알고리즘은 $θ(log 2$ $n)$ 단계의 임계 경로 길이를 가지며, 이는 프로세서가 무한히 많은 이상적인 기계에서 그만큼 많은 시간이 걸린다는 것을 의미하므로, 어떤 실제 컴퓨터에서도 $θ(n 3 /log 2$ $n)$ 의 최대 속도 업을 가진다.이 알고리즘은 임시 매트릭스 $T$ 와 데이터를 주고받는 데 내재된 통신비 때문에 실용적이지 않지만, 보다 실용적인 변형은 임시 매트릭스를 사용하지 않고 $θ(n 2)$ 속도 증가를 달성한다.^[13]null

블럭 행렬 곱하기.2D 알고리즘에서 각 프로세서는

C

의 서브트릭 1개를 담당한다.3D 알고리즘에서

A

와

B

의 모든 하위 메트릭 쌍은 하나의 프로세서에 할당된다.

통신 회피 및 분산 알고리즘

계층적 메모리가 있는 현대적 아키텍처에서는 입력 매트릭스 요소를 로드하고 저장하는 비용이 산술 비용을 지배하는 경향이 있다.단일 시스템에서 이것은 RAM과 캐시 간에 전송되는 데이터의 양인 반면 분산 메모리 멀티 노드 시스템에서는 노드 간에 전송되는 양인 반면, 어느 경우든 통신 대역폭이라고 한다.세 개의 중첩 루프를 사용하는 nauve 알고리즘은 $Ω(n 3)$ 통신 대역폭을 사용한다.null

캐논의 알고리즘은 2D 알고리즘으로도 알려져 있으며, 각 입력 매트릭스를 블록 매트릭스로 분할하는 통신 회피 알고리즘으로, 각 입력 매트릭스는 크기 $/$ $M$ /3의 소자가 $mM$ / $3인$ 블록 매트릭스, 여기서 $M$ 은 고속 메모리의 크기인 것이다.^[14]그런 다음 순발력 알고리즘은 블록 매트릭스에 사용되며, 하위 매트릭스의 생산물을 전적으로 고속 메모리로 계산한다.이는 통신 대역폭을 점증적으로 최적( $Ω(n 3)$ 계산을 수행하는 알고리즘의 경우)인 $O (n 3 / n$ )로 감소시킨다.^[15]^[16]null

$processorsp$ 2D $메쉬$ 에 의해 $pp$ 로 배열된 p 프로세서로 분산된 설정에서 결과의 하위트리거 1개를 각 프로세서에 할당할 수 있으며, 각 노드가 최소 $O (n 2 / p)$ 요소를 저장한다고 가정할 때 점증적으로 최적인 O $(n 2$ /p) $단어$ 를전송하는 각 프로세서로 제품을 계산할 수 있다.^[16]이것은 프로세서를 3D 큐브 메시지로 배열하는 3D 알고리즘에 의해 개선될 수 있으며, 두 개의 입력 하위 행렬의 모든 제품을 단일 프로세서에 할당한다.그런 다음 각 행에 대해 감소를 수행하여 결과 하위 메뉴를 생성한다.^[17]이 알고리즘은 프로세서당 $O (n 2 / p 2/3)$ 단어를 전송하는데, 이는 무증상 최적이다.^[16]단, 이를 위해서는 각 입력 매트릭스 $요소$ 를^1/3 p회 복제해야 하므로 입력 저장에 필요한 것보다 더 많은 $p$ 의^1/3 메모리가 필요하다.이 알고리즘은 Strassen과 결합하여 런타임을 더욱 줄일 수 있다.^[17]"2.5D" 알고리즘은 메모리 사용량과 통신 대역폭 사이의 지속적인 절충을 제공한다.^[18]맵리듀스와 같은 현대적인 분산 컴퓨팅 환경에서는 전문화된 곱셈 알고리즘이 개발되었다.^[19]null

메쉬 알고리즘

매트릭스 곱셈은 교차 배선 메쉬에 있는 두 개의 n×n 매트릭스에 대해 2n-1 단계로 완료되었다.

메쉬에는 다양한 곱셈 알고리즘이 있다.2D Cannon의 알고리즘을 사용하여 표준 2차원 메쉬에 2n×n을 곱하는 경우, 반복 연산을 위해 이 숫자의 절반으로 줄였지만 3n-2 단계로 곱셈을 완료할 수 있다.^[20]두 행렬의 데이터가 동시에 도착하지 않고 0으로 패딩해야 하기 때문에 표준 배열은 비효율적이다.null

2n-1단계만 필요한 2단 교차선망에서는 결과가 더욱 빠르다.^[21]성능은 100% 효율로 이어지는 반복적인 연산을 위해 더욱 향상된다.^[22]교차 배선 메쉬 배열은 비 평면(즉, 다층) 처리 구조의 특수한 경우로 볼 수 있다.^[23]null

참고 항목

참조

^ ^a ^b ^c ^d Skiena, Steven (2008). "Sorting and Searching". The Algorithm Design Manual. Springer. pp. 45–46, 401–403. doi:10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
^ ^a ^b Alman, Josh; Williams, Virginia Vassilevska (2020), "A Refined Laser Method and Faster Matrix Multiplication", 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), arXiv:2010.05846
^ Hartnett, Kevin (23 March 2021). "Matrix Multiplication Inches Closer to Mythic Goal". Quanta Magazine. Retrieved 2021-04-01.
^ ^a ^b ^c Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 75–79. ISBN 0-262-03384-4.
^ ^a ^b ^c ^d ^e Amarasinghe, Saman; Leiserson, Charles (2010). "6.172 Performance Engineering of Software Systems, Lecture 8". MIT OpenCourseWare. Massachusetts Institute of Technology. Retrieved 27 January 2015.
^ Lam, Monica S.; Rothberg, Edward E.; Wolf, Michael E. (1991). The Cache Performance and Optimizations of Blocked Algorithms. Int'l Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS).
^ ^a ^b ^c Prokop, Harald (1999). Cache-Oblivious Algorithms (PDF) (Master's). MIT.
^ Miller, Webb (1975), "Computational complexity and numerical stability", SIAM News, 4 (2): 97–107, CiteSeerX 10.1.1.148.9947, doi:10.1137/0204009
^ Press, William H.; Flannery, Brian P.; Teukolsky, Saul A.; Vetterling, William T. (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press. p. 108. ISBN 978-0-521-88068-8.
^ Coppersmith, Don; Winograd, Shmuel (1990), "Matrix multiplication via arithmetic progressions" (PDF), Journal of Symbolic Computation, 9 (3): 251, doi:10.1016/S0747-7171(08)80013-2
^ Iliopoulos, Costas S. (1989), "Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix" (PDF), SIAM Journal on Computing, 18 (4): 658–669, CiteSeerX 10.1.1.531.9309, doi:10.1137/0218045, MR 1004789, archived from the original (PDF) on 2014-03-05, retrieved 2015-01-16, The Coppersmith–Winograd algorithm is not practical, due to the very large hidden constant in the upper bound on the number of multiplications required.
^ Robinson, Sara (November 2005), "Toward an Optimal Algorithm for Matrix Multiplication" (PDF), SIAM News, 38 (9), Even if someone manages to prove one of the conjectures—thereby demonstrating that $ω = 2$ —the wreath product approach is unlikely to be applicable to the large matrix problems that arise in practice. [...] the input matrices must be astronomically large for the difference in time to be apparent.
^ ^a ^b Randall, Keith H. (1998). Cilk: Efficient Multithreaded Computing (PDF) (Ph.D.). Massachusetts Institute of Technology. pp. 54–57.
^ Kalman Filter Algorithm, Technical Report, Ph.D.를 구현하는 셀룰러 컴퓨터인 Lynn Eliot Cannon.논문, 몬태나 주립 대학교, 1969년 7월 14일.
^ Hong, J. W.; Kung, H. T. (1981). "I/O complexity: The red-blue pebble game" (PDF). STOC '81: Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing: 326–333.
^ ^a ^b ^c Irony, Dror; Toledo, Sivan; Tiskin, Alexander (September 2004). "Communication lower bounds for distributed-memory matrix multiplication". J. Parallel Distrib. Comput. 64 (9): 1017–1026. CiteSeerX 10.1.1.20.7034. doi:10.1016/j.jpdc.2004.03.021.
^ ^a ^b Agarwal, R.C.; Balle, S. M.; Gustavson, F. G.; Joshi, M.; Palkar, P. (September 1995). "A three-dimensional approach to parallel matrix multiplication". IBM J. Res. Dev. 39 (5): 575–582. CiteSeerX 10.1.1.44.3404. doi:10.1147/rd.395.0575.
^ Solomonik, Edgar; Demmel, James (2011). "Communication-optimal parallel 2.5D matrix multiplication and LU factorization algorithms". Proceedings of the 17th International Conference on Parallel Processing. Part II: 90–109.
^ Bosagh Zadeh, Reza; Carlsson, Gunnar (2013). "Dimension Independent Matrix Square Using MapReduce" (PDF). arXiv:1304.1467. Bibcode:2013arXiv1304.1467B. Retrieved 12 July 2014. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
^ Bae, S.E.; Shinn, T.-W.; Takaoka, T. (2014). "A faster parallel algorithm for matrix multiplication on a mesh array". Procedia Computer Science. 29: 2230–2240. doi:10.1016/j.procs.2014.05.208.
^ Kak, S (1988). "A two-layered mesh array for matrix multiplication". Parallel Computing. 6 (3): 383–385. CiteSeerX 10.1.1.88.8527. doi:10.1016/0167-8191(88)90078-6.
^ Kak, S. (2014) 교차 배선 메쉬 배열의 매트릭스 곱셈의 효율성.https://arxiv.org/abs/1411.3273
^ Kak, S (1988). "Multilayered array computing". Information Sciences. 45 (3): 347–365. CiteSeerX 10.1.1.90.4753. doi:10.1016/0020-0255(88)90010-2.

추가 읽기

Buttari, Alfredo; Langou, Julien; Kurzak, Jakub; Dongarra, Jack (2009). "A class of parallel tiled linear algebra algorithms for multicore architectures". Parallel Computing. 35: 38–53. arXiv:0709.1272. doi:10.1016/j.parco.2008.10.002. S2CID 955.
Goto, Kazushige; van de Geijn, Robert A. (2008). "Anatomy of high-performance matrix multiplication". ACM Transactions on Mathematical Software. 34 (3): 1–25. CiteSeerX 10.1.1.140.3583. doi:10.1145/1356052.1356053. S2CID 9359223.
Van Zee, Field G.; van de Geijn, Robert A. (2015). "BLIS: A Framework for Rapidly Instantiating BLAS Functionality". ACM Transactions on Mathematical Software. 41 (3): 1–33. doi:10.1145/2764454. S2CID 1242360.
GEM을 최적화하는 방법

[skiena-1] Skiena, Steven (2008). "Sorting and Searching". The Algorithm Design Manual. Springer. pp. 45–46, 401–403. doi:10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.

[aw20-2] Alman, Josh; Williams, Virginia Vassilevska (2020), "A Refined Laser Method and Faster Matrix Multiplication", 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), arXiv:2010.05846

[3] Hartnett, Kevin (23 March 2021). "Matrix Multiplication Inches Closer to Mythic Goal". Quanta Magazine. Retrieved 2021-04-01.

[clrs-4] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 75–79. ISBN 0-262-03384-4.

[ocw-5] Amarasinghe, Saman; Leiserson, Charles (2010). "6.172 Performance Engineering of Software Systems, Lecture 8". MIT OpenCourseWare. Massachusetts Institute of Technology. Retrieved 27 January 2015.

[6] Lam, Monica S.; Rothberg, Edward E.; Wolf, Michael E. (1991). The Cache Performance and Optimizations of Blocked Algorithms. Int'l Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS).

[prokop-7] Prokop, Harald (1999). Cache-Oblivious Algorithms (PDF) (Master's). MIT.

[8] Miller, Webb (1975), "Computational complexity and numerical stability", SIAM News, 4 (2): 97–107, CiteSeerX 10.1.1.148.9947, doi:10.1137/0204009

[9] Press, William H.; Flannery, Brian P.; Teukolsky, Saul A.; Vetterling, William T. (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press. p. 108. ISBN 978-0-521-88068-8.

[coppersmith-10] Coppersmith, Don; Winograd, Shmuel (1990), "Matrix multiplication via arithmetic progressions" (PDF), Journal of Symbolic Computation, 9 (3): 251, doi:10.1016/S0747-7171(08)80013-2

[11] Iliopoulos, Costas S. (1989), "Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix" (PDF), SIAM Journal on Computing, 18 (4): 658–669, CiteSeerX 10.1.1.531.9309, doi:10.1137/0218045, MR 1004789, archived from the original (PDF) on 2014-03-05, retrieved 2015-01-16, The Coppersmith–Winograd algorithm is not practical, due to the very large hidden constant in the upper bound on the number of multiplications required.

[robinson-12] Robinson, Sara (November 2005), "Toward an Optimal Algorithm for Matrix Multiplication" (PDF), SIAM News, 38 (9), Even if someone manages to prove one of the conjectures—thereby demonstrating that $ω = 2$ —the wreath product approach is unlikely to be applicable to the large matrix problems that arise in practice. [...] the input matrices must be astronomically large for the difference in time to be apparent.

[cilk-13] Randall, Keith H. (1998). Cilk: Efficient Multithreaded Computing (PDF) (Ph.D.). Massachusetts Institute of Technology. pp. 54–57.

[14] Kalman Filter Algorithm, Technical Report, Ph.D.를 구현하는 셀룰러 컴퓨터인 Lynn Eliot Cannon.논문, 몬태나 주립 대학교, 1969년 7월 14일.

[15] Hong, J. W.; Kung, H. T. (1981). "I/O complexity: The red-blue pebble game" (PDF). STOC '81: Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing: 326–333.

[irony-16] Irony, Dror; Toledo, Sivan; Tiskin, Alexander (September 2004). "Communication lower bounds for distributed-memory matrix multiplication". J. Parallel Distrib. Comput. 64 (9): 1017–1026. CiteSeerX 10.1.1.20.7034. doi:10.1016/j.jpdc.2004.03.021.

[Agarwal-17] Agarwal, R.C.; Balle, S. M.; Gustavson, F. G.; Joshi, M.; Palkar, P. (September 1995). "A three-dimensional approach to parallel matrix multiplication". IBM J. Res. Dev. 39 (5): 575–582. CiteSeerX 10.1.1.44.3404. doi:10.1147/rd.395.0575.

[18] Solomonik, Edgar; Demmel, James (2011). "Communication-optimal parallel 2.5D matrix multiplication and LU factorization algorithms". Proceedings of the 17th International Conference on Parallel Processing. Part II: 90–109.

[19] Bosagh Zadeh, Reza; Carlsson, Gunnar (2013). "Dimension Independent Matrix Square Using MapReduce" (PDF). arXiv:1304.1467. Bibcode:2013arXiv1304.1467B. Retrieved 12 July 2014. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)

[20] Bae, S.E.; Shinn, T.-W.; Takaoka, T. (2014). "A faster parallel algorithm for matrix multiplication on a mesh array". Procedia Computer Science. 29: 2230–2240. doi:10.1016/j.procs.2014.05.208.

[21] Kak, S (1988). "A two-layered mesh array for matrix multiplication". Parallel Computing. 6 (3): 383–385. CiteSeerX 10.1.1.88.8527. doi:10.1016/0167-8191(88)90078-6.

[22] Kak, S. (2014) 교차 배선 메쉬 배열의 매트릭스 곱셈의 효율성.https://arxiv.org/abs/1411.3273

[23] Kak, S (1988). "Multilayered array computing". Information Sciences. 45 (3): 347–365. CiteSeerX 10.1.1.90.4753. doi:10.1016/0020-0255(88)90010-2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

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

Search

매트릭스 곱셈

네임스페이스

더

목차

반복 알고리즘

캐시 동작

분할 및 재무 알고리즘

비제곱 행렬

캐시 동작

하위 큐빅 알고리즘

병렬 및 분산 알고리즘

공유메모리병렬주의

통신 회피 및 분산 알고리즘

메쉬 알고리즘

참고 항목

참조

추가 읽기