KATUBLO | エンジニアの日常BLOG

プログラミング、数学、旅行などを中心に役立つ情報をお届け

2019年07月20日

【組み合わせアルゴリズム】Strassenのアルゴリズムについて解説!

*本文は誤りを含む可能性があります。その点理解していただけると幸いです。

アルゴリズム周辺の基本知識

Strassenのアルゴリズムの解説をする前に、アルゴリズムを勉強する上で最低限知っていた方がいいと思われる用語をまとめておきます。

1の原始n乗根

n乗すると1になる数のことです。具体例をあげるならば
$$ ω^n = 1 $$
を満たす、ωのことを指します。

ブール代数

イギリスの数学者 ブール(George Boole) が1854年の著書「思考の法則に関する研究」で 提唱した記号論理学を ブール代数(Boolean algebra) と呼び, 1 または 0 の2値のみをもつ変数を用いる論理である

出典:「ブール代数と論理演算 (1) Boolean algebra & logical operation」

https://www.biwako.shiga-u.ac.jp/sensei/mnaka/ut/boolean1.html

 

booleanの値のみで計算を行う論理学のことを指すようです。組み合わせ回路(AND素子やOR素子などを使った回路)などはこのブール代数内で理論を考えて、回路を組みます。

ブール行列

行列の各要素の値が、0、1のブール代数で表現されたものを指します。

代数構造

集合に定まっている演算などによって決まる構造のことを指します。かなり抽象度高めの言い方になってますね。具体例ですと、数字という集合があってその中で足し算をすると結果というのは必ず決まるじゃないですか。おそらくこのような構造のことを指す意味だと思います。

加法・乗法の2種類の二項演算を備えた代数構造のことです。また以下の性質を持ちます。これは整数集合Zで加法・乗法を考慮したときの関係表です。

 

