and not by parenthesis. However, when working with these sets of polynomials or monomials, we need some fixed ordering of polynomials or monomials in these sets, although it may be usu-ally an arbitrary ordering. In such cases we will use the ordering in which elements of such sets are ordered as they are given on the input. For example, for the setF ={
2x2+y2+ 3y−12, x2−y2+x+ 3y−4}
we will denote the first polynomialf1 = 2x2+y2+ 3y−12and the second polynomialf2=x2−y2+x+ 3y−4. When a result depends on the ordering then we will explicitly write that the set is ordered and we will use parentheses.
4.2 Gr ¨obner bases and linear algebra
Before describing the first class of methods for solving systems of polynomial equations, i.e.
methods based on Gr¨obner bases and on computations in quotient ringsC[x1, . . . , xn]/I, we first show how polynomials and Gr¨obner bases are connected with linear algebra.
Let us consider a setF = {f1, ..., fm|fi ∈C[x1, ..., xn]} ofm polynomials innvariables over the field Cof complex numbers, and let T≻(F) denote the set of monomials in F or-dered with respect to the ordering ≻. Let s be the number of distinct monomials in F, i.e.
|T≻(F)|= s.
Now we define a linear mapping
ψT≻(F):C[x1, . . . , xn]→Cs, (4.22) such that for the polynomialf =∑s
i=1cixα(i)∈F with monomialsxα(i)ordered with respect to the ordering≻
ψT≻(F)(f) = (c1, . . . , cs). (4.23) This means that we can interpret vectors ofCsas polynomials and vice versa. We will call the mappingψthevector representationof polynomials.
Similarly we can define amatrix representationof a set ofmpolynomialsF as
ΨT≻(F) : (C[x1, . . . , xn])m→Mm×s(C), (4.24) such that
ΨT≻(F)(f1, . . . , fm) =
ψT≻(F)(f1) . . . ψT≻(F)(fm)
. (4.25)
HereMm×s(C) stands for the vector space of all matrices of sizem×swith elements from C. If it is clear with respect to which ordering the representation is created and which set of monomials is used, the subscripts are omitted, i.e. we write onlyΨT(F)or even onlyΨ.
These vector and matrix representations of polynomials allow us to use standard concepts of linear algebra and vector spaces when working with polynomials. Since many efficient linear algebra algorithms are available, such representations can significantly simplify and speed up computations with polynomials.
To show where linear algebra may be useful, we describe here how several polynomials can be reduced at the same time using Gaussian elimination, i.e. how to do polynomial division [40]
of several polynomials by Gaussian elimination.
Let us first consider polynomial division of a single polynomial, i.e. let us consider a poly-nomialf which we want to reduce by polynomialsR = (r1, . . . , rk). We want to emulate the polynomial division off byR, i.e. to computefRusing Gaussian elimination of a single matrix M. This means that we need to create this matrix Mas a matrix representationΨ(4.25) of the polynomialf and suitable monomial multiples of polynomialsr1, . . . , rk. The main question is which monomial multiples ofr1, . . . , rkshould we add to this matrix. Before describing how these monomial multiples should look like for general polynomialsf andr1, . . . , rk, we show how the matrixMlooks for a simple example.
Example 3. (Matrix polynomial division)Let’s consider polynomialf = x2+y+ 3, which we want to reduce by polynomialsR = (
x+y+ 2, y2+ 3y)
using the graded reverse lexico-graphic ordering withx > y. The polynomial division algorithm performs these steps:
1. ( r2, r1}w.r.t. the graded reverse lexicographic orderingx > y of monomials, wherer1 andr2 are polynomials fromR. In this case the set of ordered monomials contained inF isT≻(F) = (x2, xy, y2, x, y,1)
and the matrix representationΨT≻(F)(F)has the form
M= ΨT≻(F)(F) =
After Gaussian elimination of this matrixMwe obtain the following matrix
eM=
As it can be seen, the last row of the matrixeMcorresponds to the polynomial−2x−7which is, up to some non-zero multiple, in this case−1, equal to the remainder off on the division byR.
This means that Gaussian elimination on this matrix does polynomial division. The fact that in this case we only obtain the remainder up to some non-zero multiple is not so important. It is because for most of the applications we only need to generate some non-zero multiples of remainder polynomials, or only to know weather the remainder is zero or not.
Let’s now show how the matrixMcan be constructed for general polynomialsfandr1, . . . , rk. The algorithmic description of the division algorithm can be found in [40]. Here it is sufficient to describe its main idea. In thejth step of the division algorithm, the intermediate resulthj, also called the dividend, is reduced using the divisorriwith the smallest possibleisuch that the leading term ofridivides the leading term ofhj, i.e.LT(ri)|LT(hj). If suchriexists, the new dividend has the formhj+1=hj−qi,jri, whereqi,j = LTLT(r(hj)
i).
To emulate this using the matrix M, we need to add to this matrix a row corresponding to the polynomialqi,jri for each intermediate dividend hj and used divisor ri. To “add a row corresponding to a polynomialptoM” means that we addpto the set of polynomialsF that is represented by the matrixM= ΨT≻(F)(F)(4.24).
Now the question is: which divisorriwill be used in thejthstep of this algorithm? To predict this we do not need to know the exact form ofhj, wherehj =hj−1−ql,j−1rl. It is sufficient to know which monomials appear in the polynomialhj = hj−1 −ql,j−1rl. The polynomial hj contains maximally all monomials of hj−1 andql,j−1rl, except for the leading monomial LM(hj−1). This means that it is sufficient to assume that the polynomialhj−1−ql,j−1rlcontains all these monomials and with such an assumption we will surely not miss any possible divisor.
This results in the following algorithm for constructing the matrixMfor emulating polynomial division of polynomialf by polynomialsR= (r1, . . . , rk):
Algorithm 2Matrix polynomial division
Input:f,R= (r1, . . . , rk), monomial ordering≻
Output:MatrixMin the matrix representation of polynomialsF, i.e.M= ΨT≻(F)(F), such that the remainderfR∈F
1: SetF :={f}and letD=T≻(F), whereT≻(F)is the ordered set of monomials ofF
2: whileDis non-emptydo
3: Letxαbe the maximal monomial inDw.r.t.≻
4: D:=D\ {xα}
5: ifxαcan be reduced by someri ∈Rthen
6: Letri ∈Rbe the divisor with the smallest possibleisuch thatLT(ri)dividesxαand letq:= LT(rxα
i)
7: SetF :=F ∪ {qri}andM= ΨT≻(F)(F)
8: SetD:=D∪ { all monomials ofqriexcept ofxα }ordered w.r.t.≻
9: end if
10: end while
It can be proved that this algorithm terminates after a final number of steps and that the
re-sulting matrixM = ΨT≻(F)(F) contains all necessary polynomials for emulating polynomial division by its Gaussian elimination. After Gaussian elimination ofM, the final reduced poly-nomialfR will either be zero, i.e. will correspond to a zero row of reducedM, or will have a leading term that cannot be reduced by any leading term ofr1, . . . , rk. This means that, in this case, this reduced polynomial will correspond to a row of reducedMwith a pivot that was not a pivot inM. Recall that the result of polynomial division, i.e. the polynomialfR, will for general polynomialsR= (r1, . . . , rk)depend on the ordering of polynomialsr1, . . . , rkinR.
Of course the matrix Mconstructed using the proposed algorithm might also contain some unnecessary rows. It is because we have assumed that no terms cancel in hj −qri, which might not always be true. However, this is not a problem since for polynomials with general coefficients only a small number of unnecessary rows is usually generated.
For the polynomials from Example 3, the presented algorithm generates directly the ma-trix (4.27) without any unnecessary rows.
This algorithm can be easily extended to emulate the polynomial division of several poly-nomials by Gaussian elimination of a single matrix. Let us consider that we want to reduce polynomialsf1, . . . , fmbyR = (r1, . . . , rk). The algorithm for constructing a matrix emulat-ing polynomial division of these polynomials first setsF ={f1, . . . , fm}and then continues as Algorithm 2 for a single polynomial.
A similar algorithm is used in the F4 algorithm [49] to perform division of S-polynomials when constructing a Gr¨obner basis.
Note that using Gauss-Jordan elimination instead of Gaussian elimination, i.e. computing reduced row-echelon form ofM, will correspond to fully reducingf1, . . . , fmusing polynomial division. This means that not only the leading terms off1, . . . , fmcannot be further reduced by R, but no terms off1, . . . , fmcan be further reduced.
Here we have shown how several polynomials can be reduced at the same time by using Gaussian elimination of a single matrix. Polynomial division is the main part of all algorithms for finding Gr¨obner bases, and therefore, its good implementation may speed them up. This is also the main idea of the F4 algorithm for computing Gr¨obner bases [49]. F4 speeds up the reduction step by exchanging multiple polynomial divisions of S-polynomials for Gaussian elimination of a single matrix created similarly as described above.
In Section 4.4 we will show that the matrix representation of polynomials and Gauss-Jordan elimination can be also used for efficient generation of polynomials from an ideal. Moreover in [33, 31] it was shown that the matrix representation and efficient matrix algorithms like QR or LU decomposition can be used for improving numerical stability of Gr¨obner bases computa-tions.