稀疏多项式表示

稀疏表示不铺设从 $0$ 到最高次数的全部刻度，而只记录真正出现的坐标。对 $1+x^{{10}^9}$，输入的数学信息只有两个系数和两个指数；按十亿长度扫描既没有增加正确性，也没有揭示新结构。把规模记为项数 $t$ 后，求值可逐项快速幂，加法可像合并两个排序表那样进行，多元系统中的一个单项式则自然成为“指数向量加系数”的记录。

节省空间的代价是失去常数时间的任意系数定位。查找 $x^k$ 的系数需要二分、树索引或哈希；乘法会产生 $t_f{t}_g$ 个候选指数和，随后还要合并碰撞项。稀疏算法因此常把主要工作放在支持集的组合结构上，而稠密表示理路稠密多项式表示Dense polynomial representation · Coefficient-vector polynomial representation按次数连续保存从常数项到最高次项全部系数的规范多项式编码。把主要工作放在连续次数范围上。二者的复杂度参数不同，不能只比较同一个大 $O$ 符号中的字母。

取

各自只有三项。逐项相乘得到九个候选项；按指数合并后

其中 $x^{1000}$ 的系数来自 $-2x^{1000}+x^{1000}$，说明“生成候选项”与“得到规范结果”是两个不同阶段。若在特征为 $3$ 的域上计算，$3x^{1007}$、$-9x^{14}$ 与 $6x^7$ 又全部消失；合并之后删除零项是代数正确性的一部分，而不是可选的压缩。

稀疏输入也可能迅速稠密化。在有理数域上，几何和

每个因子有 $m+1$ 项，乘积在 $0$ 到 $2m$ 的每个次数上都非零；若仍用树结点逐项维护，比较与分配成本会压过数组卷积。相反，$(1+x^D{)}^k$ 只有 $k+1$ 个可能次数，在 $D$ 极大而 $k$ 较小时继续使用稀疏表更合理。若两个输入分别有 $t_f,t_g$ 项，输出至多有 $t_f{t}_g$ 项；每个输出指数都来自一个输入指数和。这个二次上界可以达到：$\sum _{i=0}^{t-1}{x}^{it}$ 与 $\sum _{j=0}^{t-1}{x}^j$ 各有 $t$ 项，其乘积为 $\sum _{k=0}^{t^2-1}{x}^k$。另一方面，指数碰撞与系数抵消都可能使实际输出更少，因此不能把输出项数无条件估成 $O(t_f+t_g)$。

稀疏表示适合超高次数少项式、符号展开中的中间表达式和多元 Gröbner 基计算。多元算法频繁询问首单项式、最小公倍单项式与可整除项，因此有序项表、堆和哈希表常被组合使用：哈希负责合并相同指数，优先结构负责按单项式序取出当前最大项。F4 算法理路F4 Gröbner 基算法F4 Gröbner basis algorithm · Faugère F4 algorithm以符号预处理收集一批临界对的约简子，并用稀疏 Macaulay 矩阵消元批量产生新首项。进一步把许多稀疏项对齐成 Macaulay 矩阵的列，说明“多项式稀疏”与“矩阵消元时仍稀疏”是两个需要分别测量的事实。

表示还影响输入规模的理论定义。若指数以二进制编码，$x^{2^n}-1$ 的文本长度是 $O(n)$，而把它展开成连续系数需要指数空间；因此某个对次数 $D$ 多项式时间的稠密算法，对稀疏编码长度未必是多项式时间。反过来，许多快速变换算法要求完整系数向量，先把项表稠密化可能正是合适的预处理。可靠实现通常根据预计输出密度设阈值切换表示，并在切换时重新规范化，而不是让两种编码在同一对象中长期并存。