From: Shin-ichiro HARA <sinara@...>
Date: 2005-11-25T00:08:45+09:00
Subject: [ruby-dev:27816] Re: Matrix class is broken without mathn

原です。

In [ruby-dev:27810]
>>オリジナルdetと形がすごく似ているので, det_625 の方がよいかなぁ...
>>って感じです.
>
>そうですね。だいたい一カ所変えただけですからね。それがなぜか一番速
>いみたい。

もう少し調べてみると det_e も det_625 も大きい行列に対してち
ょっとした成分の差で極端に遅くなる現象が見られました。多分、
互除法で係数の爆発が起こり、Begnumの領域に入ったんだと思いま
す。これは、軸を選択することによって防げるようです。次のアル
ゴリズムは結構がんばります。

class Matrix
  def determinant_e2
    size = row_size
    a = to_a
    det = 1
    d = 0
    while d < size
      clean = true
      if i = (d...size).find{|x| !a[x][d].zero?}
        i = (i...size).find_all{|x| !a[x][d].zero?}.
            min{|x, y| a[x][d].abs <=> a[y][d].abs}
        if i > d
          a[i], a[d] = a[d], a[i]
          det *= -1
        end
        (d + 1...size).each do |i|
          next if a[i][d].zero?
          clean = false
          q = a[i][d] / a[d][d]
          (d...size).each do |j|
            a[i][j] -= a[d][j] * q
          end
        end
        if clean
          det *= a[d][d]
          d += 1
        end
      else
        return 0
      end
    end
    det
  end
end

普通Floatの掃き出し法では、誤差を小さくするために、軸はなる
べく大きい成分に取るのでが、整数演算では誤差がないので、軸を
なるべく小さい成分に取ることによって、小さい余りが出るように
した方がいいみたいです。ただし、小さい行列ではdet_625の方が
速いです。

実際matrix.rbでどれを採用するかは石塚さんの判断に任せたいと
思います。確かに凝り出すと切りがないので、標準ライブラリであ
まりこってりしたアルゴリズムを使っても仕方ないですし。