An official website of the United States government
A new approach for Gröbner bases conversion of polynomial ideals (over a field) of arbitrary dimension is presented. In contrast to the only other approach based on Gröbner fan and Gröbner walk for positive dimensional ideals, the proposed approach is simpler to understand, prove, and implement. It is based on defining for a given polynomial, a truncated sub-polynomial consisting of all monomials that can possibly become the leading monomial with respect to the target ordering: the monomials between the leading monomial of the target ordering and the leading monomial of the initial ordering. The main ingredient of the new algorithm is the computation of a Gröbner basiswith respect tothe target ordering for the ideal generated by such truncated parts of the input Gröbner basis. This is done using the extended Buchberger algorithm that also outputs the relationship between the input and output bases. That information is used in attempts to recover a Gröbner basis of the idealwith respect tothe target ordering. In general, more than one iteration may be needed to get a Gröbner basiswith respect tothe target ordering since truncated polynomials may miss some leading monomials. The new algorithm has been implemented inMapleand its operation is illustrated using an example. The performance of this implementation is compared with the implementations of other approaches inMaple.In practice, a Gröbner basiswith respect toa target ordering can be computed in a single iteration on most examples.
more »
« less
Algorithms for computing greatest common divisors of parametric multivariate polynomials
Two new efficient algorithms for computing greatest common divisors (gcds) of parametric multivariate polynomials over k[U][X]are presented. The key idea of the first algorithm is that the gcd of two non-parametric multivariate polynomials can be obtained by dividing their product by the generator of the intersection of two principal ideals generated by the polynomials. The second algorithm is based on another simple insight that the gcd can be extracted using the generator of the ideal quotient of a polynomial with respect to the second polynomial. Since the ideal intersection and ideal quotient in these cases are also principal ideals, their generators can be obtained by computing minimal Gröbner bases of the ideal intersection and ideal quotient, respectively. To avoid introducing new variables which can adversely affect the efficiency, minimal Gröbner bases computations are performed on modules. Both of these constructions generalize to the parametric case as shown in the paper. Comprehensive Gröbner system constructions are used for the parametric ideal intersection and ideal quotient using the Kapur-Sun-Wang’s algorithm. It is proved that whether in a minimal comprehensive Gröbner system of a parametric ideal 20intersection or in that of a parametric ideal quotient, each branch of the specializations corresponds to a principal parametric ideal with a single generator. Using this generator, the parametric gcd of that branch is obtained by division. For the case of more than two parametric polynomials, we can use the above two algorithms to compute gcds recursively, and get an extended algorithm by generalizing the idea of the second algorithm. Algorithms do not suffer from having to apply expensive steps such as ensuring whether parametric polynomials are primitive w.r.t. the main variable as used in both the algorithms proposed by Nagasaka (ISSAC, 2017). The resulting algorithms are not only conceptually simple to understand but are more efficient in practice. The proposed algorithms and both of Nagasaka’s algorithms have been implemented in Singular, and their performance is compared on a number of examples.
more »
« less
- Award ID(s):
- 1908804
- PAR ID:
- 10642524
- Publisher / Repository:
- Elsevier
- Date Published:
- Journal Name:
- Journal of symbolic computation
- ISSN:
- 1095-855X
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Principal symmetric ideals were recently introduced by Harada et al. in [The minimal free resolution of a general principal symmetric ideal, preprint (2023), arXiv:2308.03141], where their homological properties are elucidated. They are ideals generated by the orbit of a single polynomial under permutations of variables in a polynomial ring. In this paper, we determine when a product of two principal symmetric ideals is principal symmetric and when the powers of a principal symmetric ideal are again principal symmetric ideals. We characterize the ideals that have the latter property as being generated by polynomials invariant up to a scalar multiple under permutation of variables. Recognizing principal symmetric ideals is an open question for the purpose of which we produce certain obstructions. We also demonstrate that the Hilbert functions of symmetric monomial ideals are not all given by symmetric monomial ideals, in contrast to the non-symmetric case.more » « less
-
Abstract We study a class of combinatorially defined polynomial ideals that are generated by minors of a generic symmetric matrix. Included within this class are the symmetric determinantal ideals, the symmetric ladder determinantal ideals, and the symmetric Schubert determinantal ideals of A. Fink, J. Rajchgot, and S. Sullivant. Each ideal in our class is a type C analog of a Kazhdan–Lusztig ideal of A. Woo and A. Yong; that is, it is the scheme‐theoretic defining ideal of the intersection of a type C Schubert variety with a type C opposite Schubert cell, appropriately coordinatized. The Kazhdan–Lusztig ideals that arise are exactly those where the opposite cell is 123‐avoiding. Our main results include Gröbner bases for these ideals, prime decompositions of their initial ideals (which are Stanley–Reisner ideals of subword complexes), and combinatorial formulas for their multigraded Hilbert series in terms of pipe dreams.more » « less
-
In the context of modeling biological systems, it is of interest to generate ideals of points with a unique reduced Gröbner basis, and the first main goal of this paper is to identify classes of ideals in polynomial rings which share this property. Moreover, we provide methodologies for constructing such ideals. We then relax the condition of uniqueness. The second and most relevant topic discussed here is to consider and identify pairs of ideals with the same number of reduced Gröbner bases, that is, with the same cardinality of their associated Gröbner fan.more » « less
-
We introduce a hitting set generator for Polynomial Identity Testing based on evaluations of low-degree univariate rational functions at abscissas associated with the variables. We establish an equivalence up to rescaling with a generator introduced by Shpilka and Volkovich, which has a similar structure but uses multivariate polynomials. We initiate a systematic analytic study of the power of hitting set generators by characterizing their vanishing ideals, i.e., the sets of polynomials that they fail to hit. We provide two such characterizations for our generator. First, we develop a small collection of polynomials that jointly produce the vanishing ideal. As corollaries, we obtain tight bounds on the minimum degree, sparseness, and partition class size of set-multilinearity in the vanishing ideal. Second, inspired by a connection to alternating algebra, we develop a structured deterministic membership test for the multilinear part of the vanishing ideal. We present a derivation based on alternating algebra along with the required background, as well as one in terms of zero substitutions and partial derivatives, avoiding the need for alternating algebra. As evidence of the utility of our analytic approach, we rederive known derandomization results based on the generator by Shpilka and Volkovich and present a new application in derandomization / lower bounds for read-once oblivious algebraic branching programs.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
