KATUBLO | エンジニアの日常BLOG

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

2019年07月20日

【高速アルゴリズム】strassenのアルゴリズムで逆行列を求める

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

strassenのアルゴリズムで逆行列を求める

正方行列を変形する

正則行列(逆行列を持つ行列) Aが存在するとします。この行列以下のように分解します。

$$
A = \left[ \begin{array} { l l } { A _ { 11 } } & { A _ { 12 } } \\ { A _ { 21 } } & { A _ { 22 } } \end{array} \right] \tag{1}
$$

strassenのアルゴリズムを使って逆行列を求めるために以下のように変形をします。

 

$$ \Delta = \mathrm { A } _ { 22 } – \mathrm { A } _ { 21 } \mathrm { A } _ { 11 } ^ { – 1 } \mathrm { A } _ { 12 } $$

とおき、以下のようにします。

$$
A = \left[ \begin{array} { l l } { I } & { 0 } \\ { A _ { 21 } , A _ { 11 } ^ { – 1 } } & { I } \end{array} \right] \left[ \begin{array} { l l } { A _ { 11 } } & { 0 } \\ { 0 } & { \Delta } \end{array} \right] \left[ \begin{array} { c c } { I } & { A _ { 11 } ^ { – 1 } A _ { 12 } } \\ { 0 } & { I } \end{array} \right] \tag{2}
$$

実際にこの(2)が(1)になるかどうか確認してみましょう。各行列の積を1つずつ計算していきます。

$$
A = \left[ \begin{array} { l l } { I A _ { 11 } } & { I \Delta } \\ { A _ { 21 } I^ { – 1 } } & { I \Delta } \end{array} \right] \left[ \begin{array} { c c } { I } & { A _ { 11 } ^ { -1 } A _ { 12 } } \\ { 0 } & { I } \end{array} \right]
$$

$$
= \left[ \begin{array} { l l } { I ^ { 2 } A _ { 11 } } & { I ^ { 2 } A _ { 12 } } \\ { A _ { 21 } I ^ { 2 } } & { A _ { 21 } A _ { 11 } ^ { – 1 } A _ { 12 } I + I ^ { 2 } \Delta } \end{array} \right]
$$

$$
= \left[ \begin{array} { l l } { A _ { 11 } I } & { I A _ { 12 } } \\ { A _ { 21 } I } & { I \left( A _ { 21 } A _ { 11 } ^ { – 1 } A _ { 12 } + \Delta \right) } \end{array} \right]
$$

$$
= I \left[ \begin{array} { l l } { A _ { 11 } } & { A _ { 12 } } \\ { A _ { 21 } } & { A _ { 21 } A ^ { – 1 } A _ { 12 } + \left( A _ { 22 } – A _ { 21 } A _ { 11 } ^ { – 1 } A _ { 12 } \right) } \end{array} \right]
$$

$$
= I \left[ \begin{array} { l l } { A _ { 11 } } & { A _ { 12 } } \\ { A _ { 21 } } & { A _ { 22 } } \end{array} \right]
$$

Iは単位行列であり、今回はn=1と考えると

$$
= \left[ \begin{array} { l l } { A _ { 11 } } & { A _ { 12 } } \\ { A _ { 21 } } & { A _ { 22 } } \end{array} \right]
$$

となります。なので(1)⇆(2)であることが確認することができました。

逆行列の性質

𝐴 と𝐵が𝑛次の正則行列ならば、𝐴𝐵も正則で

$$ ( A B ) ^ { – 1 } = B ^ { – 1 } A ^ { – 1 } \tag{3} $$

が成り立つ。

逆行列の形にする

(3)の性質を使って、(2)の式を変形します。

$$
A ^ { – 1 } = \left[ \begin{array} { c c } { I } & { – A _ { 11 } ^ { – 1 } A _ { 12 } } \\ { 0 } & { I } \end{array} \right] \left[ \begin{array} { c c } { A _ { 11 } ^ { – 1 } } & { 0 } \\ { 0 } & { \Delta ^ { – 1 } } \end{array} \right] \left[ \begin{array} { c c } { I } & { 0 } \\ { – A _ { 21 } A _ { 11 } ^ { – 1 } } & { I } \end{array} \right]
$$

$$
= \left[ \begin{array} { c c } { A _ { 11 } ^ { – 1 } + A _ { 12 } ^ { – 1 } A _ { 12 } \Delta ^ { – 1 } A _ { 21 } A _ { 11 } ^ { – 1 } } & { – A _ { 11 } ^ { – 1 } A _ { 12 } \Delta ^ { – 1 } } \\ { – \Delta ^ { – 1 } A _ { 21 } A _ { 11 } } & { \Delta ^ { – 1 } } \end{array} \right]
$$

逆行列を計算することができました。

 

参考文献:「A Strassen-Newton Algorithm for High-Speed Parallelizable Matrix Inversion 」

https://www.researchgate.net/profile/David_Bailey3/publication/3499047_A_Strassen-Newton_algorithm_for_high-speed_parallelizable_matrixinversion/links/53d657360cf2a7fbb2ea9d1e/A-Strassen-Newton-algorithm-for-high-speed-parallelizable-matrixinversion.pdf

 

 

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

プロフィール

@KATUO

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

広告

特集記事