Biology Reference
In-Depth Information
3.5.2 Postprocessing: The Gröbner Fan Method
Recall fromSection 3.5 that Gröbner bases depend on the choice ofmonomial ordering
and so do resulting models. In order to avoid ambiguity in model selection, we would
like to be able to (1) identify all monomial orderings that cause the Buchberger
algorithm to produce different reduced Gröbner bases; (2) study the effect of these
monomial orderings on the model dynamics; and (3) select the best model according
to some criteria.
A combinatorial structure that contains information about all reduced Gröbner
bases of an ideal, and thus fulfills item (1) from the above list, is the Gröbner fan of
an ideal. It is a polyhedral complex of cones, each corresponding to an initial ideal,
which is in a one-to-one correspondence with the marked reduced Gröbner bases of
the ideal, where “marked” refers to the initial term of each generating polynomial
being distinguished. Here we give a brief introduction to the concept of the Gröbner
fan. For details see, for example, [ 29 ].
A fixed polynomial ideal has only a finite number of different reduced Gröbner
bases. Informally, the reason is that most of the monomial orderings only differ in
high degree and the Buchberger algorithm for Gröbner basis computation does not
“see” the difference among them. However, they may vary greatly in the number
of polynomials and shape. In order to classify them, we first present a convenient
way to define monomial orderings using vectors. Again, we think of a polynomial
in k
x α 1
1
x α n
as a linear combination of monomials of the form x α =
[
x 1 ,...,
x n ]
···
n
n
over a field k , where
α
is the n -tuple exponent
α = 1 ,...,α n ) ∈ Z
0 .
ω = 1 ,...,ω n )
Definition 3.9.
is a vector with real coefficients. It
can be used to define an ordering on the elements of
Suppose that
n
Z
α ω β
0 by
if and only if
α · ω>β · ω
.
We are now almost ready to give a definition of the Gröbner fan. We first define
its building blocks, the Gröbner cones .
Definition 3.10.
be a marked reduced Gröbner basis for
an ideal I . Write each polynomial of the basis as g i
Let
G ={
g 1 ,...,
g r }
+ β
x α i
c i x β , where
=
x α i
n
is the initial term in g i .The cone of
is C G ={ ω ∈ R
0 | α i
· ω β ·
G
ω
.
The collection of all cones for a given ideal is the Gröbner fan of that ideal. The
cones are in bijectionwith themarked reducedGröbner bases of the ideal. Since reduc-
ing a polynomial modulo an ideal I , as the reverse engineering algorithm requires,
can have at most as many outputs as the number of marked reduced Gröbner bases, it
follows that the Gröbner fan contains information about all Gröbner bases (and thus
all monomial orderings) that need to be considered in the process of model selection.
For an example of utilizing the information encoded in the Gröbner fan of an ideal
for reverse engineering of PDSs, see [ 30 ].
There are algorithms based on the Gröbner fan that enumerate all marked reduced
Gröbner bases of a polynomial ideal. An excellent implementation of such an algo-
rithm is the software package Gfan [ 31 ].
for all i
,
j with c i =
0
}
 
Search WWH ::




Custom Search