加法 乗法
演算の閉性 a + b は整数 a × b は整数
結合性 a + (b + c) = (a + b) + c a × (b × c) = (a × b) × c
可換性 a + b = b + a a × b = b × a
中立元の存在性 a + 0 = a (零元 a × 1 = a (単位元
反数の存在性 a + (−a) = 0

出典: フリー百科事典『ウィキペディア(Wikipedia)』

https://ja.wikipedia.org/wiki/環_(数学)

 

性質は置いておいて、環はなんなのか?ということを簡単に理解するために以下の図を用意しました。環は以下の図のような加法(+)、乗法(・)とその他ブール値や行列を持った代数構造の集合と考えることができます。

A: 全てのn次行列

On:n次零行列

In:n次単位行列

です。この図の環の中の集合以外にも他の集合が存在すると思われます。

 

置換行列

行列の要素は0と1のみで構成され各行と各列に1が1つしか存在する行列のことです。

 

$$
\left[ \begin{array} { l l l l } { 0 } & { 0 } & { 1 } & { 0 } \\ { 0 } & { 0 } & { 0 } & { 1 } \\ { 0 } & { 1 } & { 0 } & { 0 } \\ { 1 } & { 0 } & { 0 } & { 0 } \end{array} \right]
$$

 

↑の行列式なんかは要素が0と1のみかつ各行列に1が1つの条件を満たすので置換行列です。

小行列

ある行列Aが存在したときに、この行列Aの行や列を削除した後の行列のことを指します。

直積

2つの集合A,Bが存在し、このAの集合の中の要素と、Bの集合の要素をそれぞれ取ってきて、ペアを作り、それらを集めた集合体のことを指します。具体例をあげると

$$ A = \{ 1,2 \} , B = \{ 3,4,5 \}$$

とした時、このA、Bの直積は

$$ A \times B = \{ ( 1,3 ) , ( 1,4 ) , ( 1,5 ) , ( 2,3 ) , ( 2,4 ) , ( 2,5 ) \} $$

となります。ある集合の要素を異なる集合の要素全てとペアを作る。これを全ての要素で考えたものです。

恒等式

具体例で見た方が早いです。ちなみに恒等式って高校2年生で習うと思うんですが、意味を忘れがち。

$$ (x+1)^2 = x^2 + 2x + 1  $$

xがどんな時でも成り立つ。これを恒等式という。

$$ 2x -1 = 0  $$

は[math]x=1/2[/math]のときのみ成り立つ。これは恒等式とは言わずに方程式といいます。

 

Strassenのアルゴリズムについて

Strassenのアルゴリズムの効果

結論から言うとstrassenのアルゴリズムを用いると行列の掛け算における計算量を削減することができます。

なぜ計算量を削減することができるのか

[math]n \times n  [/math] 行列のA、Bがあるとします。これら行列を[math]\frac { n } { 2 } \times \frac { n } { 2 } [/math]の行列に分解して

、以下の積の形で考えることにします。

$$
A B = \left( \begin{array} { l l } { a _ { 11 } } & { a _ { 12 } } \\ { a _ { 21 } } & { a _ { 22 } } \end{array} \right) \left( \begin{array} { l l } { b _ { 11 } } & { b _ { 12 } } \\ { b _ { 21 } } & { b _ { 22 } } \end{array} \right)
$$

$$
= \left( \begin{array} { l l } { a _ { 11 } b _ { 11 } + a _ { 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{array} \right)
$$

$$
= \left( \begin{array} { l l } { c _ { 11 } } & { c _ { 12 } } \\ { c _ { 21 } } & { c _ { 22 } } \end{array} \right)
$$

ここでstrassenのアルゴリズムは以下のようにmを定義します。

$$
m _ { 1 } = \left( a _ { 12 } – a _ { 21 } \right) \left( b _ { 21 } + b _ { 22 } \right)
$$

$$
m _ { 2 } = \left( a _ { 11 } + a _ { 22 } \right) \left( b _ { 11 } + b _ { 22 } \right)
$$

$$
m _ { 3 } = \left( a _ { 11 } – a _ { 21 } \right) \left( b _ { 11 } + b _ { 12 } \right)
$$

$$
m _ { 4 } = \left( a _ { 11 } + a _ { 21 } \right) b _ { 22 }
$$

$$
m _ { 5 } = a _ { 11 } \left( b _ { 12 } – b _ { 22 } \right)
$$

$$
m _ { 6 } = a _ { 22 } \left( b _ { 21 } – b _ { 11 } \right)
$$

$$
m _ { 7 } = \left( a _ { 21 } + c _ { 22 } \right) b _ { 11 }
$$

この定義したmは以下の関係を持ちます。Cはmを使って表現することができるんです。

$$
C _ { 11 } = m _ { 1 } + m _ { 2 } – m _ { 4 } + m _ { 6 }
$$

$$
C _ { 12 } = m _ { 4 } + m _ { 5 }
$$

$$
C _ { 21 } = m _ { 6 } + m _ { 7 }
$$

$$
C _ { 22 } = m _ { 2 } – m _ { 3 } + m _ { 5 } – m _ { 7 }
$$

通常の行列の積で計算を行う際には乗算が8回発生します。しかしこのstrassenのアルゴリズムを用いると、乗算が7回になります。mを実際に代入すると確認してみてください。乗算は計算時間を食うので1回減らすことで計算時間を削減することができるんです。

計算の削減量

[math]N \times N [/math]行列の計算時間は[math]O \left( N ^ { 3 } \right) [/math]要します。

乗算が1つ減ったことにより、計算量は以下のようになります。

$$
O \left( N ^ { \log _ { 2 } 7 } \right) \approx O \left( N ^ { 2.807 } \right)
$$

 

 

最後まで読んで頂き、ありがとうございました。
SNS等でのシェアが頂ければ幸いです!

プロフィール

@KATUO

現在都内私立大学に通う大学4年生。大学では電気電子工学を専攻。大学2年の夏頃に、プログラマーの長期インターン募集の広告が目に止まり、独学でプログラミングの学習を開始。現在は「ToC向け大規模サービスを運営するメガベンチャー」と「AIスタートアップ」でインターンで修行中。2020年4月からwebエンジニアとして社会人生活スタート。

広告

特集記事