雨谷の日和

過去12年で1,600を超えるアニメの第1話だけは見続けた僕のお勧めアニメがハズレなはずがない

行列式計算の色々なアルゴリズム2

kp氏より、ここの2004.06.27付けの記述にコメントを頂いています。→「行列式

雨谷の日和の行列式計算の色々なアルゴリズムで言及されているように、行列式の計算として掃き出し法が速度に対して有効なのは確かなのですが、精度が落ちる可能性があるというのが問題のような気がします。


(略)


ということで、割り算をしない、情報落ちを心配しなくていいそれなりに速いアルゴリズムにもそれなりの需要はあるんじゃないでしょうか。

なるほど。
ここで私がやっているような余因子展開を利用した計算方法は計算回数が次元数の階乗(n!)で増えますが、掃き出し法だと次元数の3乗(n^3)程度で済むため、大きな次元数においては圧倒的に有利です。ただ、割り算が発生する分、確かに誤差は避けられないでしょうね。
画像処理や数値計算などの用途だと、ある程度の微小な誤差は許容できる場合が多いので、掃き出し法の誤差を気にしなければならない場面はほとんど無いような気はします。ただ、行列式の計算はそればかりというわけではないので、ご指摘のように原理的に誤差の生じないアルゴリズムにも意味はありますね。


納得致しました。今やっている比較(Borland Cでの比較も含む)を一通り終えたら、今度は行列式の計算の高速化についてもネタにしてみようかと思います。


ちなみに、今回の比較で掃き出し法を選択しなかった理由は、以下の三点です。

  • 高校数学の知識があれば理解できる余因子展開に比べ、プログラムの記述が見た目難解であった。
  • 計算が速く終わり過ぎるので、有意な差を見るには巨大な次元数のサンプルデータを用意する必要があった。
  • CとJavaでは、double(もしくはfloat)の取り扱いが異なっているのではないかと懸念した。

まあ、既に色々と他の方からもご指摘頂いている様に、CとJavaの比較に適していたかというと疑問も残るわけですが、メモリに関する話題や再帰呼び出しのことなど、色々と実験できたので個人的には面白かったです。