児玉 です.

From: IKEGAMI Daisuke <daisu-ik / is.aist-nara.ac.jp>
Subject: [ruby-math:00367] Re: one/zero for algebraic class
Date: Fri, 08 Sep 2000 15:59:34 +0900
Message-ID: <200009080659.AA02727 / rho.aist-nara.ac.jp>

> いけがみです.
> 
> 今,次の本を手元に置いて読んでいます.
> 
> Algorithms for Computer Algebra,
> Keith O. Geddes, Stephen R. Czapor, George Labahn.,
> Kluwer Academic Publisher, ISBN 0-7923-9259-0
> 
> この本は多項式の実装についてページをいくらか割いていて,
> リンクトリストで実装する方法と,巾と係数の表を実装する方法が載ってました.
> Ruby で実装するのにどちらが向いているかわかりませんが,
> 後者を試してみました.
> 巾(Arrayで実装)を key とし,係数(任意のObjectで実装)をvalueとする
> 多項式の実装はうまく動きそうです.
> # 1 変数の多項式では四則演算+整数巾はうまく動きました.

僕の実装で云うと以下のように対応すると思います.
リンクトリストで実装する方法:  PolynomialM 多変数多項式クラス
巾と係数の表を実装する方法:    Polynomial  1変数多項式クラス


> この場合 "x"という文字シンボルを別クラスで扱えるので,
> 
> > できれば, 以下も受け付けるように書きたい.
> > g = 3*x**2 + x  + 1;
> 
> も受け付けます.

上の x 自体が多項式で, 係数環 K の値を内部に持っていると思いますが,
係数環 K が 整数値 1 を含まないような場合,
(つまり 整数環の拡大になっていないとき)
ここが問題になっていたわけ.


> # Array を key とするのはやめましょう,と Ruby 本に書いてますが,
> # hashを多項式の巾の multi-degree とすると妥当な表現のような気がします.
> 
> あと,Ahoらの超有名なアルゴリズム本も目を通したんですが,
> 1変数多項式の実装に配列を内部表現として用いるのは,
> 実装が簡単になり,小さな多項式の四則演算が高速に行える半面,


> 副作用として多変数への拡張が複雑になるのと,

(a)  K[x,y,z...] のように多次元配列で一気に書き下す方法と
(b)  ((K[x])[y])[z]... のように
多項式係数多項式係数多項式.... と1変数多項式を積み重ねる方法があります.

(a) はあらかじめ 次元数が分かっていれば簡単.

複雑というのは (b) を指していると思うけど,
(b) の1変数多項式を積み重ねる方法は
単に係数環が多項式になっているだけなので,
Ruby だと 普通に1変数多項式を実現すると,
そのままで自然に実行できると思います.

> x^1000+1 のような「疎」な多項式に対する記憶量が増えるようです.

多変数の場合特に 疎 になる傾向があるようです.


> 1変数多項式環の実装を多変数多項式環と別にするメリットは,
> 他にもなにかあるでしょうか?
> たとえば,体上の1変数多項式環はユークリッド整域で,
> 2変数以上の多項式環が持ってない良い性質を有していますが,
> 実装が違うことによるメリットは何でしょうか.

次のトレ−ドオフじゃないでしょうか?

(1). 前もって変数の種類(の上限)が決まっていれば
   多次元配列の実装が手軽. (特に1変数の場合)
   速度も早い可能性がある.
(2). 配列による実現の場合,
   変数が多くなると疎になる傾向があり記憶量で不利.

-- 
K.Kodama(kodama / kobe-kosen.ac.jp)