[人工智能] Groebner Basis

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 人工智能 -> Groebner Basis -> 正文阅读

[人工智能]Groebner Basis

本文参考书籍：Ideals, Varieties, and Algorithms (4th ed.) [Cox, Little & O’Shea 2015-06-14]

Affine Variety

给定域 $k$ ，令 $f_1,\cdots,f_s$ 是多元多项式环 $k[x_1,\cdots,x_n]$ 上的元素，定义仿射簇：
$V(f_1,\cdots,f_s):=\{(a_1,\cdots,a_n) \in k^n | f_i(a_1,\cdots,a_n)=0,\forall 1\le i \le s\}$
仿射簇就是方程 $f_1=\cdots=f_s=0$ 的所有解的集合。如果 $k = R$ ，那么仿射簇可以在 $R^n$ 中绘画出来；比如圆锥截线（椭圆曲线、抛物线、双曲线）

如果给定方程组 $f_1=0,\cdots,f_s=0$ ，容易知道 $h_1f_1+\cdots+h_sf_s=0,h_i\in k[x_1,\cdots,x_n]$ 。也就是说，理想 $<f_1,\cdots,f_s>$ 中的所有元素都在 $V(f_1,\cdots,f_s)$ 上“消失”了。

根据Hilbert Basis Theorem，仿射簇仅与理想有关（与方程组无关），即如果 $<f_1,\cdots,f_s>=<g_1,\cdots,g_t>=I$ ，那么 $V(f_1,\cdots,f_s)=V(g_1,\cdots,g_t)=V(I)$

Ideal of V

令 $V$ 是仿射簇，定义仿射簇的理想：
$I(V)=\{f\in k[x_1,\cdots,x_n] | f(a_1,\cdots,a_n)=0,\forall (a_1,\cdots,a_n) \in V\}$
易知， $\subseteq k[x_1,\cdots,x_n]$ 是理想。

令 $V, W$ 都是 $k^n$ 中的仿射簇，那么

$\subseteq W$ 当仅当 $\supseteq I(W)$
$V = W$ 当仅当 $I (V) = I (W)$

如果域 $k$ 是无限的，那么 $I(k^n)=\{0\}$ ，只包含零多项式。

Orderings on the Monomials in $k[x_1,\cdots,x_n]$

指数（Exponent，形如 $\alpha=(\alpha_1,\cdots,\alpha_n)\in Z_{\ge0}^n$ ），单项式（Monomial，形如 $x^\alpha$ ），系数（Coefficient，形如 $\in k$ ），项（Terms，形如 $\cdot x^\alpha$ ）

单项式顺序（monomial ordering）是 $Z_{\ge0}^n$ 上的关系 $>$ ，它满足如下条件：

是全序关系，任意的一对 $x^\alpha,x^\beta$ ，都一定有 $>, =, <$ 关系之一。良序关系自然导致了传递性。
如果 $\alpha>\beta$ ，对于 $\forall \gamma\in Z_{\ge0}^n$ ，都有 $\alpha+\gamma>\beta+\gamma$
是良序关系，如果 $\subseteq Z_{\ge0}^n$ 是非空子集，那么 $\exist\alpha \in A$ ，使得 $\ { α } \forall \beta \in A \backslash \{\alpha\}$ ，都有 $\beta>\alpha$

字典序：令 $\alpha,\beta\in Z_{\ge0}^n$ ，当向量差 $\alpha-\beta$ 的最左边的非零分量为正数，记做 $\alpha >_{lex} \beta$

反字典序：令 $\alpha,\beta\in Z_{\ge0}^n$ ，当向量差 $\alpha-\beta$ 的最右边的非零分量为负数，记做 $\alpha >_{revlex} \beta$

分级字典序：令 $\alpha,\beta\in Z_{\ge0}^n$ ，记 $\alpha >_{grlex} \beta$ ，如果满足 $|\alpha|=\sum\alpha_i > |\beta|=\sum\beta_i$ 或者 $|\alpha|=|\beta|,\alpha >_{lex} \beta$

分级反字典序：令 $\alpha,\beta\in Z_{\ge0}^n$ ，记 $\alpha >_{grevlex} \beta$ ，如果满足 $|\alpha|=\sum\alpha_i > |\beta|=\sum\beta_i$ 或者 $|\alpha|=|\beta|,\alpha >_{revlex} \beta$

在固定单项式顺序 $>$ 下，给定 $f=\sum_\alpha c_\alpha \cdot x^\alpha$ ，定义：

