Detection of steady states and their numbers for finite biological models

Get Complete Project Material File(s) Now! »

Gr¨obner bases for polynomial system solving

The general method to solve a polynomial equation set is to transform it into several equation sets of triangular-like shapes with the same solutions, and then extend the solution of each univariate polynomial within to that of the whole polynomial equation set. Therefore we start the study on polynomial system solving with Gr¨obner bases with univariate polynomial equations.

Univariate polynomial equation solving

For a univariate polynomial F ∈ K[x], now consider its solutions in some algebraic extension ˜K of K. By the algebraic fundamental theorem, F has at most deg(F) roots in ˜K, and they are the solutions of the equation F = 0. Therefore by solving F = 0 we mean to find an appropriate way to represent all these roots in ˜K of F. First, to obtain the solutions of F = 0 in Q one can use factorization of F over Q. Take F = 2×4 − 3×3 + 2×2 − 1 for example. With methods for factorization (see e.g., [153, Chapters 14&15]), one can factorize F as F = (x − 1)(2x + 1)(x2 − x + 1).
Then it is known that there exist two and only two rational solutions of F = 0: x = 1 and x = 1/2. Take the fact that all integers and rational numbers can be represented precisely in computers, one knows that the whole solving process of F = 0 in Q can be implemented in computers.
Then for the solutions in R and C, we can use formula by radicals to represent precisely the solutions of F = 0 if deg(F) ≤ 4. However, the solvability by radicals has been proved to be not feasible for general equations of degree ≥ 5 as in the Galois theory [86, Chapter VI]. But this does not mean that we can do nothing to solve equations with higher degrees, for example we can adopt the numeric methods like the Newton method [82].
But in Computer Algebra we have a symbolic method to represent the real solutions of a polynomial equation, that is the real root isolation [30, 136]. It means to compute a sequence of disjoint rational intervals such that each real root of F is contained in some interval and there is only one root in each interval. As the lengths of the intervals can be arbitrarily small, we can regard these intervals as a “precise” representation of all the real roots of F without errors. Or in other words, all the distinct real solutions can be computed precisely.
To summarize, the solutions of a univariate polynomial equation in various number fields can be represented in an appropriate way, and there exist applicable methods to solve them. Therefore, in the following we always assume that any univariate polynomial equation is solvable.

Zero-dimensional polynomial equation set

In previous discussions we have made clear that the common method to solve a zerodimensional polynomial equation set via Gr¨obner bases consists of three steps: computing Gr¨obner bases w.r.t. DRL, changing their orderings to LEX, and transforming Gr¨obner bases w.r.t. LEX to either triangular sets or rational univariate representations. We have reviewed the first two steps in this chapter, next we briefly show how the rational univariate representation (short as RUR) can be used to represent the solutions of zero-dimensional polynomial equation sets, leaving the contents for transformation to triangular sets in Section 2.4.

Positive-dimensional polynomial equation set

Now suppose that F ⊂ K[x] is a positive-dimensional polynomial equation set, and G is a Gr¨obner basis of a = F w.r.t. LEX. Then by the Elimination Theorem (Theorem 1.2.3), one knows that G ∩ K[xl] is precisely a Gr¨obner basis of the elimination ideal al.
Let a = (a1, . . . , al) ∈ Zero(al). Then we call a a partial solution of the polynomial equation set F = 0. The following theorem furnishes a sufficient condition to extend a partial solution.
Theorem 1.4.3 (Extension Theorem). Let a = hF1, . . . , Fsi be an ideal in C[x], and an−1 be its (n−1)th elimination ideal. For each i = 1, . . . , s, write Fi in the form Fi = GixNi n + Hi, where Ni ≤ 0, Gi ∈ C[xn−1] nonzero, and deg(Hi, xn) < Ni. Suppose that c = (c1, . . . , cn−1) ∈ Zero(an−1) is a partial solution. If c 6∈ Zero({G1, . . . ,Gs}), then there exists cn ∈ C such that (c, cn) ∈ Zero(a).

Regular, simple and irreducible triangular sets

Let R be a commutative ring with identity and a ⊂ R an ideal . An element p ∈ R is said to be regular in R if p is neither zero nor a zero divisor in R, and regular modulo a if its standard image in R/a is regular.
Definition 2.3.1. A triangular set T = [T1, . . . , Tr] ⊂ K[x] is called a regular set if ini(Ti) is regular modulo sati−1(T ) for i = 2, . . . , r.
Regular sets are also known as regular chains introduced by Kalkbrener [77] and as proper ascending chains due to Yang and Zhang [167]. They were generalized by Wang [158] to regular systems.
The regular set is one kind of commonly used triangular sets. Next we list some of its remarkable properties for later use. Recall that u and y are the parameters and dependents of a triangular set respectively.

Table of contents :

Introduction
I Background 
Chapter 1 Gr¨obner bases
1.1 Preliminaries
1.2 Gr¨obner bases and Buchberger algorithm
1.3 FGLM algorithm
1.4 Gr¨obner bases for polynomial system solving
Chapter 2 Triangular sets
2.1 Concepts and terminologies
2.2 Characteristic sets and Wu–Ritt algorithm
2.3 Regular, simple and irreducible triangular sets
2.4 Triangular sets for polynomial system solving
Chapter 3 Some constructions in algebra
3.1 Commutative algebra
3.2 Basics of finite fields
II Contributions 
Chapter 4 Sparse FGLM algorithms
4.1 Ideals in shape position
4.2 General ideals
4.3 Multiplication matrices
4.4 Implementation and experimental results
Chapter 5 Simple decomposition over finite fields
5.1 Simple sets revisited
5.2 Zero-dimensional polynomial sets
5.3 Positive-dimensional polynomial sets
5.4 Implementation and experimental results
Chapter 6 Squarefree decomposition and factorization over unmixed products of field extensions
6.1 Unmixed products of field extensions
6.2 Squarefree decomposition over unmixed products
6.3 Factorization over unmixed products
6.4 Examples and experiments
Chapter 7 Applications
7.1 Detection of steady states and their numbers for finite biological models
7.2 Sparse FGLM algorithm for interpolation problem in list decoding
Conclusions
Bibliography

GET THE COMPLETE PROJECT