Vector space bases associated to vanishing ideals of points

DOI10.1016/J.JPAA.2009.05.013MaRDI QIDQ2655003zbMATH OpenOpenAlexFDO

Publication date 22 January 2010

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0808.3591

ideals of points normal form standard monomials

Polynomial rings and ideals; rings of integer-valued polynomials (13F20) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Affine geometry (14R99)

Abstract: We discuss four different constructions of vector space bases associated to vanishing ideals of points. We show how to compute normal forms with respect to these bases and give new complexity bounds. As an application, we improve the computational algebra approach to the reverse engineering of gene regulatory networks.

Review text

The author discusses four different constructions of vector space bases associated to vanishing ideals of points and he shows how to compute normal forms with respect to these bases giving new complexity bounds. Let \(k[x_1, \dots, x_n]\) be the polynomial ring in \(n\) variables over a field \(k\). The vanishing ideal \(I\) with respect to a set of points \(\{p_1, \dots, p_n\}\) in \(k^n\) is defined as the set of elements of \(k[x_1, \dots, x_n]\) that are zero on all of the \(p_i\)'s. The main tool that is used to compute vanishing ideals of points is the Buchberger-Möller algorithm which returns a Gröbner basis for the ideal vanishing on the set \(\{p_1, \dots, p_n\}\). A complementary result of the algorithm is a vector space basis for the quotient ring \(k[x_1, \dots, x_n]/I\). In several applications it turns out that the attention is more related on this vector space basis than in the Gröbner basis. For example, it may be preferable to compute normal forms using vector spaces methods instead of Gröbner basis techniques. Thus the author introduces four different approaches for the construction of the vector space basis, all of which perform better than the Buchberger-Möller algorithm. The first construction produces a vector space basis, for the quotient ring, given by a family of separators, that is, a family \(\{f_1, \dots, f_n\}\) of polynomials such that \(f_i(p_i)=1\) and \(f_i(p_j)=0\) if \(i\not= j\). The second construction is a \(k-\)basis formed by the residues \(1,f,\dots, f^{m-1}\), where \(f\) is a linear form. The third construction produces a set of monomials outside the initial ideal of \(I\) with respect to the lexicographical ordering, using only combinatorial methods. Finally, the fourth construction gives a \(k-\)basis which is the complement of the initial ideal with respect to a class of admissible monomial orders. A fundamental element for the effectiveness of these methods is a fast combinatorial algorithm which gives useful structure informations about the relations between the points. As an important application, the author drastically improves the computational algebra approach to the reverse engineering of gene regularity networks.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Vector space bases associated to vanishing ideals of points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2655003)