$multideg(f):=max\{\alpha\in Z_{\ge0}^n | c_\alpha \neq 0\}$ ，简写为 $d e g (f)$
$LC(f):=c_{deg(f)} \in k$ ，前导系数
$LM(f):=x^{deg(f)}$ ，前导单项式
$LT(f):=LC(f)\cdot LM(f)$ ，前导项

易知， $d e g (f g) = d e g (f) + d e g (g)$ ， $deg(f+g)\le max(deg(f),deg(g))$ ；若 $deg(f)\neq deg(g)$ 则 $d e g (f + g) = m a x (d e g (f), d e g (g))$

Division Algorithm

令 $>$ 是 $Z_{\ge0}^n$ 上的单项式顺序，令有序 $s$ 元组 $F=(f_1,\cdots,f_s) \in (k[x_1,\cdots,x_n])^s$ ，对于任意 $\in k[x_1,\cdots,x_n]$ ，都可以写成 $f=q_1f_1+\cdots+q_sf_s+r$

这种表示不唯一。交换 $F$ 元素的顺序，商 $q_i$ 会改变，余数 $r$ 也可能不同。对于有序 $s$ 元组 $F$ ， $f$ 除以 $F$ 的余数记做 $\overline f^F$

monomial ideal

单项理想：给定（可能无限大）子集 $A\subseteq Z_{\ge0}^n$ ，令 $I=<x^\alpha | \alpha \in A>$ ，它包含所有的有限和 $\sum_{\alpha\in A}h_\alpha x^\alpha$ ， $h_\alpha \in k[x_1,\cdots,x_n]$

若单项式 $x^\beta \in I$ ，那么 $\exist \alpha \in A,x^\alpha|x^\beta$ ，易知 $\beta \in \alpha+Z_{\ge0}^n$

关于单项理想的三个等价表述：

$\in I$
$f$ 的每一项都属于 $I$
$f$ 是 $I$ 中单项式的 $k$ 上线性组合

Dickson’s Lemma：令 $I=<x^\alpha | \alpha \in A> \subseteq k[x_1,\cdots,x_n]$ 是单项理想，那么可以写成 $I=<x^{\alpha_1},\cdots,x^{\alpha_s}>$ ，其中 $\alpha_1,\cdots,\alpha_s \in A$ ，即 $I$ 是由有限个单项式生成的。

最小基：单项理想 $I$ 存在唯一的一组基 $\{x^{\alpha_1},\cdots,x^{\alpha_s}\}$ ，满足 $x^{\alpha_i} \nmid x^{\alpha_j},\forall i \neq j$

Hilbert Basis Theorem

令 $\subseteq k[x_1,\cdots,x_n]$ 是任意的非零理想，确定单项顺序，可以定义：

$\ { 0 } , L T ( f ) = c x α } LT(I):=\{cx^\alpha | \exist f \in I \backslash \{0\},LT(f)=cx^\alpha \}$
$\in LT(I)>$

如果 $I=<f_1,\cdots,f_s>$ ，那么 $<LT(f_1),\cdots,LT(f_s)> \subseteq <LT(I)>$ ，并且可以是严格大。

$< L T (I) >$ 是单项理想，根据Dickson’s Lemma它是有限生成的。如果 $<LT(I)>=<LT(g_1),\cdots,LT(g_t)>$ ，其中 $g_1,\cdots,g_t \in I$ ，那么可以声明 $I=<g_1,\cdots,g_t>$ ：令 $\forall f \in I$ ，做除法 $f=q_1g_1,\cdots,q_tg_t+r$ ，则 $r$ 必定是零（因为 $LT(r)\in<LT(I)>$ ，但是 $deg(LT(r))<deg(TL(g_i))$ ）

Hilbert Basis Theorem： $k[x_1,\cdots,x_n]$ 的任意理想 $I$ ，都拥有有限的生成集，即 $I=<g_1,\cdots,g_t>$ ，其中 $g_1,\cdots,g_t\in I$ 是有限个多项式。

Groebner Basis

固定单项式顺序，对于理想 $I$ 的有限子集 $G=\{g_1,\cdots,g_t\}$ ，如果满足
$<LT(g_1),\cdots,LT(g_t)> = <LT(I)>$
那么集合 $G$ 叫做 $I$ 的Groebner Basis或者standard basis

$K[x_1,\cdots,x_n]$ 的任意理想 $I$ 都拥有很多的Groebner基，并且它们都是 $I$ 的一组基， $\in G>$

The Ascending Chain Condition

