Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Strassenのアルゴリズムによる 行列積の計算 /strassen-algorithm

Strassenのアルゴリズムによる 行列積の計算 /strassen-algorithm

このスライドの著者は宮川拓です。
CC BY 3.0 Licenseの元に利用を許諾します。

Miyakawa Taku

December 27, 2017
Tweet

More Decks by Miyakawa Taku

Other Decks in Programming

Transcript

  1. 三重ループ  = ( ), = ( )を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
  2. 分割統治 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
  3. 分割統治 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
  4. 分割統治 n: 行列の次数 スカラ値の 掛け算の回数 1 1 2 8 4

    64 8 512 16 4,096 2倍 8 = 23 倍 2倍 8 = 23 倍 2倍 8 = 23 倍 計算量はやっぱり() #jjug 10/19
  5. 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
  6. 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
  7. 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
  8. 計測 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