immut/term の設計

設計目標

TermPolynomial[A] は 分配形式 の多変数多項式、すなわち非ゼロ項の平坦で整列されたリストです。多項式を順序どおりに走査する場合、多項式全体の算術演算、先頭項を直接読む場合に適した表現であり、同時に構造的等価性を持つイミュータブルな値でもあります。

数学的背景

多項式 $f \in R[x_0, x_1, \dots]$ は、互いに異なる指数ベクトル $\alpha_k \in \mathbb{N}^{(\infty)}$ と非ゼロ係数 $c_k$ による有限和 $f = \sum_{k=1}^{m} c_k x^{\alpha_k}$ です(core の設計 を参照)。ExponentVector::compare の単項式順序 $\prec$ を固定します。$\alpha_1 \succ \alpha_2 \succ \cdots \succ \alpha_m$ となるように項を並べたものが $f$ の 正規項リスト です。最初の項 $c_1 x^{\alpha_1}$ が先頭項 $\operatorname{LT}(f)$、$\alpha_1$ が先頭単項式、$c_1$ が先頭係数です。

$\prec$ は全順序で $\alpha_k$ は互いに異なるので、整列したリストは存在して一意です。したがって

$$f = g \iff \text{the canonical term lists of } f \text{ and } g \text{ are equal}.$$

設計上の判断

正規形: 整列済み、マージ済み、ゼロなし

選択. TermPolynomial は正規項リストそのものを永続的な @immut/vector.Vector に格納します。導出された Eq は格納されたリストを比較し、上の同値性によりこれは多項式の等価性になります。from_terms は任意の入力を 3 つの手順でこの形にします:

1. 入力のコピーを compare で降順に整列する。
2. 整列したリストをたどり、等しい指数ベクトルが連続する各区間の係数を加算する。
3. 和が非ゼロの区間だけを残す。

compare はちょうど等しいベクトルに対して $0$ を返すので、手順 1 の後では等しいベクトルは隣接しています。手順 2 は整列後に残った順序のまま区間を合計しますが、AddMonoid の加法は結合的かつ可換なので問題ありません。手順 3 によって $2x_0 - 2x_0$ が消えます。整列には $O(m \log m)$ 回の比較がかかり、長さ $\ell$ のベクトルでは各比較が $O(\ell)$ です。

連結と再正規化による算術演算

加算は 2 つの項リストを連結して from_terms を呼び出します。乗算は $mn$ 個の積 $(\alpha_i + \beta_j,\ c_i d_j)$ をすべて作って from_terms を呼び出します。どちらも教科書どおりの定義に上記の正規化を続けたものなので、その正しさは from_terms の正しさに帰着します。コストはそれぞれ $O((m+n)\log(m+n))$ 回と $O(mn \log(mn))$ 回の比較です。

スカラー倍と符号反転は順序を保つ

scale(γ, c) は各項 $(\alpha, a)$ を $(\alpha + \gamma, ac)$ に写し、並べ直しは行いません。単項式順序では写像 $\alpha \mapsto \alpha + \gamma$ が狭義単調増加なので、これは正当です:

$$\alpha \succ \beta \;\Longrightarrow\; \alpha + \gamma \succ \beta + \gamma$$

(両立性。core の設計 で導出しています)。したがって狭義降順の入力からは狭義降順の出力が得られ、特に異なる指数は異なったままです。ただし $R$ が零因子を持つ場合は係数 $ac$ がゼロになり得る(Int では $2^{16} \cdot 2^{16} = 0$)ため、そのような項は取り除かれます。結果は $O(m)$ 回の項演算で正規形になります。符号反転は指数を保つので、取り除く処理だけを行います。

積の先頭項

項を降順に格納すると先頭項は to_terms()[0] になり、単項式順序によって先頭項は乗法的になります。$\alpha_1$ と $\beta_1$ をそれぞれ $f$ と $g$ の先頭単項式とします。任意の項 $\alpha \preceq \alpha_1$ と $\beta \preceq \beta_1$ について、

$$\alpha + \beta \;\preceq\; \alpha_1 + \beta \;\preceq\; \alpha_1 + \beta_1 ,$$

