hide
Free keywords:
Quantitative Biology, Molecular Networks, q-bio.MN,Computer Science, Symbolic Computation, cs.SC,Mathematics, Algebraic Geometry, math.AG
Abstract:
We consider the problem of testing whether the points in a complex or real
variety with non-zero coordinates form a multiplicative group or, more
generally, a coset of a multiplicative group. For the coset case, we study the
notion of shifted toric varieties which generalizes the notion of toric
varieties. This requires a geometric view on the varieties rather than an
algebraic view on the ideals. We present algorithms and computations on 129
models from the BioModels repository testing for group and coset structures
over both the complex numbers and the real numbers. Our methods over the
complex numbers are based on Gr\"obner basis techniques and binomiality tests.
Over the real numbers we use first-order characterizations and employ real
quantifier elimination. In combination with suitable prime decompositions and
restrictions to subspaces it turns out that almost all models show coset
structure. Beyond our practical computations, we give upper bounds on the
asymptotic worst-case complexity of the corresponding problems by proposing
single exponential algorithms that test complex or real varieties for toricity
or shifted toricity. In the positive case, these algorithms produce generating
binomials. In addition, we propose an asymptotically fast algorithm for testing
membership in a binomial variety over the algebraic closure of the rational
numbers.
