immut/term 设计

设计目标

TermPolynomial[A] 是分布形式的多变量多项式：一个扁平的、已排序的非零项列表。它是按顺序遍历多项式、进行整体多项式算术以及直接读取首项时所用的表示，同时保持为具有结构相等的不可变值。

数学背景

多项式 $f \in R[x_0, x_1, \dots]$ 是一个有限和 $f = \sum_{k=1}^{m} c_k x^{\alpha_k}$ ，其中指数向量 $\alpha_k \in \mathbb{N}^{(\infty)}$ 互不相同，系数 $c_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 通过三个步骤把任意输入变为这种形式：

按 compare 对输入的副本进行降序排序；
遍历已排序的列表，把每一段相等指数向量的系数相加；
仅当某一段的和非零时才保留它。

由于 compare 恰好在两个向量相等时返回 $0$ ，第 1 步之后相等的向量是相邻的。第 2 步按排序留下的任意顺序对一段求和，这无妨，因为 AddMonoid 加法满足结合律和交换律。第 3 步使 $2x_0 - 2x_0$ 消失。排序需要 $O(m \log m)$ 次比较，对长度为 $\ell$ 的向量，每次比较为 $O(\ell)$ 。

通过拼接与重新规范化实现算术

加法拼接两个项列表并调用 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$ 和 $\alpha_1$ 各应用一次相容性；两步都取等号当且仅当 $\alpha = \alpha_1$ 且 $\beta = \beta_1$ 。因此 $\alpha_1 + \beta_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。三者都通过一次遍历各项计算得出；没有任何缓存，因为列表在构造后从不修改。

正确性 / 不变量

规范形式。各项按 $\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$ 个乘积。当前版本保留了所有操作共用的、更简单的基于排序的规范化。
基于归并的加法对两个有序列表可以做到线性时间；出于同样的原因未予实现。
递归（嵌套单变量）表示 $R[x_0][x_1]\cdots$ 使多变量 Horner 求值变得自然，但会把布局绑定到某个变量顺序上，并使分布序下的首项难以查找。
升序。首项会是最后一个元素。降序会先显示最高次的部分，这符合多项式通常的书写方式。

边界

不提供除法、范式、S-多项式或 Gröbner 基，尽管单项式序可以支持它们。
不支持按键查找指数；需要按指数向量 get 时请使用 SparsePolynomial。
变量是位置式的；命名由 ContextPolynomial 负责。
没有 Compare 或 Hash 实例，因此项多项式不能作为有序映射或哈希映射的键。
指数为 UInt，溢出时回绕；系数遵循 A 的语义（整数回绕、浮点数舍入、按精确的 == 0 修剪）。