Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Strassenのアルゴリズムによる行列積の計算 /strassen-algorithm
Search
Miyakawa Taku
December 27, 2017
Programming
8
3.4k
Strassenのアルゴリズムによる 行列積の計算 /strassen-algorithm
このスライドの著者は宮川拓です。
CC BY 3.0 Licenseの元に利用を許諾します。
Miyakawa Taku
December 27, 2017
Tweet
Share
More Decks by Miyakawa Taku
See All by Miyakawa Taku
入門: 末尾呼び出し最適化 /tail-call-elimination-intro
miyakawataku
2
2.4k
JVM言語の動き方・動かし方 /make-jvm-lang
miyakawataku
6
2.2k
Java SE 8から11で何が起きた?一気におさらいしてみよう! /java-se-8-to-11
miyakawataku
15
5.4k
ミニバッチサイズと学習率の関係 /small-batch-learning
miyakawataku
0
2.2k
機械学習プロジェクトの進め方 /howtoproceedwithmlproject
miyakawataku
0
360
グラフアルゴリズムその2: 単一始点最短路問題 /graphShortestPaths
miyakawataku
0
180
Viterbiのアルゴリズム /viterbi-algorithm
miyakawataku
0
300
Other Decks in Programming
See All in Programming
Le côté obscur des IA génératives
pascallemerrer
0
140
GitHub Actions × AWS OIDC連携の仕組みと経緯を理解する
ota1022
0
250
CSC509 Lecture 05
javiergs
PRO
0
300
理論と実務のギャップを超える
eycjur
0
130
Go言語の特性を活かした公式MCP SDKの設計
hond0413
1
230
私はどうやって技術力を上げたのか
yusukebe
43
18k
Cursorハンズオン実践!
eltociear
2
990
The Past, Present, and Future of Enterprise Java
ivargrimstad
0
300
クラシルを支える技術と組織
rakutek
0
200
CSC509 Lecture 04
javiergs
PRO
0
300
Go言語はstack overflowの夢を見るか?
logica0419
0
120
非同期jobをtransaction内で 呼ぶなよ!絶対に呼ぶなよ!
alstrocrack
0
710
Featured
See All Featured
Dealing with People You Can't Stand - Big Design 2015
cassininazir
367
27k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
132
19k
The Web Performance Landscape in 2024 [PerfNow 2024]
tammyeverts
9
860
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
52
5.6k
Large-scale JavaScript Application Architecture
addyosmani
514
110k
Optimizing for Happiness
mojombo
379
70k
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
23
1.5k
Art, The Web, and Tiny UX
lynnandtonic
303
21k
The Cost Of JavaScript in 2023
addyosmani
54
9k
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
9
970
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
31
9.7k
The MySQL Ecosystem @ GitHub 2015
samlambert
251
13k
Transcript
Strassenのアルゴリズムによる 行列積の計算 2017-12-27 ビール&LT大会 ハッシュタグ: #jjug 宮川 拓
@miyakawa_taku JJUG幹事です SI屋で賃労働してます オレオレJVM言語Kinkを作っています https://bitbucket.org/kink/kink
尾上部屋の里山さんのファンです 自己紹介 #jjug 2/19
あらまし 本物のプログラマになりたい! ということで、 『アルゴリズムイントロダクション』 を読み進めています n次正方行列の積が、Θ(3)よりも小さい計 算量で計算できるらしい(§4.2)
びっくり! #jjug 3/19
背景 機械学習の計算は行列計算のかたまり 行列計算が速いと嬉しい #jjug 4/19
まずはふつうに計算 #jjug 5/19
三重ループ = ( ), = ( )をn次の正方行列とする =
∙ の要素は = σ=1 ∙ すなおに三重ループで実装: for i in 1~n: for j in 1~n: c[i, j] = 0 for k in 1~n: c[i, j] += a[i, k] * b[k, j] 3 回繰り返す → 計算量は() #jjug 6/19
準備: 分割統治 #jjug 7/19
分割統治 A, B, Cを縦横半分に分割すると、 = ∙ は次のように書き直せる 11 12 21
22 = 11 12 21 22 ∙ 11 12 21 22 = 11 ∙ 11 + 12 ∙ 21 11 ∙ 12 + 12 ∙ 22 21 ∙ 11 + 22 ∙ 21 21 ∙ 12 + 22 ∙ 22 #jjug 8/19
分割統治 def prod(a, b): if a.order == b.order == 1:
return matrix_1x1(a[0, 0] * b[0, 0]) a11, a12, a21, a22 = partition(a) b11, b12, b21, b22 = partition(b) c11 = prod(a11, b11) + prod(a12, b21) c12 = prod(a11, b12) + prod(a12, b22) c21 = prod(a21, b11) + prod(a22, b21) c22 = prod(a21, b12) + prod(a22, b22) return concat(c11, c12, c21, c22) 計算量はスカラ値の掛け算の回数に比例 n次行列の乗算は 2 次行列の乗算を8回再帰呼び出し #jjug 9/19
分割統治 n: 行列の次数 スカラ値の 掛け算の回数 1 1 2 8 4
64 8 512 16 4,096 2倍 8 = 23 倍 2倍 8 = 23 倍 2倍 8 = 23 倍 計算量はやっぱり() #jjug 10/19
Strassenのアルゴリズム #jjug 11/19
Strassenのアルゴリズム A, Bを分割した上で1 ~7 を次のように置く 1 = 11 (12
− 22 ) 2 = (11 + 12 )22 3 = (21 + 22 )11 4 = 22 21 − 11 5 = (11 + 22 )(11 + 22 ) 6 = 12 − 22 21 + 22 7 = 11 − 21 11 + 12 2 次行列を 計7回乗算 #jjug 12/19
Strassenのアルゴリズム ここで、次が成り立つ 11 = 11 11 + 12 21
= 5 + 4 − 2 + 6 12 = 11 12 + 12 22 = 1 + 2 21 = 21 11 + 22 21 = 3 + 4 22 = 21 12 + 22 22 = 5 + 1 − 3 − 7 Cは1 ~7 の和で表せる 2 次行列の乗算を7回再帰呼び出しすれば良い! #jjug 13/19
Strassenのアルゴリズム Strassen 計算量 n 三重ループ 計算量 1 1 1 7
2 8 49 4 64 343 8 512 2,401 16 4,096 8倍 8倍 8倍 7倍 7倍 7倍 Θ 27 = .… Θ 28 = Θ 3 < #jjug 14/19
実装&計測 #jjug 15/19
実装 https://bitbucket.org/miyakawataku/matrix- multiplication/src/default/matrix.go #jjug 16/19
計測 0.000010 0.000100 0.001000 0.010000 0.100000 1.000000 10.000000 100.000000 1,000.000000
10,000.000000 16 64 256 1,024 4,096 実行時間(秒) n (行列の次数) 三重ループ Strassen #jjug 17/19
総括 #jjug 18/19
総括 素敵なアルゴリズムは、nが小さい時には遅い。 そして大抵の場合、nは小さい。 素敵なアルゴリズムの計算量の式には、大きな 定数項が掛かっている。 nが大きくなることが分かっていない限り、素敵 にしてはならない。 ― Rob Pike
“Notes on Programming in C” #jjug 19/19