吴消元法

多项式：

P=P(${\displaystyle x_{1}}$ ,${\displaystyle x_{2}}$ ,……${\displaystyle x_{n}}$ )中

主变元

变元(${\displaystyle x_{1}}$ ,${\displaystyle x_{2}}$ ,……${\displaystyle x_{n}}$ )中下标最大下标

称为多项式P的主变元，记为 Ivar(P)^[1]

例如 P=${\displaystyle -2*x_{2}^{2}-x_{1}*x_{2}^{2}+2*x_{1}*x_{2}+2*x_{1}^{2}*x_{1}+x_{1}^{3}}$ 

变元为${\displaystyle x_{1}}$ ,${\displaystyle x_{2}}$ ,主变元为 Ivar(P)${\displaystyle =x_{2}}$ 。

多项式的类

多项式P的类定义为 主变元 Ivar(P)的下标，记作 cls(P).

上例多项式P的类 为 cls(P)=2。

多项式的次数

多项式关于变元${\displaystyle x_{i}}$ 的次数 记为 deg(P,${\displaystyle x_{i}}$ )^[2]

多项式关于主变元的次数，记为deg(P)=deg(P,ivar(P))

多项式的长度，定义为多项式的项数，记为 t(P).

多项式的指标集[t(P),cls(P),deg(P)]。

初式

多项式的初式，是多项式主变数最高幂项的系数，记为 init(P)^[3]

例如 P=${\displaystyle -2*x_{2}^{2}-x_{1}*x_{2}^{2}+2*x_{1}*x_{2}+2*x_{1}^{2}*x_{1}+x_{1}^{3}}$ 

${\displaystyle =(-2-x_{1})*x_{2}^{2}+2*x_{1}*x_{2}+2*x_{1}^{2}*x_{1}+x_{1}^{3}}$ 

init(P)=${\displaystyle (-x_{1}-2)}$ ;

初式 init(P)是一个除主变元之外的多项式I

：I=I(${\displaystyle x_{1}}$ ,${\displaystyle x_{2}}$ ,……${\displaystyle x_{c-1}}$ )

其中 c=cls(P) 是多项式 P的类。

正则形式

将多项式表示为

P=${\displaystyle I*x_{c}^{d}+}$ 关于${\displaystyle x_{c}}$ 的低次幂项，称为多项式P的正则形式。^[4]

P，Q为非零多项式，如果 cls(P)<cls(Q)，或cls(P)=cls(Q)，但deg(P)<deg(Q),则称P的序低于Q的序。记为 P<Q。

如果P<Q，或Q< P 都不成立，则P，Q同序，记为 P~Q.^[5][6]

约化

多项式 P，Q，如果

cls(P) =c>0； deg(Q,${\displaystyle x_{c}}$ )<deg(P).

则称P对于Q是约化的^[7]

如果多项式P的初式 init(P) 是常数，则对于任何低类多项式Q，（cls(Q)<cls(P))都是约化的。^[8]

例子：^[9]

P=${\displaystyle (x_{1}+3)*(x_{1}+8)*x_{2}^{5}+S(x_{1},x_{2})}$ 

Q=${\displaystyle (x_{1}+1)*(x_{1}+2)*(x_{1}+3)*x_{2}^{2}}$ 

其中 ivar(P)=${\displaystyle x_{2}}$ 

cls(P)=c=2

deg(P)=5

deg(S)<5

deg(Q,${\displaystyle x_{c}}$ )=2;

P 对于 Q 是约化的。

升列

多项式集 AS: ${\displaystyle A_{1}}$ ,${\displaystyle A_{2}}$ ....${\displaystyle A_{r}}$ 是一个升列

如果满足以下两个条件：^[10]

1. cls(${\displaystyle A_{1}}$ ） < cls(${\displaystyle A_{2}}$ ) <....< cls(${\displaystyle A_{r}}$ )
2. init(${\displaystyle A_{j}}$ ) 关于 ${\displaystyle A_{i}}$  对于任意的 i<j 是约化的。

三角列

如果非零多项式集 AS: ${\displaystyle A_{1}}$ ,${\displaystyle A_{2}}$ ....${\displaystyle A_{r}}$ 

只满足：

cls(${\displaystyle A_{1}}$ ） < cls(${\displaystyle A_{2}}$ ) <....< cls(${\displaystyle A_{r}}$ )

则非零多项式集 AS 是一个三角列，又称为弱升列。^[11]

两个多项式:F,G, 其中 cls(F)=c,init(F)=I,通过多项式除法可得：

${\displaystyle I^{s}*G=Q*F+R}$ 

如取s尽量小，R称为 G关于F的Ritt余式，记为 R=Remdr(G/F)^[12]

零点集

多项式方程组 PS =0 的全部解，称为PS 的零点集，记为 Zero(PS)^[13]

两个多项式方程组 ${\displaystyle P_{1}}$ ,${\displaystyle P_{2}}$ 

如果 R=Remdr(${\displaystyle P_{2}}$ /${\displaystyle P_{1}}$ )

则 Zero(PS)=Zero(${\displaystyle P_{2}}$ ,${\displaystyle P_{1}}$ )=Zero((${\displaystyle P_{2}}$ ,${\displaystyle P_{1}}$ ,R)

加入余式，零点集不变。^[14]

多项式对升列的余式

给出一个多项式P=P(${\displaystyle x_{1}}$ ,${\displaystyle x_{2}}$ ……${\displaystyle x_{k}}$ }和一个升列 AS={${\displaystyle A_{1}}$ ,${\displaystyle A_{2}}$ ……${\displaystyle A_{k}}$ }

按反向次序连环计算下列余式：

${\displaystyle r_{k}}$ =Remdr(P / ${\displaystyle A_{k}}$ )

${\displaystyle r_{k-1}}$ =Remdr(${\displaystyle r_{k}}$  / ${\displaystyle A_{k-1}}$ )

${\displaystyle \ldots }$ 

${\displaystyle r_{1}}$ =Remdr(${\displaystyle r_{2}}$  / ${\displaystyle A_{1}}$ )

最后得到的余式 ${\displaystyle r_{1}}$ ≡R≡Remdr(P/AS) 称为 P 对于 AS 的余式。^[15]

R 是唯一确定的多项式。

R 对于 AS 是约化的。^[16]

• 王东明 以 Maple 编写的 CharSets 软件包，自1991年就成为Maple Shared Library 的软件包，也是他2003年 Epsilon Maple软件包的组成单元之一^[17]
• 数学机械化自动推理平台 MMP 3.0 有 charser 软件，但MMP 3.0 平台为半成品，用户寥寥无几，远不如 王东明 CharSets 软件包成功。

• 计算机视觉、自动化定理证明、机器人、生物^[18]

引用

书籍

• 吴文俊 著 《数学机械化》 科学出版社 2006 王东明 著 《消元法及其应用》 科学出版社 2002 ISBN 7-03-010560-5
• Dongming Wang（王东明）. Elimination Practice London: Imperial College Press, 2004, ISBN 1-86094-438-8
• 高小山、王定康、裘宗燕、杨宏 著 《方程求解与机器证明》 科学出版社 2008 ISBN 978-03-017862-6
• 关霭雯 编 《吴消元法讲义》 北京理工大学 1994