Project Topics
Get Complete Project Material File(s) Now! »
Gr¨obner bases and Linear Algebra
The aim of this section is to present an efficient strategy to solve zero-dimensional systems. The first step is to compute a Gr¨obner basis for a graded ordering, and the most common is the DRL ordering. In [71], Lazard showed the link between linear algebra and Gr¨obner bases computations. Faug`ere presented in [34] an efficient algorithm which includes Buchberger criterions into linear algebra computations of Gr¨obner basis. In [35], he presented the first signature-based algorithm: the advantage of this algorithm is that no useless pairs are considered if the input is a regular sequence (see chapter 2). The two last algorithms have been implemented in [63], and are the most efficient algorithms to compute Gr¨obner bases for a graded ordering. We focus on the zero-dimensional case: the FGLM algorithm [39] can be used to compute a Gr¨obner basis for any ordering of a zero-dimensional ideal, once a Normal Form is known. This Normal Form is usually available as soon as a first Gr¨obner basis of the ideal has been computed. Figure 1.34 summarizes the common strategy to solve a zero-dimensional system.
Lazard’s algorithm and Macaulay’s matrices
The aim of this subsection is to present the Lazard’s algorithm, which computes a Gr¨obner basis for a graded ordering. In order to simplify notations, we present it only in the homogeneous case. Before giving the algorithm, we present the so-called Macaulay’s matrix of a sequence of polynomials in a given degree, and then explain the authorized operations on it.
FGLM algorithm
FGLM algorithm [39] was published in 1993 and named by the four names of its authors Faug`ere, Gianni, Lazard and Mora. From a Gr¨obner basis G of a zero dimensional I, FGLM algorithm returns the Gr¨obner basis for an other ordering �2. The idea is simple and powerful: since I is zero dimensional, the quotient algebra K[X]/I is of finite dimension δ.
Thus, if we pick monomials m by increasing ordering for �2, the knowledge of G allows us to compute NF�(m, G). With enough monomials, we obtain linear combinations between the normal forms, which give a Gr¨obner basis of I for �2. In order to compute efficiently these normal forms, the algorithm uses linear algebra: it first computes the matrices Mi of the maps f �→ xif in K[X]/I for each i ∈ {1, . . . , n}, using algorithm 1.47.
In algorithm 1.47, we assume that I is not equal to K[X], which can be easily checked: in this case the reduced Gr¨obner basis G for � of I is equal to {1}. We now define the staircase and the boundary of G:
Definition 1.48. Let G be the reduced Gr¨obner basis for � of an ideal I � K[X]. We define:
— the staircase E(G) of G is the basis of K[X]/I given by monomials not top reducible by G.
— the boundary B(G) of G is the set {xi�k | 1 ≤ i ≤ n and �k ∈ E(G)}\E(G).
Since I is zero-dimensional, the staircase E(G) = {1 = �1 ≺ · · · ≺ �δ} is finite of cardinal δ = dimK(K[X]/I). In this case, the following proposition characterizes B(G). Proposition 1.49. [39] Let G be the reduced Gr¨obner basis for � of a zero-dimensional ideal I � K[X]. For every m ∈ B(G), one and only one of the following condition holds:
1. For each xi dividing m, m/xi belongs to E(G). This is the case if and only if m is the leading monomial of an element g ∈ G.
2. m can be written xi �m for some i and some �m ∈ B(G).
Proof. The equivalence in the first point follows directly from the definition of a reduced Gr¨obner basis. Assume that there exists xi dividing m such that m/xi does not belong to E(G). Since m belongs to B(G), m can also be written xj� with � ∈ E(G). It follows that i �= j and xi divides �. E(G) is obviously closed under division, so �� = �/xi ∈ E(G). Thus xj�� ∈ B(G) because xj�� = m/xi /∈ E(G), and the proposition is proved.
Matrix SAGBI-F5 algorithm
Now we give a description of the SAGBI-F5 algorithm. We consider a graded subalgebra A of K[X] = K[x1, . . . , xn], which is connected and finitely generated.
The SAGBI-F5 algorithm is very close to the original F5-algorithm, but it works in A instead of K[X]. We present here a Matrix SAGBI-F5 algorithm, which uses SAGBIMacaulay’s matrices. We use the same notations, f1, . . . , fs are homogeneous polynomials in A of degree d1 ≤ · · · ≤ ds, and � is a graded ordering. We assume that in every component Ad, a basis (bdi )1≤i≤nd of A as a K-vector space has been computed, with LM�(bd1 ) � LM�(bd2 ) � · · · � LM�(bd nd ).
Definition 1.67. Let F = f1, . . . , fs ∈ A be homogeneous polynomials of degrees d1, . . . , ds and � be an ordering on K[x1, . . . , xn]. Let D be an integer. The SAGBI-Macaulay’s matrix MacA �,D(F) is a matrix:
— with dimK(AD) columns, indexed by polynomials (bd k)1≤k≤nd sorted by � with decreasing order.
— with �s i=1 dimK(AD−di) rows, indexed by pairs (i, bd−di j ), where i ∈ {1, . . . , s} and j ∈ {1, . . . , nd−dj}, so that bd−dj k ranges all the basis of Ad−dj . The indexes are sorted by increasing i first, and then by decreasing bd−di j .
— such that MacA �,D(F)(i,b� j ),bDk is equal to the coefficient of αk in the writing fib� j = �nD k=1 αkbDk.
Just like the classical Matrix-F5-algorithm 1.44, the SAGBI-F5 algorithm constructs matrices incrementally degree by degree and equation by equation, and remove from the SAGBIMacaulay matrix some useless rows. At each degree d the algorithm constructs a SAGBIMacaulay’s matrix Md,i and performs row reductions on it, the valid operations being to add to some row a linear combinations of rows situed above. The incremental step from i − 1 to i introduces the rows corresponding to bd−di j fi for all polynomials of (bd−di j ) in the basis of Ad−dj , except those having same leading monomial as a row of �Md−di,i−1, where di = deg(fi). This criterion is a variant of the F5-criterion 1.45 and is explained in lemma 1.69. The algorithm stops when the current degree is equal to a given bound D.
Gradings on subalgebras of K[X±1]
In this thesis, we have to consider several algebras. In chapters 3 and 4, we will deal with K[X]G, the algebra of invariants under the action of a finite group G, which is a subalgebra of K[X], graded by the total degree on K[X]. We will also have to consider the whole algebra K[X], but the action of an abelian group, joined to the total degree, gives a grading by the commutative monoid N×X(G) where X(G) is an abelian finite group. In chapter 5, we will study polynomial systems in K[S], a subalgebra of the ring of Laurent polynomials K[X±1], where S is a semigroup of Zn. This subalgebra will be graded by N. Quasi-homogeneous and multihomogeneous gradings are also classical gradings on K[X], given by N or N�.
In order to give a theoretical framework, which is valid for all these algebras, we fix a commutative monoid M with neutral e, which can be seen as one of the mentioned monoids.
Definition 2.12. Let A be a subalgebra of K[X±1]. A grading indexed by M on A is a decomposition of A into graded components (Ad)d∈M such that:
— Ae = K.
— A = � d∈M Ad as a K vector space.
— Let d, d� ∈ M and (f, h) ∈ Ad × Ad� . Then fh ∈ Ad+d� .
A polynomial f in a component Ad is said to be M-homogeneous of M-degree d. We fix such a subalgebra A graded by M and see how this grading can be transfered on homogeneous ideals of A and associated quotient algebras.
Definition 2.13. An ideal I ⊆ A is said to be M-homogeneous if it is generated by homogeneous elements.
Table of contents :
Introduction
I Preliminaries
1 Gr¨obner Bases
1.1 Gr¨obner Basics
1.1.1 Ideals and Varieties
1.1.2 Monomial Orderings and Gr¨obner bases
1.1.3 Buchberger Algorithm
1.1.4 What is Solving ?
1.2 Gr¨obner bases and Linear Algebra
1.2.1 Lazard’s algorithm and Macaulay’s matrices
1.2.2 Matrix-F5 algorithm
1.2.3 FGLM algorithm
1.3 Extension to subalgebras
1.3.1 SAGBI bases
1.3.2 Matrix SAGBI-F5 algorithm
2 Commutative Algebra and Gr¨obner bases
2.1 Commutative Algebra and Hilbert series
2.1.1 Algebraic tools
2.1.2 Gradings on subalgebras of K[X±1]
2.1.3 Hilbert Function and Hilbert Series
2.2 Applications in K[X]
2.2.1 Bounds on the degrees
2.2.2 Genericity of regular sequences. Semi-regular sequences
2.2.3 Affine case
3 Invariant Theory and Monomial Algebras
3.1 Invariant Theory
3.1.1 Action of Groups on Polynomials. Computation of Invariants
3.1.2 Molien’s Theorem
3.1.3 Structure of the algebra of invariants, and classical strategies
3.1.4 Representation Theory of finite groups
3.1.5 Estimates of Dimensions of Isotypic Components
3.2 Monomial Algebras
II Contributions
4 Solving systems with symmetries
4.1 Vortex Problem
4.1.1 Vortex Problem
4.1.2 From invariant system to invariant equations
4.1.3 From two blocks to symmetric functions in one block
4.1.4 Solving the equations with the symmetric functions
4.1.5 Benchmarks
4.2 Ideals stable under the action of an abelian group
4.2.1 Linear change of variables
4.2.2 Grading induced by a diagonal matrix group
4.2.3 Abelian Matrix-F5 algorithm
4.2.4 Abelian-FGLM algorithm
4.2.5 Complexity questions
4.2.6 Experiments
4.3 Stable equations and SAGBI bases
4.3.1 SAGBI-Gr¨obner bases in invariant rings
4.3.2 SAGBI-FGLM algorithm and general algorithm to obtain an invariant Gr¨obner basis
4.3.3 Removing spurious solutions
4.3.4 Implementation and Benchmarks
5 Gr¨obner Bases in Monomial Algebras
5.1 Introduction
5.2 Sparse Gr¨obner bases
5.3 Algorithms
5.3.1 Sparse-MatrixF5 algorithm
5.3.2 Sparse-FGLM algorithm
5.4 Complexity
5.5 Dense, multi-homogeneous and overdetermined systems
5.6 Experimental results
