@comment $OpenXM: OpenXM/src/asir-doc/int-parts/datatype/dpoly.texi,v 1.1 2001/04/23 05:45:36 noro Exp $
@section 分散表現多項式

@example
typedef struct oDL @{   指数ベクトル
    int td;            全次数
    int d[1];          指数ベクトル本体
@} *DL;

typedef struct oMP @{   単項式リスト
    struct oDL *dl;    指数ベクトルへのポインタ
    P c;               係数
    struct oMP *next;  次の単項式へのポインタ
@} *MP;

typedef struct oDP @{   分散表現多項式
    short id;          識別子 (=O_DP)
    short nv;          変数の個数
    int sugar;         sugar の値
    struct oMP *body;  単項式リストへのポインタ
@} *DP;

struct order_pair @{    ブロックに対する項順序型指定
    int order;         項順序型
    int length;        ブロックの長さ
@};

struct order_spec @{   項順序型指定構造体
    int id;           項順序型指定識別子 
                   (0: primitive 項順序; 1:ブロック項順序; 2:行列による項順序)
    Obj obj;          Risa object として与えられた項順序型
    int nv;           変数の個数
    union @{                                 項順序型指定
        int simple;                         primitive 項順序識別子
        struct @{                            ブロック項順序型指定 
            int length;                     ブロック数
            struct order_pair *order_pair;  各ブロックの項順序型配列へのポインタ
        @} block;
        struct @{                            行列による項順序型指定
            int row;                        列数    
            int **matrix;                   行列本体
        @} matrix;
    @} ord;
@};
@end example
@noindent

分散表現多項式は, 多項式を, ある代数系を係数とする単項式の和として表現する. 
単項式は, 係数および項 (term) の積である. 項は変数の冪積である. 変数を固定
するとき, 項は, 指数のみを取り出した指数ベクトルで表せる. 上記構造体定義に
おいて, @code{DP} は分散表現多項式の wrapper, @code{MP} は各単項式の係数
および指数ベクトルを表す. また @code{DL} は指数ベクトルを表す. 

@code{MP}により単項式リストを構成する際, 項の順序を指定する必要がある. 
これは, 変数が固定された場合に, 項の集合の間にある条件を満たす全順序を
設定することにより行う. Risa においては, 項順序の指定を, 

@enumerate
@item 各変数と, 指数ベクトルの成分の位置の対応 (変数順序)
@item 指数ベクトルに対する順序の指定 (項順序型)
@end enumerate

により行う. 1. は単に変数をリストとして指定することにより行う. 2. は
3 つのカテゴリに分かれる. 

@enumerate
@item primitive 項順序型

これは, 次のような識別子により指定される型である. 

全次数つき順序は, まず全次数による比較を行う.

辞書式順序は, 指数ベクトルの先頭から比較を行い, 値が大きい方の順序を上と
する. 

逆辞書式順序は, 指数ベクトルの末尾から比較を行い, 値が小さい方の順序を上
とする.

@example
ORD_REVGRADLEX = 0   全次数逆辞書式順序
ORD_GRADLEX = 1      全次数辞書式順序
ORD_DLEX = 2         辞書式順序
@end example

@item ブロック項順序型

これは, 変数リストを幾つかのブロックにわけ, 各ブロックに primitive 項順序
型を指定して, 先頭のブロックから比較を行っていく型である. この型は, 

[[N1,O1],[N2,O2],...]

なるリストにより指定できる. ここで, Ni はブロック内の変数の個数, Oi は
そのブロックにおける primitive 項順序型である. 

@item 行列項順序型

指数ベクトル a, b に対し, ある条件を満たす行列 M により, M(a-b) の最初の
0 でない成分が正の場合に a の順序が上, として全順序が定義できる. この
順序型を, M により定義される行列項順序型とよぶ
@end enumerate

@code{DP} は sugar なるメンバを持つ. これは, 以下の規則により計算される. 

@itemize

@item 以下で説明する @code{ptod()} により生成された分散表現多項式の場合には全
次数に一致する.

@item 分散多項式に単項式をかけた場合には, sugar の値は多項
式の sugar に単項式の全次数を加えたものになる. 

@item 分散多項式の加減算においては, 結果の sugar の値は大きい方の値
となる.
@end itemize

この値は通常は呼び出した演算関数によりメンテナンスされるが, 独自に
分散多項式を生成した場合には, 上の規則により sugar の値を計算し
設定する必要がある. 

@subsection 分散表現多項式の生成
@example
#include "ca.h"

MKDP(n,m,d)  (macro; int n; MP m; DP d)
変数の個数が n である単項式リスト m から分散表現多項式を生成する. 
sugar の値は設定されず, この macro を実行したあとに設定する必要がある. 

NEWDL(d,n) (macro; int n; DL d)
長さ n の指数ベクトル d を生成する. d の全次数は 0, 各成分は 0 に初期化
される. 

NEWMP(m) (macro; MP m)
単項式リスト構造体 m を生成する. 

NEXTMP(r,c) (macro; MP r,c)
r を単項式リストの先頭とし, c を末尾とするとき, 末尾に単項式リストを
追加し, c をその単項式リストを指すようにする. r が 0 のとき, 
単項式リストが生成され, r および c はその単項式リストを指す. 

void initd(struct order_spec *spec)
項順序構造体 spec を現在の項順序として指定する. 

void ptod(VL vl, VL dvl, P p, DP *pr)
変数順序 vl の元で構成された(再帰表現)多項式 p を, 変数順序 dvl のもとで, 
現在設定されている項順序型に従って分散表現多項式に変換し *pr とする. 
@end example

@code{NEXTMP()} は単項式リストの末尾に単項式を追加していく場合に用いる. 
@subsection 四則
@example
#include "ca.h"

void addd(VL vl,DP a,DP b,DP *rp)
*rp = a + b

void subd(VL vl,DP a,DP b,DP *rp)
*rp = a - b

void muld(VL vl,DP a,DP b,DP *rp)
*rp = a * b

compd(VL vl,DP a,DP b)
以下の順序で比較
@end example
@noindent
@code{compd(vl,a,b)} は次のような順序づけによる. 

@enumerate
@item 先頭の単項式の指数ベクトルを, 現在設定される順序で比較. 
@item 指数ベクトルが等しい場合, 係数を多項式の順序で比較. 
@item 先頭の単項式が等しい場合, 1., 2. の比較を次の項以降に対して続ける. 
@end enumerate