From: keiju@... (=?ISO-2022-JP?B?GyRCQFBETTc9PHkbKEI=?=)
Date: 2005-11-25T17:49:32+09:00
Subject: [ruby-dev:27820] Re: Matrix class is broken without mathn

けいじゅ＠いしつかです.

In [ruby-dev:27810] the message: "[ruby-dev:27810] Re: Matrix class is
broken without mathn", on Nov/22 16:59(JST) Shin-ichiro HARA writes:

>原です。

>>ただ, Rational+quo式 は, detを計算すると勝手にrational.rbをrequireして
>>しまうので, det前と後でquoを用いているメソッド(inv等)の振る舞いが変わっ
>>てしまうことに気が付きましたので, やはりまずいかなぁ. と思っていたとこ
>>ろでした(^^;;
>
>そうですね。それはありますね。

です.

>（Rational+quo式ではなく）quo式でも、rationalをrequireしているかどうか
>でdetの戻り値が変わってしまうという仕様なので、それはそれで気持ちが悪い
>ですね。

まあ, rationalをrequireしているので, 結果が変わってもしょうがないとい
うか, それを意図していることがほとんどだと思います.

>しかし、意識して成分をRational化あるいはFloat化しておけばその現
>象は避けられるし、何より何も意識していなかった場合でも、ひどい値を返す
>ことはない、というのが有り難いと思います。

クラスは異なっていても, 値としてはあっていますしね(^^;;

>>>determinant         : 4.278sec.
>>>determinant_e       : 0.329sec.
>
>他のマシンで試したら5倍程度の差でした。CPUによるみたいです。

それでも, ずいぶん違いますね...

>>ちなみに, determinant_e の eは何の省略形です?
>
>electric、、、違う。アルゴリズムがElementary divisor（単因子）を求め
>るところに出てくるものの一部なので。Exactという気もしたし、、、
>名前はいいのがあれば代えてしまってください。

原作者の名前ということで, このままでいいのでは? 

>>ただ, 行列の要素にはいろいろなものが入る可能性があるので, det_eがちゃ
>>んと動作する条件を明確にした方がよいかと思います.
>
>ちゃんと動作するのは、IntegerかRationalの行列です。

それだけではないですよね? 多項式環などでも計算できそうですが?

>オリジナルのdetと最も違うのは、成分が全てIntegerである行列に対し必ず
>Integerを返す所です。Floatが混じると無限ループに陥る可能性があります。

うーむ. これはまずいかなぁ... というか, Floatが入っていると結果も間違っ
ていますよね? 

もう一つのメイルもマージしました:

In [ruby-dev:27816] the message: "[ruby-dev:27816] Re: Matrix class is
broken without mathn", on Nov/25 00:08(JST) Shin-ichiro HARA writes:

>原です。

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

(中略)

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

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

たぶん, そのとおりだとおもいます. 

やるんだったら, いろいろと懲りたい人用に, アルゴリズムとか構造を変えら
れるな行列クラスを別に用意した方がよいと思います.

さらに, もう一つのメイルもマージしました:

In [ruby-dev:27817] the message: "[ruby-dev:27817] Re: Matrix class is
broken without mathn", on Nov/25 00:24(JST) Shin-ichiro HARA writes:

>原です。

>>整数行列の逆行列が整数行列になることがあるからですか?
>>そこまでは考えなくてよいんじゃないでしょうか? 
>
>そうですよね。特殊なケースまでmatrix.rbで面倒を見る必要はな
>いと私も思います。

>、、、とは言え、もし実装したらどうなるか興味が沸いたので、やっ
>てみました。

(中略)

>他にも単因子を求めるアルゴリズムとか作ってみたのですが、こう
>なるとmatrix.rbじゃなくてmatrix-i.rbとか別ファイルにしたほう
>がいいかもしれません。

まあ, これも, 『アルゴリズムとか構造を変えられるな行列クラス』の方で
やってくださいって感じですか...

最後に:

>実際matrix.rbでどれを採用するかは石塚さんの判断に任せたいと思います。

今のをまとめると:

* determinantは, quo を用いたものにする. 
  標準では:

    aMatrix.det => Float

  require "rational" した状態だと:

    aMatrix.det => Rational

* もう一つ, determinant_e を導入する. アルゴリズムは 原さんのdeterminant_625

* rank も, quo を用いたものにする.
* rank_e を追加導入する

他に異議のある方がいなければ, 上記のようにしたいと思います.

__
---------------------------------------------------->> 石塚 圭樹 <<---
---------------------------------->> e-mail: keiju@ishitsuka.com <<---