ここでは両立性を $\beta$ について 1 回、$\alpha_1$ について 1 回適用しています。どちらの段階も等号が成り立つのは $\alpha = \alpha_1$ かつ $\beta = \beta_1$ のときに限ります。したがって $\alpha_1 + \beta_1$ はちょうど 1 組の項からしか生じず、$fg$ におけるその係数は $c_1 d_1$ であり、

$$\operatorname{LT}(fg) = \operatorname{LT}(f)\operatorname{LT}(g) \quad \text{whenever } c_1 d_1 \neq 0 .$$

これが次数付き順序を除算型のアルゴリズムで有用にする性質であり、この表現が任意のキー順序ではなく単項式順序を採用している理由です。

項ごとの評価

eval(values) は $\sum_k c_k \prod_i a_i^{\alpha_{k,i}}$ を計算し、各累乗は二分累乗法で求めます。係数環が可換であれば、これは評価準同型 $\mathrm{ev}_a : R[x_0, \dots, x_{n-1}] \to R$, $x_i \mapsto a_i$ です。dense の設計 と同じ単項式による議論で、これは環準同型になります。コストは $O\bigl(\sum_k \sum_i \log \alpha_{k,i}\bigr)$ 回の係数の乗算です。

評価点は少なくとも arity() 個の値を与える必要があります。項が使う各変数についてインデックス $i$ が読まれるためです。配列が短い場合、eval は中断 (abort) し、eval_checked は None を返します。アリティを超える値が読まれることはありません。

形状と能力のメタデータ

arity は格納されている最も長い指数ベクトルの長さ、total_degree は項の次数の最大値、term_count はリストの長さであり、これらを合わせて PolynomialShape::Multivariate を構成します。3 つとも項を 1 回走査して計算します。リストは構築後に変更されないため、何もキャッシュしません。

正しさ / 不変条件

• 正規形. 項は $\prec$ について狭義降順で、すべての係数は非ゼロです。すべてのコンストラクタと演算が、from_terms によって、または scale と neg については順序保存の議論によって、この性質を再確立します。
• 値の等価性 は多項式の等価性です。
• 先頭項. to_terms()[0] は $\operatorname{LT}(f)$ であり、係数の積が非ゼロであれば $\operatorname{LT}(fg) = \operatorname{LT}(f)\operatorname{LT}(g)$ です。
• one() は、A において $1 = 0$ である場合に限りゼロ多項式です。
• 累乗. pow(e) は $O(\log e)$ 回の乗算を行い、pow(0) は one() です。
• 計算量($m$ 項と $n$ 項): from_terms は $O(m \log m)$、+ は $O((m+n)\log(m+n))$、* は $O(mn \log(mn))$、scale、neg、arity、total_degree は $O(m)$、eval は $O(\sum_k \sum_i \log \alpha_{k,i})$。各比較のコストは $O(\ell)$ です。

採用しなかった代替案

• ヒープによる乗算(整列済みの $m$ 本のストリーム $\alpha_i + \beta_1, \alpha_i + \beta_2, \dots$ を優先度付きキューでマージする方法)を使えば、乗算を $O(mn \log \min(m, n))$ に下げ、$mn$ 個の積すべてを実体化せずに済みます。現在の版では、すべての演算が共有するより単純な整列ベースの正規化を採用しています。
• マージによる加算 は 2 つの整列済みリストに対して線形時間で行えますが、同じ理由で実装していません。
• 再帰的(入れ子の一変数)表現 $R[x_0][x_1]\cdots$ は多変数の Horner 評価を自然にしますが、配置が変数の順序に縛られ、分配順序における先頭項を求めるコストが高くなります。
• 昇順. 先頭項が最後の要素になってしまいます。降順にすると最高次の部分が最初に来るため、多項式の通常の書き方に一致します。

境界

• 単項式順序はそれらを支えうるものの、除算、正規形、S 多項式、グレブナー基底は提供しません。
• キーによる指数検索はありません。指数ベクトルによる get が必要な場合は SparsePolynomial を使ってください。
• 変数は位置で指定します。名前は ContextPolynomial の役割です。
• Compare と Hash のインスタンスはないため、項多項式を整列マップやハッシュマップのキーにすることはできません。
• 指数は UInt でありオーバーフロー時にラップアラウンドします。係数は A の意味論に従います(整数のラップアラウンド、浮動小数点数の丸め、厳密な == 0 による切り詰め)。