理想的上升链： $I_1 \subseteq I_2 \subseteq I_3 \subseteq \cdots$

上升链条件（ACC）：令 $I_1 \subseteq I_2 \subseteq I_3 \subseteq \cdots$ 是 $k[x_1,\cdots,x_n]$ 中理想的上升链，那么存在一个 $N\ge1$ ，使得 $I_N=I_{N+1}=\cdots$

ACC等价于Hilbert Basis Theorem.

Groebner基的性质

理想 $I$ 的子集 $G=\{g_1,\cdots,g_t\}$ 是Groebner基，任意给定 $\in k[x_1,\cdots,x_n]$ ，那么存在一个 $\in k[x_1,\cdots,x_n]$ ，使得 $r$ 的每一项都不被 $LT(g_i)$ 整除，且 $\in I$

实际上， $r$ 就是 $f$ 除以 $G$ 的唯一余数 $r=\overline f^G$ ，无论如何改变 $G$ 中元素的除法顺序（但商 $q_i$ 可能会改变）。这里，余数 $r$ 叫做 $f$ 的标准型（normal form）

理想的隶属问题：令 $G$ 是理想 $I$ 的Grobner基，那么 $\in I$ 当仅当 $\overline f^G=0$

冗余：如果 $G$ 是理想 $I$ 的Grobner基，令 $\in G$ 且 $\ { p } ) > LT(p) \in <LT(G \backslash\{p\})>$ ，那么 $\ { p } G \backslash\{p\}$ 依然是理想 $I$ 的Grobner基。

约简Groebner基：任意的理想 $I$ ，都存在唯一的一组Grobner基 $G$ ，满足：

$LC(p)=1,\forall p \in G$
$\forall p \in G$ ，它的任意单项式都不属于 $\ { p } ) > <LT(G\backslash\{p\})>$

相等理想：固定单项式顺序，如果理想 $<f_1,\cdots,f_s>$ 和理想 $<g_1,\cdots,g_t>$ 拥有相同的约简Groebner基，那么它们是同一个理想。

求解方程组：设置单项顺序为字典序，那么Groebner基 $G$ 可以写成行阶梯矩阵的形式，矩阵的第 $i$ 行是 $g_i \in G$ 的 $k$ 上系数。可以用来消元，求解方程组：通过方程组 $E q$ 可以确定一个仿射簇 $V (E q)$ ，令 $I = < E q >$ ，计算 $I$ 的Groebner基 $G$ ，那么 $V (E q) = V (I) = V (G)$ 。由于 $G$ 是行阶梯矩阵，最后一行仅包含少量的变元，求解后回代计算倒数第二行，最终可求得 $V (E q)$

Buchberger’s Criterion

对于 $\in k[x_1\cdots,x_n]$ ，记 $x^\gamma = lcm(LM(f),LM(g))$ ，定义S多项式（syzygy-polynomial）为：
$\dfrac{x^\gamma}{LT(f)} \cdot f - \dfrac{x^\gamma}{LT(g)} \cdot g$
如果 $deg(p_i)=\delta,\forall i$ ，且 $deg(\sum_i p_i)<\delta$ ，那么 $\sum_i p_i$ 可以表示成S多项式的线性组合： $\sum_i p_i = \sum c_{jl}S(p_j,p_l)$ ，其中 $c_{ij} \in k$

Buchberger’s Criterion：理想 $I$ 的子集 $G=\{g_1,\cdots,g_t\}$ ， $G$ 是Groebner基当仅当 $\overline{S(g_i,g_j)}^G = 0,\forall i \neq j$

Buchberger’s Criterion也被叫做S-pair criterion，可以用来判断 $G$ 是否是Groebner基，也用来自然地引出计算Groebner基的算法。

Buchberger’s Algorithm

初始版本：
在这里插入图片描述
改进版本：

但是在实践中，Buchberger’s Algorithm的效率过低，实际上使用的是更高效的F4算法和F5算法来计算Groebner基。

Nullstellensatz

弱零点定理：令 $k$ 是代数封闭域， $\in k[x_1,\cdots,x)n]$ 是理想，它满足 $V(I)=\empty$ ，那么 $I=k[x_1,\cdots,x_n]$

Hilbert零点定理：令 $k$ 是代数封闭域，对于 $f,f_1,\cdots,f_s \in k[x_1,\cdots,x_n]$ ，那么 $\in I(V(f_1,\cdots,f_s))$ 当仅当 $f^m \in <f_1,\cdots,f_s>$ ， $\exist m \ge 1$