Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
Strassenのアルゴリズムによる行列積の計算 /strassen-algorithm
Search
Miyakawa Taku
December 27, 2017
Programming
3.8k
8
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
Strassenのアルゴリズムによる 行列積の計算 /strassen-algorithm
このスライドの著者は宮川拓です。
CC BY 3.0 Licenseの元に利用を許諾します。
Miyakawa Taku
December 27, 2017
Transcript
19 slides
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
More Decks by Miyakawa Taku
See All by Miyakawa Taku
入門: 末尾呼び出し最適化 /tail-call-elimination-intro
miyakawataku
2
2.6k
JVM言語の動き方・動かし方 /make-jvm-lang
miyakawataku
6
2.5k
Java SE 8から11で何が起きた?一気におさらいしてみよう! /java-se-8-to-11
miyakawataku
14
5.8k
ミニバッチサイズと学習率の関係 /small-batch-learning
miyakawataku
0
2.4k
機械学習プロジェクトの進め方 /howtoproceedwithmlproject
miyakawataku
0
410
グラフアルゴリズムその2: 単一始点最短路問題 /graphShortestPaths
miyakawataku
0
230
Viterbiのアルゴリズム /viterbi-algorithm
miyakawataku
0
380
Other Decks in Programming
See All in Programming
仕様駆動開発入門 (何を作るかを先に決めて渡す) | 目指せ Kiro マスター 05
inariku
PRO
3
210
Augmenting AI with the Power of Jakarta EE
ivargrimstad
0
390
LLM 101
dalinaum
0
520
[DroidKnights 2026] Workflow AX: From Auto-Documented Policies to E2E Testing
raeminkang
0
600
AIが生成したコードは読むべきか?抽象化設計とコードの品質保証 / abstraction-design-and-quality
minodriven
16
9.4k
RaspberryPi 5で軽くはじめるk3sとtailscaleを用いたホームサーバー構築 (1)
nasum
0
420
Scalaの型でマルチテナントの認可を守る
nextbeatdev
0
160
学びを記事・スライド・Xへ高速展開する― AI-assisted Learning Loopで回すコンテンツ生成術
ochtum
0
220
Web3Dライブラリを作ってVue Custom Rendererの仕組みを理解しよう / lets learn vue custom renderer by making 3d library
drumath2237
1
140
AIコーディング時代のKotest ユニットテストから APIレベルの仕様固定化テストへ
ooga04
0
310
Proxmox x Talos Linux x Terraform で実現するなんかいい感じの Kubernetes クラスタ / A Sleek Kubernetes Cluster Powered by Proxmox, Talos Linux, and Terraform
nnaka2992
0
280
React Native経験者が Flutterを30⽇間触って驚いたこと
3saito
0
200
Featured
See All Featured
Mozcon NYC 2025: Stop Losing SEO Traffic
samtorres
1
610
Everyday Curiosity
cassininazir
0
410
Raft: Consensus for Rubyists
vanstee
143
7.9k
The Straight Up "How To Draw Better" Workshop
denniskardys
239
140k
Claude Code どこまでも/ Claude Code Everywhere
nwiizo
68
61k
Learning to Love Humans: Emotional Interface Design
aarron
275
41k
Accessibility Awareness
sabderemane
1
310
BBQ
matthewcrist
90
10k
Designing for humans not robots
tammielis
254
26k
30 Presentation Tips
portentint
PRO
1
470
コードの90%をAIが書く世界で何が待っているのか / What awaits us in a world where 90% of the code is written by AI
rkaga
63
48k
Collaborative Software Design: How to facilitate domain modelling decisions
baasie
1
390