Buchberger 算法

当前生成集可视为一组定向重写规则：遇到被某个首单项式整除的项就向下约简。两条规则的首项有共同倍数时，可能从同一单项式走出两条路径并留下不同结果。S-pair 把最小的这种分叉显式制造出来；若差异能约简为零，冲突已协调，若留下非零余式，就把它加入规则集修补缺口。

算法因此不是盲目枚举理想元素。它只追踪由首项重叠产生的有限类型冲突，并用单项式理想的 Noether 性证明修补不会无限发生。一个旧 pair 曾经约简为零，或曾以余式扩充 $G$ 后得到标准表示，其表示在以后扩大 $G$ 时仍有效。因此工作集耗尽时，全部最终 pair 都已获得判据所需的表示。pair 选择策略会显著改变中间规模，却保留这一正确性核心。

在 $K[x,y]$ 上取 lex 序 $x\succ y$，从

开始。首个 S-pair 给出

它不能被 $f_1,f_2$ 约简，故加入 $G$。随后 $\mathrm{LM}(g_3)=x$ 已整除 $f_2$ 的首项，pair $(f_2,g_3)$ 产生

加入 $g_4$ 后，其余 pair 均约简到零。对集合做 interreduction，$f_1,f_2$ 都可由 $g_3,g_4$ 表示，最终 reduced basis 为

这个过程还展示算法输出未必自动 reduced：停止条件只保证所有 S-pair 归零，旧的冗余元素仍可能留在 $G$ 中。

多元除法的余式在 $G$ 尚非 Gröbner 基时依赖除数次序，因此不同运行会产生不同中间多项式；正确性只要求每个选中的 S-pair得到某个合法完全余式。为避免遗漏，product criterion 和 chain criterion 只能在各自前提成立时删除 pair，不能因为“看起来相似”就跳过。

底环不是域时首系数不一定可除，算法需要环上的 Gröbner 基变体。精确有理数计算还会出现系数膨胀，常以模素数计算和 rational reconstruction 缓解。最坏情况下 Gröbner 基次数与规模可双指数增长，Buchberger 终止定理没有给出实用的多项式时间界；小例子的顺滑消元不能换成一般性能承诺。

pair 选择可以按最小总次数、糖度或预估矩阵规模排序；Buchberger 的两类经典判据能提前排除必然约简为零的 pair。对齐次输入时按次数处理便于控制层次，非齐次系统可用 homogenization 或 sugar strategy 模拟这一行为。无论采用哪种优化，最终仍应以 Buchberger criterion 或等价证书核验。

F4 算法理路F4 Gröbner 基算法F4 Gröbner basis algorithm · Faugère F4 algorithm以符号预处理收集一批临界对的约简子，并用稀疏 Macaulay 矩阵消元批量产生新首项。保留同一临界 pair 框架，却把一批 S-多项式的相互约简放进稀疏矩阵消元，从而复用公共单项式倍数。后来的 signature 算法还会追踪生成表示以预判零约简。Buchberger 算法因此既是可直接实现的基线，也是判断这些改进是否保持理想与首项不变量的参照。

得到基后，可进行理想成员判定、消元和零维求解；但算法只在选定单项式序下完成符号预处理，不负责选择数值稳定的根算法。若应用只需一个消元多项式，完整 reduced lex basis 可能过度计算，resultant、FGLM 次序转换或专用结构算法可能更合适。

可按实际处理的临界对报告成本。固定一对，令 $g=|G|$，$s$ 为本次除法中各基多项式、工作多项式与余式的项数上界，$n$ 为变量数，$L$ 为全部除法迭代数，包含把不可约首项移入余式的步骤。用有序稀疏项表并逐个扫描除数，假设所选单项式序的比较可用 $O(n+1)$ 次指数操作完成（例如 lex、grlex 或 grevlex），且域运算和指数算术均按单位成本计，构造 S-多项式及完成这次除法共用 $O((n+1)[s+L(g+s)])$ 次系数或指数操作；其中 $n+1$ 也覆盖零变量的常数情形。全程成本须累加实际临界对的开销；存储由保留的基与工作项记录，以及至多 $O(g^2)$ 个待处理 pair 决定。系数、指数的位长度，额外判据和最终 interreduction 的成本分别计入。