Algebraic Solution of Systems of Polynomial Equations Using Groebner Bases
Algebraic Solution of Systems of Polynomial Equations Using Groebner Bases
复制标题
DOI：
10.1007/3-540-51082-6_83
复制
发表时间：
1987-06
期刊：
影响因子：
--
通讯作者：
P. Gianni;T. Mora
中科院分区：
文献类型：
--
作者：
P. Gianni;T. Mora
Buchberger 的 Gr6bner 基计算算法 [BUCI, 2, 4] 最重要的应用之一是多项式方程组（具有有限多个根）的求解，即计算 O 维多项式理想的零点。它基于 Gr6bner 碱基之间的关系，这是一种词典排序和消除理想，由 Trinks [TRI] 发现。目前，不同的计算机代数系统中都提供了使用 GrGbner 基础计算来隔离多项式方程组实根的软件包，包括 SAC-2、Reduce、Scratchpad If、Maple。原则上，Buchberger-Trinks 算法应该允许在系数域 k（通常是有理数）的代数闭包中计算此类系统的解，从某种意义上说，可以明确表示包含所有解的 k 的有限扩展并表达该域中的根。然而，这需要对 k 的代数扩展塔进行多项式因式分解，这通常非常昂贵，因此所得算法不太可行，并且据我们所知，没有可用的实现。 [GTZ]关于理想一次分解的成果包括对O维理想的Gr6bner基结构的深入研究；特别是，该论文表明，在坐标的“一般”线性变化之后，多项式方程组的根可以用 k 的简单扩展来表示。因此，在这种情况下，不需要在代数扩展塔上对多项式进行因式分解。然而，执行坐标更改会产生引入稠密多项式和增加系数大小的不良影响。接下来的问题是生成计算（O 维）理想的 Or6bner 基的策略，该策略至少能够控制这些副作用的影响：本文提出了两种这样的策略，以及 Gianni 的算法在当前问题中的应用，该算法在“通用”坐标变化后计算 O 维理想的根式。 D. Duval ([DUV]) 提出了一种基于她的“分裂算法”的不同方法，无需多项式因式分解即可计算多项式方程组的解。她的算法也应该通过坐标的“通用”变化来简化。本文讨论的算法是在 SCRATCHPAD If 中实现的。在第一节中，我们回顾了[GTZ]中GrObner基的一些众所周知的性质以及零维理想的Gr6bner基结构的性质；在第二部分中，我们回顾一下用于求解代数方程组的 GrGbner 基础算法。
One of the most important applications of Buchberger's algorithm for Gr6bner basis computation [BUCI, 2, 4] is the solution of systems of polynomial equations (having finitely many roots), ie the computation of zeros of O-dimenslonal polynomial ideals. It is based on a relation between Gr6bner bases wrt, a lexicographical ordering and elimination ideals, which was discovered by Trinks [TRI]. Packages for isolation of real roots of systems of polynomial equations using GrGbner basis computation are currently available in different computer algebra systems, including SAC-2, Reduce, Scratchpad If, Maple. In principle, Buchberger-Trinks algorithm should allow to compute solutions of such systems in the algebraic closure of the coefficient field k (usually the rational numbers), in the sense that it is possible to represent explicitly a finite extension of k containing all solutions and to express the roots in this field. However~ this requires several factorlsatione of polynomials over a tower of algebraic extensions of k, which is usually very costly, so that the resulting algorithm is not very feasible and, as far as we know, no implementation is available. The results of [GTZ] on primary decomposition of ideals include a thorough study on the structure of Gr6bner bases for O-dimensional ideals; in particular, the paper shows, that after a" generic" linear change of coordinates, the roots of a system of polynomial equations can be expressed in a simple extension of k. Therefore, in this case, no factorisation of polynomials over towers of algebraic extensions is needed. However performing a change of coordinates has the undesirable effects of introducing dense polynomials and of increasing the size of coefficients. The problem then arises of producing strategies to compute Or6bner bases for (O-dimensional) ideals, which at least are able to control the influence of these sideeffects: two such strategies are presented in this paper, together with the application to the present problem of an algorithm by Gianni that computes the radical of a O-dimensional ideal after a" generic" change of coordinates. A different approach, based on her" splitting algorithm", to compute solutions of systems of polynomial equations without the need of polynomial factorisaticns has been proposed by D. Duval ([DUV]); also her algorithm should be simplified by a" generic" change of coordinates.The algorithms discussed in this paper are implemented in SCRATCHPAD If. In the first section we recall some well-known properties of GrObner bases and properties on the structure of Gr6bner bases of zero-dimensional ideals from [GTZ]; in the second section we recall the GrGbner basis algorithm for solving systems of algebraic equations.