行列式の計算

いま、行列計算ライブラリで使っている行列式の計算方法は「余因子行列に展開」する方法だけど、いまいち遅い気がするので改良しようとしているんだけど、どうするのがいいんだろう?

方法1 定義どおりの計算

再帰的な呼び出しをしない分、関数のオーバーロードは減る。
ただし、置換の組合せの数は階乗で増えていくため、次数が増えるとループ数は半端じゃなくなる。

INT_MAX (32bit)を越えない最大の n! は n = 12 だってさ。以外に小さいでしょ。

方法2 余因子行列に展開

余因子行列で展開すると余因子行列を貯めるメモリが必要なので、大量のメモリのオーバーヘッドを生じる。
ただし、行列自身は変えないので、工夫すればオーバーヘッドは減らせる。

例として5次の行列式を求めるときのオーバーロードの様子を見てみましょう。

1. 5次の Deteminant();
2. 5 × 4次の Determinant();
3. 5 × 4 × 3次の Determinant();
4. 5 × 4 × 6個のかけ算 (サラスの公式)
5. = 120 個のかけ算 + オーバーロード (+ メモリ処理)

なので、方法1より遅いことがわかりますね。

方法3 掃き出しをしてから展開

0の項を omit することで計算を省略する方法。

1行掃き出せば、1つの余因子行列の行列式だけ計算すればよいが、行列が変わるので、新たにメモリを食ってしまう。

同じように5次の行列式の計算の様子を見てみることにしますか。

1. 階段行列変形 (4×5回(以上)の列基本変形)
2. 4次の Determinant();
3. 3次の Determinant();
4. 2次の Determinant();
5. = 100回ぐらいのかけ算 + メモリ処理 (行列のコピー)

まあ、なにごとも実験してみることも大切ですよね。