An official website of the United States government
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
The Number of Gröbner Bases in Finite Fields
In the field of algebraic systems biology, the number of minimal polynomial models constructed using discretized data from an underlying system is related to the number of distinct reduced Groebner bases for the ideal of the data points. While the theory of Groebner bases is extensive, what is missing is a closed form for their number for a given ideal. This work contributes connections between the geometry of data points and the number of Groebner bases associated to small data sets. Furthermore we improve an existing upper bound for the number of Groebner bases specialized for data over a finite field.
more »
« less
- Award ID(s):
- 1720335
- PAR ID:
- 10177092
- Date Published:
- Journal Name:
- Association for Women in Mathematics series
- Volume:
- 21
- ISSN:
- 2364-5741
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We present results and conjectures on the connection between the convexity of a neural code and the canonical form of its ideal. The connection is established through properties of the Gröbner basis of the neural ideal and the uniqueness of its reduced form. An efficient algorithm for identifying neural codes with unique reduced Gröbner bases is introduced.more » « less
-
Eliassi-Rad, Tina (Ed.)Multidimensional unfolding methods are widely used for visualizing item response data. Such methods project respondents and items simultaneously onto a low-dimensional Eu- clidian space, in which respondents and items are represented by ideal points, with person- person, item-item, and person-item similarities being captured by the Euclidian distances between the points. In this paper, we study the visualization of multidimensional unfold- ing from a statistical perspective. We cast multidimensional unfolding into an estimation problem, where the respondent and item ideal points are treated as parameters to be esti- mated. An estimator is then proposed for the simultaneous estimation of these parameters. Asymptotic theory is provided for the recovery of the ideal points, shedding lights on the validity of model-based visualization. An alternating projected gradient descent algorithm is proposed for the parameter estimation. We provide two illustrative examples, one on users’ movie rating and the other on senate roll call voting.more » « less
-
Amir Hashemi (Ed.)We present Hermite polynomial interpolation algorithms that for a sparse univariate polynomial f with coefficients from a field compute the polynomial from fewer points than the classical algorithms. If the interpolating polynomial f has t terms, our algorithms, require argument/value triples (w^i, f(w^i), f'(w^i)) for i=0,...,t + ceiling( (t+1)/2 ) - 1, where w is randomly sampled and the probability of a correct output is determined from a degree bound for f. With f' we denote the derivative of f. Our algorithms generalize to multivariate polynomials, higher derivatives and sparsity with respect to Chebyshev polynomial bases. We have algorithms that can correct errors in the points by oversampling at a limited number of good values. If an upper bound B >= t for the number of terms is given, our algorithms use a randomly selected w and, with high probability, ceiling( t/2 ) + B triples, but then never return an incorrect output. The algorithms are based on Prony's sparse interpolation algorithm. While Prony's algorithm and its variants use fewer values, namely, 2t+1 and t+B values f(w^i), respectively, they need more arguments w^i. The situation mirrors that in algebraic error correcting codes, where the Reed-Solomon code requires fewer values than the multiplicity code, which is based on Hermite interpolation, but the Reed-Solomon code requires more distinct arguments. Our sparse Hermite interpolation algorithms can interpolate polynomials over finite fields and over the complex numbers, and from floating point data. Our Prony-based approach does not encounter the Birkhoff phenomenon of Hermite interpolation, when a gap in the derivative values causes multiple interpolants. We can interpolate from t+1 values of f and 2t-1 values of f'.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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1007/978-3-030-42687-3_9
