Solving systems of equations by Gr¨obner basis conversion

The second standard method for solving systems of polynomial equations tries to avoid the problem of large computational complexity of the Gr¨obner basis w.r.t. the lexicographic ordering by computing a Gr¨obner basis w.r.t. some other monomial ordering. Then this basis is converted to the lexicographic Gr¨obner basis and the method continues as the Elimination Gr¨obner Basis Method presented in the previous section.

Usually, the graded reverse lexicographic (grevlex) ordering from Definition 5, which often requires far less computational effort than a lexicographic Gr¨obner basis computation, is used in this method [40, 13]. Then some algorithm for converting a Gr¨obner basis with respect to one monomial ordering to a Gr¨obner basis with respect to a different monomial ordering is used. The FGLM algorithm [48] can be used for zero-dimensional ideals and the Gr¨obner walk algorithm [38] for general ideals.

Since we are considering zero-dimensional ideals, we briefly describe here the main ideas of the FGLM algorithm.

The algorithm starts with some Gr¨obner basisG of the idealI and converts it to a lexico-graphic Gr¨obner basis G_lex, or a Gr¨obner basis w.r.t. some other monomial ordering, of the same ideal. The algorithm uses only two structures, a listG_lex = {g₁, . . . , g_k}, which at each stage contains a subset of the lexicographic Gr¨obner basis, and a list B_lex, which contains a subset of the monomial basis of the quotient ringC[x₁, . . . , x_n]/I. Both these lists are initially empty.

For each monomialx^α ∈ C[x1, . . . , xn]in increasing lexicographic ordering, starting with x^α = 1, the algorithm performs these three steps:

Algorithm 4FGLM

1. For the inputx^α, computex^αG

• Ifx^αG = ∑

jcjx^α(j)G, where[ x^α(j)]

∈ Blex andcj ∈ C, i.e. ifx^αGis linearly dependent on the remainders on division by G of the monomials inB_lex, then add polynomialg=x^α−∑

jc_jx^α(j)∈ItoG_lexas the last element.

• Otherwise add[x^α]toB_lexas the last element.

2. Termination Test

If a polynomial g havingLT(g)equal to a power of the greatest variable in the lexico-graphic ordering was added toGlex, then STOP.

3. Next Monomial

Replacex^αwith the next monomial, w.r.t. the lexicographic ordering, which is not divisi-ble by any of the monomialsLT(gi)forgi∈Glex. GOTO 1.

Note that the original ordering (not the lexicographic ordering) is used for division byGin this algorithm.

Theorem 3. The FGLM algorithm terminates for every input Gr¨obner basis G of a zero-dimensional idealI and correctly computes a lexicographic Gr¨obner basisGlex forI and the lexicographic monomial basisB_lexfor the quotient ringA=C[x1, . . . , xn]/I.

Proof. The proof of this theorem can be found in [39].

Here we only show that the first polynomial added toG_lexusing this algorithm is a polynomial in one variable (the smallest in the used lexicographic ordering).

Let the ordering of the variables bex1 > x2 > · · · > xn. Using this ordering, the FGLM algorithm starts with the monomialx^α = 1and continues with monomials x_n, x²_n, x³_n and so on in increasing lexicographic order. Let us consider the setS1 =

{

[1],[xn],[xn]², . . . }

with [x_n]ⁱ ∈ A = C[x₁, . . . , x_n]/I, i ≥ 0. Since our ideal is zero-dimensional, the algebraA is finite dimensional. This means that the setS₁ is linearly dependent inA. Moreover, also the set S2=

{

1, xnG, x²_n^G, x³_n^G, . . . }

is linearly dependent.

Letibe the smallest positive integer for which {

1, x_n^G, x²_n^G, . . . , xⁱ_n^G }

is linearly dependent.

This means that in the FGLM algorithm monomial cosets[1],[x_n],[ x²_n]

, . . .[ xⁱ_n⁻¹]

will be added toB_lexand we can write

xⁱ_n^G=

withc_j ∈C. Therefore the polynomial xⁱ_n−

i−1

∑

j=1

cjx^j_n∈I (4.36)

is a polynomial in one variable (xn), which is added toGlexas the first polynomial.

For some applications, e.g. where it is sufficient to find solutions only for one variable or where solutions for other variables can be found in a different “easier” way, the algorithm can be stopped after finding this one-variable polynomial.

Example 5. (FGLM method)Let us consider the system of polynomial equations (4.30) from Example 4, i.e. the system

2x²+y²+ 3y−12 = 0, (4.37)

x²−y²+x+ 3y−4 = 0.

Here we show how this system can be solved using the FGLM conversion algorithm. This al-gorithm starts with a Gr¨obner basisGw.r.t. some “feasible” monomial ordering. Usually the graded reverse lexicographic ordering (grevlex) is used here. In this case the Gr¨obner basisG w.r.t. this grevlex ordering consists of the following two polynomials

G={

3y²−2x−3y−4,3x²+x+ 6y−16}

. (4.38)

The computation of this basis is simpler than the computation of the lexicographic Gr¨obner basis (4.32) for the same ideal. In this case both polynomials from the grevlex Gr¨obner basis G(4.38) can be easily obtained from the initial polynomials (4.37) as their simple linear combi-nations. Denoting the input polynomials asf₁andf₂and polynomials from the grevlex Gr¨obner basisGasg1andg2, we haveg1=f1−2f2andg2 =f1+f2.

Now we transform this grevlex Gr¨obner basisGto the lexicographic Gr¨obner basis using the presented FGLM algorithm.

First we set Glex = {} andBlex = {}. Then we go through monomialsx^α ∈ C[x, y]in increasing lexicographic order forx > y, i.e. we start with1and continue withy, y²and so on.

For each of these monomials, we first perform the main loop of the FGLM algorithm. This main loop requires to computex^αG and to check if this remainder is linearly dependent on the remainders of the monomials inB_lexon the division byG. In this case we have

1. 1^G= 1,and sinceB_lexis empty we setB_lex={[1]}, is linearly independent we setB_lex ={

[1],[y],[

is linearly dependent we let B_lex = {

[1],[y],[

}, wherecjare coefficients from the linear combi-nation

and therefore, the first element of the G_lex, i.e. the lexicographic Gr¨obner basis, will be polynomialy⁴−2y³− ¹³₉y²+ ¹⁰₃y−⁸₉.

Next we can continue with the next two steps of the FGLM algorithm, i.e. the termination test and the next monomial step. This means that we can continue with monomials containingxin the lexicographic ordering and for these monomials again perform the main loop. However, in this case, it is sufficient to stop here and find solution foryfrom the polynomial equation

y⁴−2y³−13

9 y²+10 3 y− 8

9 = 0. (4.41)

This equation gives us solutions y = {

1, 2, ¹₃, −⁴₃}

. Solutions for x can be obtained by substituting the solutions foryto one from the initial polynomial equations (4.37). In this way we obtain four solutions of the system (4.37)

(−2,1),(1,2), (

−7 3,1

3 )

, (8

3,−4 3

)

. (4.42)

Note that the polynomial equation (4.41) is equivalent to the polynomial equation 9y⁴ − 18y³−13y²+ 30y−8 = 0obtained from the lexicographic Gr¨obner basis (4.32) computed in Example 4.

4.3.3 Solving systems of equations via eigenvalues end eigenvectors

In document ZuzanaK´ukelov´a AlgebraicMethodsinComputerVision (Stránka 48-51)