読者です 読者をやめる 読者になる 読者になる

雨谷の日和

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

分数での掃き出し法による行列式計算1

ボヤキ - 技術

そういえば去年の今ごろは行列式の計算のプログラムをちまちまちまちまと作ってみていて、最後の方に「行列式計算の色々なアルゴリズム2」とか言いつつ、そのまま色々と忙しくなってしまって放り出してしまっているわけですが。

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

という部分については色々とその後も考えてみてはいました。
ただ、掃き出し法による行列式計算は、誤差は出るもののかなり高速に計算結果が出てくるので、情報落ちをしないアルゴリズムの高速化をごちゃごちゃ考えてもあまり実りはないなぁという結論に、個人的には落ち着いています。
ところで、掃き出し法の計算は通常、浮動小数点型(doubleとか)で行うんですが、これを分数で行うことも理論上は可能ではあります。
ということで、そういう分数での計算のプログラムをちまちまと作ってみる日記をこれから休み休みやってみようかなぁと思っていたり思っていなかったりで。
今回はC言語との比較とかそういう話ではなくて、Java のプログラムをちまちま作る様を何気につらつら書くということを目的とします。
そんな日記何の役に立つのであろうかとかいう疑問はこの際放置ということで。


まずは、ここに載っているC言語でのプログラムを参考に、double型での掃き出し法による行列式計算のプログラムを書いてみました。
こんな感じ→ソースコード


詳しい解説はまあ、元ネタのサイト方を読んで頂ければ良いとして、これを実際に実行してみると以下のような感じの結果になります。

result: 4.892616779999999E8

Flat profile of 0.09 secs (6 total ticks): main

  Interpreted + native   Method
 16.7%     1  +     0    java.lang.String.hashCode
 16.7%     1  +     0    Total interpreted

  Thread-local ticks:
 50.0%     3             Class loader
 33.3%     2             Compilation


Global summary of 0.10 seconds:
100.0%     8             Received ticks
 12.5%     1             Compilation
 37.5%     3             Class loader



ちなみに同じ環境で、以前のベタなソースコード(をちょっと改変したもの)を実行してみると、こんな感じに。

result: 489261678

Flat profile of 17.55 secs (903 total ticks): main

  Interpreted + native   Method
  0.1%     1  +     0    java.lang.String.hashCode
  0.1%     1  +     0    Total interpreted

     Compiled + native   Method
 99.6%   899  +     0    org.dmwp.math.DeterminantTestExpand.calcExpand
 99.6%   899  +     0    Total compiled

  Thread-local ticks:
  0.2%     2             Class loader
  0.1%     1             Compilation


Flat profile of 0.02 secs (1 total ticks): DestroyJavaVM

  Thread-local ticks:
100.0%     1             Blocked (of total)


Global summary of 17.57 seconds:
100.0%   905             Received ticks
  0.1%     1             Compilation
  0.2%     2             Class loader



以前より遅くなっているのは、テスト環境が変わっているからで、以下のような構成での実測です。

まあ、要するに掃き出し法とベタな展開とだと、200倍くらいの性能差が出てくるわけでして。
さて、今後は掃き出し法のアルゴリズムを分数を使ったものに書き換えて行くわけですが、しかしまずは分数をどうやって取り扱ったら良いのかという、そこら辺から考えていくことになるんではないかと思っていたりします。
気の長い話になるかも。まあ、休み休み書いていきます。