行列とベクトルに関する計算
■ 概要
計算量のオーダーを理解するための最も簡単な例として行列とベクトルに関する計算をご紹介します。簡単な例とはいえ、数値計算を行う上で出てくる頻度が高い計算なので、しっかり把握したいものです。
行列とベクトルの計算には数種類あり、表1にまとめてみます。ここで行列をA、B、ベクトルをu、v、スカラーをkで表します。行列もベクトルもともにサイズがNとします。
| 計算 | 数式 | 計算量のオーダー |
|---|---|---|
| ベクトルとスカラーの掛け算 | ku | O(N) |
| ベクトルとベクトルの足し算 | u+v | O(N) |
| ベクトルとベクトルの内積 | u・v | O(N) |
| ベクトルの絶対値 | |u| | O(N) |
| 行列とスカラーの掛け算 | kA | O(N2) |
| 行列と行列の足し算 | A+B | O(N2) |
| 行列と行列の掛け算 | AB | O(N3) |
| 逆行列 | A-1 | O(N3) |
表1の計算量のオーダーを求める簡単な方法は実際にコーディングするときに最低何重ループで書けるかを見ればよい。例えば、上の4つはループ1個で計算できるので、計算量のオーダーはO(N)。行列とスカラーの掛け算および行列と行列の掛け算は2重ループを使うので、オーダーはO(N2)。行列と行列の掛け算は一見、2重ループでよいですが、実際にコーディングしてみると、3重ループになるので、オーダーはO(N3)。逆行列はコーディングしたことがないと、なかなか創造できませんが、一番古典的な方法のガウス消去法ならO(N3)。
実際に行列関連の計算をすると解かりますが、O(N2)なら許容範囲です。O(N3)となると、Nがちょっとだけ増えるだけでたちまち計算がとんでもなく遅くなります。行列と行列の掛け算や逆行列を計算するときは注意しないといけません。下記のサンプルではO(N3)の計算を効率よく計算する方法をご紹介します。
