50 results
Search Results
2. Construction of free differential algebras by extending Gröbner-Shirshov bases.
- Author
-
Li, Yunnan and Guo, Li
- Subjects
- *
GROBNER bases , *ALGEBRA , *POLYNOMIALS , *DIFFERENTIAL algebra - Abstract
As a fundamental notion, the free differential algebra on a set is concretely constructed as the polynomial algebra on the differential variables. Such a construction is not known for the more general notion of the free differential algebra on an algebra, from the left adjoint functor of the forgetful functor from differential algebras to algebras, instead of sets. In this paper we show that a generator-relation presentation of a base algebra can be extended to the free differential algebra on this base algebra. More precisely, a Gröbner-Shirshov basis property of the base algebra can be extended to the free differential algebra on this base algebra, allowing a Poincaré-Birkhoff-Witt type basis for these more general free differential algebras. Examples are provided as illustrations. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
3. Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squares.
- Author
-
Gaar, Elisabeth, Krenn, Daniel, Margulies, Susan, and Wiegele, Angelika
- Subjects
- *
LOGICAL prediction , *DOMINATING set , *SEMIDEFINITE programming , *EVIDENCE , *GROBNER bases - Abstract
Vizing's conjecture (open since 1968) relates the product of the domination numbers of two graphs to the domination number of their Cartesian product graph. In this paper, we formulate Vizing's conjecture as a Positivstellensatz existence question. In particular, we select classes of graphs according to their number of vertices and their domination number and encode the conjecture as an ideal/polynomial pair such that the polynomial is non-negative on the variety associated with the ideal if and only if the conjecture is true for this graph class. Using semidefinite programming we obtain numeric sum-of-squares certificates, which we then manage to transform into symbolic certificates confirming non-negativity of our polynomials. Specifically, we obtain exact low-degree sparse sum-of-squares certificates for particular classes of graphs. The obtained certificates allow generalizations for larger graph classes. Besides computational verification of these more general certificates, we also present theoretical proofs as well as conjectures and questions for further investigations. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
4. Computing strong regular characteristic pairs with Gröbner bases.
- Author
-
Dong, Rina and Wang, Dongming
- Subjects
- *
GROBNER bases , *BASE pairs , *ALGORITHMS , *POLYNOMIALS - Abstract
The W-characteristic set of a polynomial ideal is the minimal triangular set contained in the reduced lexicographical Gröbner basis of the ideal. A pair (G , C) of polynomial sets is a strong regular characteristic pair if G is a reduced lexicographical Gröbner basis, C is the W-characteristic set of the ideal 〈 G 〉 , the saturated ideal sat (C) of C is equal to 〈 G 〉 , and C is regular. In this paper, we show that for any polynomial ideal I with given generators one can either detect that I is unit, or construct a strong regular characteristic pair (G , C) by computing Gröbner bases such that I ⊆ sat (C) = 〈 G 〉 and sat (C) divides I , so the ideal I can be split into the saturated ideal sat (C) and the quotient ideal I : sat (C). Based on this strategy of splitting by means of quotient and with Gröbner basis and ideal computations, we devise a simple algorithm to decompose an arbitrary polynomial set F into finitely many strong regular characteristic pairs, from which two representations for the zeros of F are obtained: one in terms of strong regular Gröbner bases and the other in terms of regular triangular sets. We present some properties about strong regular characteristic pairs and characteristic decomposition and illustrate the proposed algorithm and its performance by examples and experimental results. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
5. Sum-of-squares certificates for Vizing's conjecture via determining Gröbner bases.
- Author
-
Gaar, Elisabeth and Siebenhofer, Melanie
- Subjects
- *
GROBNER bases , *SUM of squares , *LOGICAL prediction , *DOMINATING set , *SEMIDEFINITE programming - Abstract
The famous open Vizing conjecture claims that the domination number of the Cartesian product graph of two graphs G and H is at least the product of the domination numbers of G and H. Recently Gaar, Krenn, Margulies and Wiegele used the graph class G of all graphs with n G vertices and domination number k G and reformulated Vizing's conjecture as the problem that for all graph classes G and H the Vizing polynomial is sum-of-squares (SOS) modulo the Vizing ideal. By solving semidefinite programs (SDPs) and clever guessing they derived SOS-certificates for some values of k G , n G , k H , and n H. In this paper, we consider their approach for k G = k H = 1. For this case we are able to derive the unique reduced Gröbner basis of the Vizing ideal. Based on this, we deduce the minimum degree (n G + n H − 1) / 2 of an SOS-certificate for Vizing's conjecture, which is the first result of this kind. Furthermore, we present a method to find certificates for graph classes G and H with n G + n H − 1 = d for general d , which is again based on solving SDPs, but does not depend on guessing and depends on much smaller SDPs. We implement our new method in SageMath and give new SOS-certificates for all graph classes G and H with k G = k H = 1 and n G + n H ≤ 15. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
6. A "pseudo-polynomial" algorithm for the Frobenius number and Gröbner basis.
- Author
-
Morales, Marcel and Dung, Nguyen Thi
- Subjects
- *
GROBNER bases , *ARITHMETIC series , *ALGORITHMS - Abstract
Given n ⩾ 2 and a 1 , ... , a n ∈ N. Let S = 〈 a 1 , ... , a n 〉 be a semigroup. The aim of this paper is to give an effective pseudo-polynomial algorithm on a 1 , which computes the Apéry set and the Frobenius number of S. We also find the Gröbner basis of the toric ideal defined by S , for the weighted degree reverse lexicographical order ≺ w to x 1 , ... , x n , without using Buchberger's algorithm. As an application we introduce and study some special classes of semigroups. Namely, when S is generated by generalized arithmetic progressions and generalized almost arithmetic progressions with the ratio a positive or a negative number. We determine symmetric and almost symmetric semigroups generated by a generalized arithmetic progression. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
7. Homogeneous Einstein metrics on Stiefel manifolds associated to flag manifolds with two isotropy summands.
- Author
-
Arvanitoyeorgos, Andreas, Sakane, Yusuke, and Statha, Marina
- Subjects
- *
EINSTEIN manifolds , *MANIFOLDS (Mathematics) , *GROBNER bases , *HOMOGENEOUS spaces , *PARAMETRIC equations - Abstract
We study invariant Einstein metrics on the Stiefel manifold V k R n ≅ SO (n) / SO (n − k) of all orthonormal k -frames in R n. The isotropy representation of this homogeneous space contains equivalent summands, so a complete description of G -invariant metrics is not easy. In this paper we view the manifold V 2 p R n as total space over a classical generalized flag manifold with two isotropy summands and prove for 2 ≤ p ≤ 2 5 n − 1 it admits at least four invariant Einstein metrics determined by Ad (U (p) × SO (n − 2 p)) -invariant scalar products. Two of the metrics are Jensen's metrics and the other two are new Einstein metrics. The Einstein equation reduces to a parametric system of polynomial equations, which we study by combining Gröbner bases and geometrical arguments. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
8. Symbolic computation on the partition lattice of an n-set.
- Author
-
Li, Yongbin, Fu, Qiuju, and Deng, Renbin
- Subjects
- *
SYMBOLIC computation , *FINITE fields , *CHARACTERISTIC functions , *ALGEBRA , *GROBNER bases , *POLYNOMIALS - Abstract
In this paper, an injection from the partition lattice Π n to a zero-dimensional affine algebra over the finite field F 2 is constructed. We study some interesting properties of the injection and present two direct sum decompositions of the zero-dimensional affine algebra. Based upon these, some properties of Π n are revealed in an algebraic manner, for instance, the rank-generating function and characteristic polynomial of Π n can be derived using the symbolic method. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
9. Computing Gröbner bases of pure binomial ideals via submodules of
- Author
-
Boffi, Giandomenico and Logar, Alessandro
- Subjects
- *
POLYNOMIAL rings , *BINOMIAL equations , *ALGORITHMS , *CONES , *ABELIAN groups , *GROUP theory - Abstract
Abstract: A binomial ideal is an ideal of the polynomial ring which is generated by binomials. In a previous paper, we gave a correspondence between pure saturated binomial ideals of and submodules of and we showed that it is possible to construct a theory of Gröbner bases for submodules of . As a consequence, it is possible to follow alternative strategies for the computation of Gröbner bases of submodules of (and hence of binomial ideals) which avoid the use of Buchberger algorithm. In the present paper, we show that a Gröbner basis of a -module of rank lies into a finite set of cones of which cover a half-space of . More precisely, in each of these cones , we can find a suitable subset which has the structure of a finite abelian group and such that a Gröbner basis of the module (and hence of the pure saturated binomial ideal represented by ) is described using the elements of the groups together with the generators of the cones. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
10. Ideals of the form I1(XY).
- Author
-
Saha, Joydip, Sengupta, Indranath, and Tripathi, Gaurab
- Subjects
- *
MATRICES (Mathematics) , *BETTI numbers , *HOMOLOGY theory , *EULER characteristic , *ALGEBRA - Abstract
Abstract In this paper we compute Gröbner bases for determinantal ideals of the form I 1 (X Y) , where X and Y are both matrices whose entries are indeterminates over a field K. We use the Gröbner basis structure to determine Betti numbers for such ideals. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
11. A factorization algorithm for G-algebras and its applications.
- Author
-
Levandovskyy, Viktor and Heinle, Albert
- Subjects
- *
FACTORIZATION , *RING theory , *FINITE element method , *RATIONAL root theorem , *ALGORITHMIC randomness , *MATHEMATICAL models - Abstract
Factorization of polynomials into irreducible factors is an important problem with numerous applications, both over commutative and over non-commutative rings. It has been recently proved by Bell, Heinle and Levandovskyy that a large class of non-commutative algebras are finite factorization domains (FFD for short). This provides a termination criterion for a factorization algorithms of elements in a vast class of finitely presented K -algebras, which includes the ubiquitous G -algebras, encompassing algebras of common linear partial functional operators. In this paper, we contribute an algorithm to find all distinct factorizations of a given element in a G -algebra, with minor assumptions on the underlying field, and establish its complexity. Moreover, the property of being an FFD, in combination with the factorization algorithm, enables us to generalize the factorizing Gröbner basis algorithm for G -algebras. This algorithm is useful for various applications, e.g. in analysis of solution spaces of systems of linear partial functional equations with polynomial coefficients. Additionally, it is possible to include inequality constraints for ideals in the input. The developed algorithms are accompanied by freely available implementations and illustrated by interesting examples. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
12. Prony's method in several variables: Symbolic solutions by universal interpolation.
- Author
-
Sauer, Tomas
- Subjects
- *
MULTIVARIATE analysis , *POLYNOMIALS , *INTERPOLATION , *MATHEMATICAL variables , *SYMBOLIC computation , *GEOMETRIC connections - Abstract
The paper considers a symbolic approach to Prony's method in several variables and its close connection to multivariate polynomial interpolation. Based on the concept of universal interpolation that can be seen as a weak generalization of univariate Chebychev systems, we can give estimates on the minimal number of evaluations needed to solve Prony's problem. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
13. Border bases for lattice ideals.
- Author
-
Boffi, Giandomenico and Logar, Alessandro
- Subjects
- *
LATTICE theory , *IDEALS (Algebra) , *GROBNER bases , *VECTOR spaces , *MODULES (Algebra) - Abstract
The main ingredient to construct an O -border basis of an ideal I ⊆ K [ x 1 , … , x n ] is the order ideal O , which is a basis of the K -vector space K [ x 1 , … , x n ] / I . In this paper we give a procedure to find all the possible order ideals associated with a lattice ideal I M (where M is a lattice of Z n ). The construction can be applied to ideals of any dimension (not only zero-dimensional) and shows that the possible order ideals are always in a finite number. For lattice ideals of positive dimension we also show that, although a border basis is infinite, it can be defined in finite terms. Furthermore we give an example which proves that not all border bases of a lattice ideal come from Gröbner bases. Finally, we give a complete and explicit description of all the border bases for ideals I M in case M is a 2-dimensional lattice contained in Z 2 . [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
14. Computational aspects of retrieving a representation of an algebraic geometry code.
- Author
-
Márquez-Corbella, Irene, Martínez-Moro, Edgar, Pellikaan, Ruud, and Ruano, Diego
- Subjects
- *
CODING theory , *QUANTUM computers , *ALGEBRAIC geometry , *CYBERTERRORISM , *CRYPTOSYSTEMS , *REPRESENTATIONS of algebras , *TOPOLOGICAL degree , *CRYPTOGRAPHY - Abstract
Abstract: Code-based cryptography is an interesting alternative to classic number-theoretic public key cryptosystem since it is conjectured to be secure against quantum computer attacks. Many families of codes have been proposed for these cryptosystems such as algebraic geometry codes. In Márquez-Corbella et al. (2012) – for so called very strong algebraic geometry codes , where is an algebraic curve over , is an n-tuple of mutually distinct -rational points of and E is a divisor of with disjoint support from – it was shown that an equivalent representation can be found. The n-tuple of points is obtained directly from a generator matrix of , where the columns are viewed as homogeneous coordinates of these points. The curve is given by , the homogeneous elements of degree 2 of the vanishing ideal . Furthermore, it was shown that can be computed efficiently as the kernel of certain linear map. What was not shown was how to get the divisor F and how to obtain efficiently an adequate decoding algorithm for the new representation. The main result of this paper is an efficient computational approach to the first problem, that is getting F. The security status of the McEliece public key cryptosystem using algebraic geometry codes is still not completely settled and is left as an open problem. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
15. Ideal-specific elimination orders form a star-shaped region.
- Author
-
Bosse, Hartwig, Gärtner, Christine, and Golubitsky, Oleg
- Subjects
- *
ELIMINATION (Mathematics) , *POLYNOMIALS , *GROBNER bases , *MATHEMATICAL forms , *MATHEMATICAL variables , *COMPUTER algorithms - Abstract
This paper shows that for any given polynomial ideal the collection of Gröbner cones corresponding to -specific elimination orders forms a star-shaped region which contrary to first intuition in general is not convex. Moreover we show that the corresponding region may contain Gröbner cones intersecting in the boundary of the Gröbner fan in the origin only. This implies that Gröbner walks aiming for the elimination of variables from a polynomial ideal can be terminated earlier than previously known. We provide a slightly improved stopping criterion for a known Gröbner walk algorithm for the elimination of variables. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
16. Proving isometry for homogeneous Einstein metrics on flag manifolds by symbolic computation.
- Author
-
Arvanitoyeorgos, Andreas, Chrysikos, Ioannis, and Sakane, Yusuke
- Subjects
- *
HOMOGENEOUS spaces , *METRIC geometry , *MANIFOLDS (Mathematics) , *PARAMETRIC modeling , *POLYNOMIALS , *DIFFERENTIAL geometry - Abstract
The question whether two Riemannian metrics on a certain manifold are isometric is a fundamental and also a challenging problem in differential geometry. In this paper we ask whether two non-Kähler homogeneous Einstein metrics on a certain flag manifold are isometric. We tackle this question by reformulating it into a related question on a parametric system of polynomial equations and answering it by carefully combining Gröbner bases and geometrical arguments. Using this technique, we are able to prove the isometry of such metrics. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
17. Structures of precision losses in computing approximate Gröbner bases
- Author
-
Liang, Ye
- Subjects
- *
APPROXIMATION theory , *PRECISION (Information retrieval) , *FLOATING-point arithmetic , *COEFFICIENTS (Statistics) , *POLYNOMIALS , *COMPUTATIONAL complexity , *MATHEMATICAL programming - Abstract
Abstract: In computing approximate Gröbner bases, it is not easy to trace precision losses of floating-point coefficients of intermediate approximate polynomials. The measured precision losses are usually much larger than their genuine values. One reason causing this phenomenon is that most existing methods for tracing precision losses do not consider the dependence of such precision losses in any polynomial (as an equation). In this paper, we define an algebraic structure called PL-space (precision loss space) for a polynomial (as an equation) and set up a theory for it. We prove that any PL-space has a finite weak basis and a strong basis and show how they effect on tracing precision losses by an example. Based on the study of minimal strong bases, we propose the concept of dependence number which reveals the complexity of the dependence of precision losses in a polynomial. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
18. Selecting lengths of floats for the computation of approximate Gröbner bases
- Author
-
Liang, Ye
- Subjects
- *
GROBNER bases , *APPROXIMATION theory , *ALGORITHMS , *PONTOONS , *BENCHMARK testing (Engineering) , *POLYNOMIALS , *COEFFICIENTS (Statistics) , *MATHEMATICAL programming - Abstract
Abstract: The computation of approximate Gröbner bases is reported to be highly unstable in the literature. Selecting a suitable length of floats is helpful for stabilizing this computation. In this paper, we present a method to compute such a suitable length of floats. We concentrate on a family of polynomial systems sharing the same support and study the relation between the lengths of floats and the coefficients of relevant polynomials. Then we give a reference length of floats for all the polynomial systems in the family. One feature of our method is that it need not utilize numerical algorithms of Gröbner bases. Hence, our method can avoid the influence of the instabilities of the existing numerical algorithms and thus will be helpful for designing stable ones (e.g., stable Shirayanagiʼs algorithm). Experiments show that our method can work out reliable and reasonably large lengths of floats for most of the tested benchmarks. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
19. Algorithms for integrals of holonomic functions over domains defined by polynomial inequalities
- Author
-
Oaku, Toshinori
- Subjects
- *
HOLONOMY groups , *MATHEMATICAL inequalities , *INTEGRAL functions , *THEORY of distributions (Functional analysis) , *LINEAR differential equations , *POLYNOMIALS - Abstract
Abstract: A holonomic function is a differentiable or generalized function which satisfies a holonomic system of linear partial or ordinary differential equations with polynomial coefficients. The main purpose of this paper is to present algorithms for computing a holonomic system for the definite integral of a holonomic function with parameters over a domain defined by polynomial inequalities. If the integrand satisfies a holonomic difference–differential system including parameters, then a holonomic difference–differential system for the integral can also be computed. In the algorithms, holonomic distributions (generalized functions in the sense of L. Schwartz) are inevitably involved even if the integrand is a usual function. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
20. Root isolation of zero-dimensional polynomial systems with linear univariate representation
- Author
-
Cheng, Jin-San, Gao, Xiao-Shan, and Guo, Leilei
- Subjects
- *
POLYNOMIALS , *UNIVARIATE analysis , *LINEAR algebra , *ALGORITHMS , *ACCURACY , *SYMBOLIC computation - Abstract
Abstract: In this paper, a linear univariate representation for the roots of a zero-dimensional polynomial equation system is presented, where the complex roots of the polynomial system are represented as linear combinations of the roots of several univariate polynomial equations. An algorithm is proposed to compute such a representation for a given zero-dimensional polynomial equation system based on Gröbner basis computation. The main advantage of this representation is that the precision of the roots of the system can be easily controlled. In fact, based on the linear univariate representation, we can give the exact precisions needed for isolating the roots of the univariate equations in order to obtain roots of the polynomial system with a given precision. As a consequence, a root isolating algorithm for a zero-dimensional polynomial equation system can be easily derived from its linear univariate representation. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
21. Lattice Polly Cracker cryptosystems
- Author
-
Caboara, Massimo, Caruso, Fabrizio, and Traverso, Carlo
- Subjects
- *
PUBLIC key cryptography , *LATTICE theory , *BINOMIAL theorem , *MATHEMATICAL optimization , *ALGEBRA , *HERMITE polynomials , *GROUP theory , *IDEALS (Algebra) - Abstract
Abstract: Using Gröbner bases for the construction of public key cryptosystems has been often attempted, but has always failed. We review the reason for these failures, and show that only ideals generated by binomials may give a successful cryptosystem. As a consequence, we concentrate on binomial ideals that correspond to Euclidean lattices. We show how to build a cryptosystem based on lattice ideals and their Gröbner bases, and, after breaking a simple variant, we construct a more elaborate one. In this variant the trapdoor information consists in a “small” change of coordinates that allows one to recover a “fat” Gröbner basis. While finding a change of coordinates giving a fat Gröbner basis is a relatively easy problem, finding a small one seems to be a hard optimization problem. This paper develops the details and proofs related to computer algebra, the cryptographic details related to security, the comparison with other lattice cryptosystems and discusses the implementation. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
22. Artificial discontinuities of single-parametric Gröbner bases
- Author
-
Faugère, Jean-Charles and Liang, Ye
- Subjects
- *
DISCONTINUOUS groups , *GROBNER bases , *APPROXIMATION theory , *POLYNOMIALS , *PARAMETER estimation , *ZERO (The number) , *IDEALS (Algebra) , *MATHEMATICAL variables - Abstract
Abstract: Artificial discontinuity is a kind of singularity at a parametric point in computing the Gröbner basis of a specialized parametric ideal w.r.t. a certain term order. When it occurs, though parameters change continuously at the point and the properties of the parametric ideal have no sudden changes, the Gröbner basis will still have a jump at the parametric point. This phenomenon can cause instabilities in computing approximate Gröbner bases. In this paper, we study artificial discontinuities in single-parametric case by proposing a solid theoretical foundation for them. We provide a criterion to recognize artificial discontinuities by comparing the zero point numbers of specialized parametric ideals. Moreover, we prove that for a single-parametric polynomial ideal with some restrictions, its artificially discontinuous specializations (ADS) can be locally repaired to continuous specializations (CS) by the TSV (Term Substitution with Variables) strategy. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
23. Looking for Gröbner basis theory for (almost) skew 2-nomial algebras
- Author
-
Li, Huishi
- Subjects
- *
GROBNER bases , *DIVISION rings , *POLYNOMIALS , *EXISTENCE theorems , *QUANTUM theory , *YANG-Baxter equation - Abstract
Abstract: In this paper, we introduce (almost) skew 2-nomial algebras and look for a one-sided or two-sided Gröbner basis theory for such algebras at a modest level. That is, we establish the existence of a skew multiplicative -basis for every skew 2-nomial algebra, and we explore the existence of a (left, right, or two-sided) monomial ordering for an (almost) skew 2-nomial algebra. As distinct from commonly recognized algebras holding a Gröbner basis theory (such as algebras of the solvable type () and some of their homomorphic images), a subclass of skew 2-nomial algebras that have a left Gröbner basis theory but may not necessarily have a two-sided Gröbner basis theory, respectively a subclass of skew 2-nomial algebras that have a right Gröbner basis theory but may not necessarily have a two-sided Gröbner basis theory, are determined such that numerous quantum binomial algebras (which provide binomial solutions to the Yang–Baxter equation) and their Koszul dual () are involved. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
24. Parametric polynomial spectral factorization using the sum of roots and its application to a control design problem
- Author
-
Anai, Hirokazu, Hara, Shinji, Kanno, Masaaki, and Yokoyama, Kazuhiro
- Subjects
- *
SIGNAL processing , *GROBNER bases , *FACTORIZATION , *MATHEMATICAL optimization , *ALGEBRA , *NUMERICAL analysis - Abstract
Abstract: This paper presents an algebraic approach to polynomial spectral factorization, an important mathematical tool in signal processing and control. The approach exploits an intriguing relationship between the theory of Gröbner bases and polynomial spectral factorization which can be observed through the sum of roots, and allows us to perform polynomial spectral factorization in the presence of real parameters. It is discussed that parametric polynomial spectral factorization enables us to express quantities such as the optimal cost in terms of parameters and the sum of roots. Furthermore an optimization method over parameters is suggested that makes use of the results from parametric polynomial spectral factorization and also employs two quantifier elimination techniques. This proposed approach is demonstrated in a numerical example of a particular control problem. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
25. On Lawrence semigroups
- Author
-
Pisón-Casares, Pilar and Vigneron-Tenorio, Alberto
- Subjects
- *
MATHEMATICS , *MATHEMATICAL analysis , *ALGEBRA , *DIOPHANTINE equations - Abstract
Abstract: Lawrence semigroups arise as a tool to compute Graver bases of semigroup ideals. It is known that the minimal free resolution of semigroup ideals is characterized by the reduced homologies of certain simplicial complexes. In this paper we study the minimal degrees of a Lawrence semigroup ideal and its first syzygy given a combinatorial characterization of the nonvanishing cycles in their associated reduced homologies. We specialize the results that appeared in [Briales, E., Campillo, A., Marijuán, C., Pisón, P., 1998. Minimal systems of generators for ideals of semigroups. J. Pure Appl. Algebra, 127, 7–30] and [Pisón-Casares, P., Vigneron-Tenorio, A., 2001. First syzygies of toric varieties and diophantine equations in congruence. Comm. Alg. 29 (4), 1445–1466] to the Lawrence semigroups. [Copyright &y& Elsevier]
- Published
- 2008
- Full Text
- View/download PDF
26. Gröbner bases and the number of Latin squares related to autotopisms of order ≤7
- Author
-
Falcón, R.M. and Martín-Morales, J.
- Subjects
- *
ALGEBRA , *MATHEMATICAL analysis , *ALGORITHMS , *LINEAR systems - Abstract
Abstract: Latin squares can be seen as multiplication tables of quasigroups, which are, in general, non-commutative and non-associative algebraic structures. The number of Latin squares having a fixed isotopism in their autotopism group is at the moment an open problem. In this paper, we use Gröbner bases to describe an algorithm that allows one to obtain the previous number. Specifically, this algorithm is implemented in Singular to obtain the number of Latin squares related to any autotopism of Latin squares of order up to 7. [Copyright &y& Elsevier]
- Published
- 2007
- Full Text
- View/download PDF
27. Generating all polynomial invariants in simple loops
- Author
-
Rodríguez-Carbonell, E. and Kapur, D.
- Subjects
- *
INVARIANTS (Mathematics) , *POLYNOMIALS , *ALGORITHMS , *ACERACEAE - Abstract
Abstract: This paper presents a method for automatically generating all polynomial invariants in simple loops. It is first shown that the set of polynomials serving as loop invariants has the algebraic structure of an ideal. Based on this connection, a fixpoint procedure using operations on ideals and Gröbner basis constructions is proposed for finding all polynomial invariants. Most importantly, it is proved that the procedure terminates in at most iterations, where is the number of program variables. The proof relies on showing that the irreducible components of the varieties associated with the ideals generated by the procedure either remain the same or increase their dimension at every iteration of the fixpoint procedure. This yields a correct and complete algorithm for inferring conjunctions of polynomial equalities as invariants. The method has been implemented in Maple using the Groebner package. The implementation has been used to automatically discover non-trivial invariants for several examples to illustrate the power of the technique. [Copyright &y& Elsevier]
- Published
- 2007
- Full Text
- View/download PDF
28. Efficiency improvement in an systems approach to polynomial optimization
- Author
-
Bleylevens, Ivo, Peeters, Ralf, and Hanzon, Bernard
- Subjects
- *
ELECTRONIC data processing , *COMPUTATIONAL complexity , *MACHINE theory , *MATRICES (Mathematics) - Abstract
Abstract: The problem of finding the global minimum of a so-called Minkowski-norm dominated polynomial can be approached by the matrix method of Stetter and Möller, which reformulates it as a large eigenvalue problem. A drawback of this approach is that the matrix involved is usually very large. However, all that is needed for modern iterative eigenproblem solvers is a routine which computes the action of the matrix on a given vector. This paper focuses on improving the efficiency of computing the action of the matrix on a vector. To avoid building the large matrix one can associate the system of first-order conditions with an system of difference equations. One way to compute the action of the matrix efficiently is by setting up a corresponding shortest path problem and solving it. It turns out that for large the shortest path problem has a high computational complexity, and therefore some heuristic procedures are developed for arriving cheaply at suboptimal paths with acceptable performance. [Copyright &y& Elsevier]
- Published
- 2007
- Full Text
- View/download PDF
29. Computation of unirational fields
- Author
-
Gutierrez, Jaime and Sevilla, David
- Subjects
- *
ALGORITHMS , *MATHEMATICS , *MATHEMATICAL programming , *ALGEBRA - Abstract
Abstract: One of the main contributions which Volker Weispfenning made to mathematics is related to Gröbner bases theory. In this paper we present an algorithm for computing all algebraic intermediate subfields in a separably generated unirational field extension (which in particular includes the zero characteristic case). One of the main tools is Gröbner bases theory. Our algorithm also requires computing primitive elements and factoring over algebraic extensions. Moreover, the method can be extended to finitely generated -algebras. [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF
30. Gröbner bases of Hilbert ideals of alternating groups
- Author
-
Wada, Takashi and Ohsugi, Hidefumi
- Subjects
- *
POLYNOMIALS , *HILBERT algebras , *CHARACTERISTIC functions , *FUNCTIONAL analysis - Abstract
Abstract: The Hilbert ideal is an ideal generated by invariant polynomials (of strictly positive degree) of a finite group. In this paper, the reduced Gröbner bases and the universal Gröbner bases of Hilbert ideals of alternating groups are studied. [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF
31. Computing all roots of the likelihood equations of seemingly unrelated regressions
- Author
-
Drton, Mathias
- Subjects
- *
GAUSSIAN distribution , *DISTRIBUTION (Probability theory) , *MATHEMATICAL models , *MULTIVARIATE analysis - Abstract
Abstract: Seemingly unrelated regressions are statistical regression models based on the Gaussian distribution. They are popular in econometrics but also arise in graphical modeling of multivariate dependencies. In maximum likelihood estimation, the parameters of the model are estimated by maximizing the likelihood function, which maps the parameters to the likelihood of observing the given data. By transforming this optimization problem into a polynomial optimization problem, it was recently shown that the likelihood function of a simple bivariate seemingly unrelated regressions model may have several stationary points. Thus local maxima may complicate maximum likelihood estimation. In this paper, we study several more complicated seemingly unrelated regression models, and show how all stationary points of the likelihood function can be computed using algebraic geometry. [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF
32. Gröbner finite path algebras
- Author
-
Leamer, Micah J.
- Subjects
- *
ALGEBRA , *MATHEMATICAL analysis , *MATHEMATICS , *EQUATIONS - Abstract
Abstract: Let be a field and a finite directed multi-graph. The focus of this paper is to offer a complete description of all path algebras and admissible orders with the property that all of their finitely generated ideals have finite Gröbner bases and of those which contain a finitely generated ideal whose Gröbner bases are all infinite. [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF
33. Conquering inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic
- Author
-
Steel, Allan
- Subjects
- *
ALGORITHMS , *ALGEBRA , *MATHEMATICS , *MATHEMATICAL analysis - Abstract
Abstract: Algebraic function fields of positive characteristic are non-perfect fields, and many standard algorithms for solving some fundamental problems in commutative algebra simply do not work over these fields. This paper presents practical algorithms for the first time for (1) computing the primary decomposition of ideals of polynomial rings defined over such fields and (2) factoring arbitrary multivariate polynomials over such fields. Difficulties involving inseparability and the situation where the transcendence degree is greater than one are completely overcome, while the algorithms avoid explicit construction of any extension of the input base field. As a corollary, the problem of computing the primary decomposition of a positive-dimensional ideal over a finite field is also solved. The algorithms perform very effectively in an implementation within the Magma Computer Algebra System, and an analysis of their practical performance is given. [Copyright &y& Elsevier]
- Published
- 2005
- Full Text
- View/download PDF
34. A new class of term orders for elimination
- Author
-
Quoc-Nam Tran
- Subjects
Basis conversion ,Algebra and Number Theory ,Ideal (set theory) ,Basis (linear algebra) ,Algebraic structure ,Elimination ,Computation ,Elimination theory ,System of linear equations ,Term (time) ,Algebra ,Computational Mathematics ,Gröbner basis ,Groebner basis ,Mathematics - Abstract
Elimination is a classical subject. The problem is algorithmically solvable by using resultants or by one calculation of Groebner basis with respect to an elimination term order. However, there is no existing method that is both efficient and reliable enough for applicable size problems, say implicitization of bi-cubic Bezier surfaces with degree six in five variables. This basic and useful operation in computer aided geometric design and geometric modeling defies a solution even when approximation using floating-point or modular coefficients is used for Groebner basis computation.An elimination term order can be used to eliminate U for any ideal in K[X][U]. However, for most practical problems we are given a fixed ideal, which means that an elimination term order may be too much for our calculation.In this paper, the author proposes a new approach for elimination. Instead of using a classical elimination term order for all problems or ideals as usual, the author proposes to use algebraic structures of the given system of equations for finding more suitable term orders for elimination of the given problem only. Experimental results showed that these ideal-specific term orders are much more efficient for elimination. In particular, when ideal specific term orders for elimination are used with Groebner walk conversion, one can completely avoid all perturbations. This is a significant result because researchers have been struggling with how to perturb basis conversions for a long time.
- Full Text
- View/download PDF
35. On Lawrence semigroups
- Author
-
Pilar Pisón-Casares and Alberto Vigneron-Tenorio
- Subjects
Discrete mathematics ,Pure mathematics ,Hilbert's syzygy theorem ,Algebra and Number Theory ,Mathematics::Commutative Algebra ,Semigroup ,Diophantine equation ,Semigroup ideal ,Lattice ideal ,Graver basis ,Gröbner basis ,Simplicial complex ,Computational Mathematics ,Special classes of semigroups ,Lawrence lifting ,Mathematics - Abstract
Lawrence semigroups arise as a tool to compute Graver bases of semigroup ideals. It is known that the minimal free resolution of semigroup ideals is characterized by the reduced homologies of certain simplicial complexes.In this paper we study the minimal degrees of a Lawrence semigroup ideal and its first syzygy given a combinatorial characterization of the nonvanishing cycles in their associated reduced homologies. We specialize the results that appeared in [Briales, E., Campillo, A., Marijuán, C., Pisón, P., 1998. Minimal systems of generators for ideals of semigroups. J. Pure Appl. Algebra, 127, 7–30] and [Pisón-Casares, P., Vigneron-Tenorio, A., 2001. First syzygies of toric varieties and diophantine equations in congruence. Comm. Alg. 29 (4), 1445–1466] to the Lawrence semigroups.
- Full Text
- View/download PDF
36. Gröbner Bases in Orders of Algebraic Number Fields
- Author
-
David Andrew Smith
- Subjects
Discrete mathematics ,Ring (mathematics) ,Reduction (recursion theory) ,Ideal (set theory) ,Algebra and Number Theory ,Mathematics::Commutative Algebra ,Division algorithm ,Algebraic number field ,Gröbner basis ,Computational Mathematics ,Computer Science::Symbolic Computation ,Algebraic number ,Axiom ,Mathematics - Abstract
We prove that any orderOof any algebraic number field K is a reduction ring. Rather than showing the axioms for a reduction ring hold, we start from scratch by well-orderingO, defining a division algorithm, and demonstrating how to use it in a Buchberger algorithm which computes a Gröbner basis given a finite generating set for an ideal. It is shown that our theory of Gröbner bases is equivalent to the ideal membership problem and in fact, a total of eight characterizations are given for a Gröbner basis. Additional conclusions and questions for further investigation are revealed at the end of the paper.
- Full Text
- View/download PDF
37. The Schmidt–Kolchin Conjecture
- Author
-
Georg M. Reinhart
- Subjects
Discrete mathematics ,Computational Mathematics ,Monomial ,Gröbner basis ,Algebra and Number Theory ,Conjecture ,Basis (linear algebra) ,Mathematics::Commutative Algebra ,Algebraic function ,Monomial basis ,Monomial order ,Mathematics ,Vector space - Abstract
In his study of papers by Osgood and Kolchin on rational approximations of algebraic functions, Schmidt observed and proved a theorem which states that the dimension of the vector space of differentially homogeneous differential polynomials is at least 2d. We will show that the dimension is actually equal to 2dand that a basis can be effectively computed. The proof proceeds by developing a term ordering of differential monomials in several variables which ranks monomials relative to a given monomial. This new ordering will be useful in polynomial algorithms in general. The ordering has been implemented in Mathematica.
- Full Text
- View/download PDF
38. An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals, and Applications to Commutative Semigroups
- Author
-
Ulla Koppenhagen and Ernst W. Mayr
- Subjects
Algebra and Number Theory ,Mathematics::Commutative Algebra ,Binomial (polynomial) ,Computation ,Parallel computation thesis ,Space (mathematics) ,Algebra ,Computational Mathematics ,Gröbner basis ,Enumeration ,Commutative property ,Algorithm ,Optimal decision ,Mathematics - Abstract
It is known that the reduced Gröbner basis of general polynomial ideals can be computed in exponential space. The algorithm, obtained by Kühnle and Mayr, is, however, based on rather complex parallel computations, and, above that, makes extensive use of the parallel computation thesis. In this paper, we exhibit an exponential space algorithm for generating the reduced Gröbner basis of binomial ideals which can be implemented without any complex parallel computations. This result is then applied to derive space optimal decision procedures for the finite enumeration and subword problems for commutative semigroups.
- Full Text
- View/download PDF
39. The μ-basis and implicitization of a rational parametric surface
- Author
-
David A. Cox, Falai Chen, and Yang Liu
- Subjects
Surface (mathematics) ,Algebra and Number Theory ,Moving plane ,Syzygy module ,Rational surface ,Base point ,Mathematical analysis ,μ-basis ,Computational Mathematics ,Gröbner basis ,Parametric surface ,Rational point ,Rational motion ,Elliptic rational functions ,Applied mathematics ,Implicitization ,Parametric equation ,Mathematics - Abstract
The concept of a @m-basis was introduced in the case of parametrized curves in 1998 and generalized to the case of rational ruled surfaces in 2001. The @m-basis can be used to recover the parametric equation as well as to derive the implicit equation of a rational curve or surface. Furthermore, it can be used for surface reparametrization and computation of singular points. In this paper, we generalize the notion of a @m-basis to an arbitrary rational parametric surface. We show that: (1) the @m-basis of a rational surface always exists, the geometric significance of which is that any rational surface can be expressed as the intersection of three moving planes without extraneous factors; (2) the @m-basis is in fact a basis of the moving plane module of the rational surface; and (3) the @m-basis is a basis of the corresponding moving surface ideal of the rational surface when the base points are local complete intersections. As a by-product, a new algorithm is presented for computing the implicit equation of a rational surface from the @m-basis. Examples provide evidence that the new algorithm is superior than the traditional algorithm based on direct computation of a Grobner basis. Problems for further research are also discussed. is a basis of the corresponding moving surface ideal of the rational surface when the base points are local complete intersections. As a by-product, a new algorithm is presented for computing the implicit equation of a rational surface from the @m-basis. Examples provide evidence that the new algorithm is superior than the traditional algorithm based on direct computation of a Grobner basis. Problems for further research are also discussed.
- Full Text
- View/download PDF
40. Gröbner bases and the number of Latin squares related to autotopisms of order ≤7
- Author
-
Raúl M. Falcón, Jorge Martín-Morales, and Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
- Subjects
Algebra and Number Theory ,Group (mathematics) ,Algebraic structure ,Mathematics::General Mathematics ,Open problem ,Mathematics::History and Overview ,Latin square ,Order (ring theory) ,Moment (mathematics) ,Combinatorics ,Algebra ,Computational Mathematics ,Multiplication ,Autotopism group ,Orthogonal array ,Gröbner basis ,Mathematics - Abstract
Ejemplar dedicado a: Special issue on Non-commutative Gröbner Bases and Applications Latin squares can be seen as multiplication tables of quasigroups, which are, in general, noncommutativeand non-associative algebraic structures. The number of Latin squares having a fixed isotopismin their autotopism group is at the moment an open problem. In this paper, we use Gröbner bases todescribe an algorithm that allows one to obtain the previous number. Specifically, this algorithm is implemented in SINGULAR to obtain the number of Latin squares related to any autotopism of Latin squares oforder up to 7.
- Full Text
- View/download PDF
41. Solutions of systems of algebraic equations and linear maps on residue class rings
- Author
-
Kazuhiro Yokoyama, Taku Takeshima, and Masayuki Noro
- Subjects
Algebra ,Algebraic equation ,Gröbner basis ,Computational Mathematics ,Algebra and Number Theory ,Computation ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,Algorithm complexity ,Linear algebra ,Fundamental Resolution Equation ,Lexicographical order ,Mathematics - Abstract
In this paper, we present new mathematical results and several new algorithm for solving a system of algebraic equations algebraically. We find that many ideal-theoretical arguments for the problem can be translated into their counterparts in the theory of linear maps. And by this translation, we succeed in giving a new description for the U-resultant and forms of solutions of systems straightforwardly. New algorithms proposed here apply algorithms of linear algebra to avoid repeated computations of Grobner bases under lexicographic order, and they require computation of a Grobner basis, under arbitrary order, only once in principle. The new algorithms improve the efficiency of computation.
- Full Text
- View/download PDF
42. On the Bézout Construction of the Resultant
- Author
-
P. Bikker and A. Yu. Uteshev
- Subjects
Polynomial ,Algebra and Number Theory ,Mathematics::Commutative Algebra ,Elimination theory ,Rational function ,Poisson distribution ,Algebra ,Computational Mathematics ,symbols.namesake ,Gröbner basis ,symbols ,Computer Science::Symbolic Computation ,Point (geometry) ,Mathematics - Abstract
This paper deals with some ideas of Bézout and his successors Poisson, Netto and Laurent for solving polynomial systems. We treat them from the determinantal and from the Gröbner basis point of view. This results in effective algorithms for constructing the multivariate resultant. Other problems of Elimination Theory are discussed: how to find an eliminant for a polynomial system, how to represent its zeroes as the rational functions of the roots of this eliminant and how to separate zeroes.
- Full Text
- View/download PDF
43. Conquering inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic
- Author
-
Allan Steel
- Subjects
Algebraic function field ,Polynomial ,Algebra and Number Theory ,Inseparability ,Primary decomposition ,Factorization of polynomials over finite fields ,Polynomial factorization ,Field (mathematics) ,Algebra ,Computational Mathematics ,Gröbner basis ,Field extension ,Factorization of polynomials ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,Non-perfect field ,Algebraic function ,Mathematics - Abstract
Algebraic function fields of positive characteristic are non-perfect fields, and many standard algorithms for solving some fundamental problems in commutative algebra simply do not work over these fields. This paper presents practical algorithms for the first time for (1) computing the primary decomposition of ideals of polynomial rings defined over such fields and (2) factoring arbitrary multivariate polynomials over such fields. Difficulties involving inseparability and the situation where the transcendence degree is greater than one are completely overcome, while the algorithms avoid explicit construction of any extension of the input base field. As a corollary, the problem of computing the primary decomposition of a positive-dimensional ideal over a finite field is also solved. The algorithms perform very effectively in an implementation within the Magma Computer Algebra System, and an analysis of their practical performance is given.
- Full Text
- View/download PDF
44. On Factorizing the Symbolic U-resultant — Application of the ddet operator
- Author
-
Tetsuro Fujise, Horokazu Murao, and Hidetsune Kobayashi
- Subjects
Algebra ,Computational Mathematics ,Algebraic equation ,Matrix (mathematics) ,Gröbner basis ,Polynomial ,Algebra and Number Theory ,Operator (computer programming) ,Simple (abstract algebra) ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,Algebraic number ,Symbolic computation ,Mathematics - Abstract
This paper presents a new, practical, efficient algorithm for factorizing the U -resultant of a system of algebraic equations with finitely many solutions. Given a matrix whose determinant is the U -resultant, our algorithm obtains the true linear factors with exact multiplicities, directly from the matrix without expanding the multivariate determinant. The main focuses are laid upon the use of a new operator, which enables us to treat only matrices of univariate polynomial elements, and also upon the exact treatment of multiplicities, which is made possible by the symbolic representation of solutions in simple algebraic extensions of Q . The algorithm is probabilistic in the sense that there exists no deterministic method to give an appropriate parameterization. The efficiency of our algorithm will be demonstrated with some empirical problems.
- Full Text
- View/download PDF
45. On Lucky Primes
- Author
-
Hans-Gert Gräbe
- Subjects
Noetherian ,Pure mathematics ,Algebra and Number Theory ,Hilbert's syzygy theorem ,Mathematics::Commutative Algebra ,Linear system ,Lift (mathematics) ,Computational Mathematics ,Gröbner basis ,Homogeneous polynomial ,Linear algebra ,Computer Science::Symbolic Computation ,Commutative property ,Mathematics - Abstract
Winkler (1988) and Pauer (1992) present algorithms for a Hensel lifting of a modular Grobner basis over lucky primes to a rational one. They have to solve a linear system with modular polynomial entries that requires another (modular) Grobner basis computation. After an extension of luckiness to arbitrary (commutative noetherian) base rings we show in this paper that for a homogeneous polynomial ideal I one can lift not only its Grobner basis but also a homogeneous basis of its syzygy module. The same result holds for arbitrary ideals and liftings from Z / p to Q . Moreover the same lifting can be obtained from a true Grobner trace by linear algebra over Q only. Parallel modular techniques allow to find such a true Grobner trace and a lucky prime with high probability. All these results generalize in an obvious way to homogeneous modules generated by the rows of matrices with polynomial entries. Since luckiness can be weakened to a condition that transfers from I to higher syzygy modules the lifting theorem generalizes to a lifting theorem for the resolution of I .
- Full Text
- View/download PDF
46. Polynomial-Time Computation of the Dimension of Algebraic Varieties in Zero-Characteristic
- Author
-
Alexander Chistov
- Subjects
Discrete mathematics ,Gröbner basis ,Computational Mathematics ,Algebra and Number Theory ,Homogeneous polynomial ,Algebraic surface ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,Polarization of an algebraic form ,Dimension of an algebraic variety ,Algebraic variety ,Algebraic curve ,Projective variety ,Mathematics - Abstract
In this paper an algorithm is described for the computation of the dimension of a projective algebraic variety over a zero characteristic ground field. The variety is given as a set of zeros of a family of homogeneous polynomials of the degree less than d in n +1 variables. The working time of the algorithm is polynomial in the size of input and d n .
- Full Text
- View/download PDF
47. Analogs of Gröbner Bases in Polynomial Rings over a Ring
- Author
-
J. Lyn Miller
- Subjects
Discrete mathematics ,Noetherian ,Pure mathematics ,Hilbert's syzygy theorem ,Algebra and Number Theory ,Mathematics::Commutative Algebra ,Polynomial ring ,Mathematics::Rings and Algebras ,Multiplicative function ,Subalgebra ,Integral domain ,Gröbner basis ,Computational Mathematics ,Computer Science::Symbolic Computation ,Mathematics - Abstract
In this paper we will define analogs of Grobner bases for R -subalgebras and their ideals in a polynomial ring R [ x 1 ,..., x n ] where R is a noetherian integral domain with multiplicative identity and in which we can determine ideal membership and compute syzygies.The main goal is to present and verify algorithms for constructing these Grobner basis counterparts.As an application, we will produce a method for computing generators for the first syzygy module of a subset of an R [ x 1 ,..., x n ] where each coordinate of each syzygy must be an element of the subalgebra.
- Full Text
- View/download PDF
48. Are Buchberger’s criteria necessary for the chain condition?
- Author
-
Hoon Hong and John Perry
- Subjects
Algebra and Number Theory ,Carry (arithmetic) ,010102 general mathematics ,010103 numerical & computational mathematics ,Extension (predicate logic) ,Symbolic computation ,01 natural sciences ,Buchberger criteria ,Algebra ,Computational Mathematics ,Gröbner basis ,Chain (algebraic topology) ,S-polynomials ,Buchberger's algorithm ,Gröbner bases ,0101 mathematics ,Mathematics - Abstract
Buchberger’s Gröbner basis theory plays a fundamental role in symbolic computation. The resulting algorithms essentially carry out several S-polynomial reductions. In his Ph.D. thesis and later publication Buchberger showed that sometimes one can skip S-polynomial reductions if the leading terms of polynomials satisfy certain criteria. A question naturally arises: Are Buchberger’s criteria also necessary for skipping S-polynomial reductions? In this paper, after making the question more precise (in terms of a chain condition), we show the answer to be “almost, but not quite”: necessary when there are four or more polynomials, but not necessary when there are exactly three polynomials. For that case, we found an extension to Buchberger’s criteria that is necessary as well as sufficient.
- Full Text
- View/download PDF
49. Some results on Gröbner bases over commutative rings
- Author
-
Ann K. Boyle and William W. Adams
- Subjects
Computational Mathematics ,Single variable ,Gröbner basis ,Pure mathematics ,Algebra and Number Theory ,Coprime integers ,Commutative ring ,Finite set ,Mathematics - Abstract
Let F be a finite set of polynomials in A [ x ], where A is a commutative ring and x is a single variable. This paper is concerned with what properties are imposed on the coefficients of these polynomials if F is assumed to be a Grobner basis. When A = R [ y ] for some commutative ring R , we characterize Grobner bases in R [ y, x ] in terms of Grobner bases in R [ y ][ x ] and Grobner bases in R [ y ]. We then address the question of lifting Grobner bases from A to A[ x ] by examining the relationship between Szekeres bases and Grobner bases. Finally we show that if A is a UFD, then, if the elements of F form a Grobner basis and are relatively prime, the same is true of the leading coefficients of the polynomials in F .
- Full Text
- View/download PDF
50. Improving the DISPGB algorithm using the discriminant ideal
- Author
-
Antonio Montes and Montserrat Manubens
- Subjects
Polynomial ,Ideal (set theory) ,13F10 ,Algebra and Number Theory ,Basis (linear algebra) ,Discriminant ideal ,Parametric polynomial system ,68W30 ,Mathematics - Commutative Algebra ,Commutative Algebra (math.AC) ,Constructive ,Comprehensive Gröbner bases ,13P10 ,Algebra ,Gröbner basis ,Computational Mathematics ,Discriminant ,FOS: Mathematics ,Rewriting ,Algorithm ,Mathematics ,Parametric statistics - Abstract
In 1992, V. Weispfenning proved the existence of Comprehensive Groebner Bases (CGB) and gave an algorithm to compute one. That algorithm was not very efficient and not canonical. Using his suggestions, A. Montes obtained in 2002 a more efficient algorithm (DISPGB) for Discussing Parametric Groebner Bases. Inspired in its philosophy, V. Weispfenning defined, in 2002, how to obtain a Canonical Comprehensive Groebner Basis (CCGB) for parametric polynomial ideals, and provided a constructive method. In this paper we use Weispfenning's CCGB ideas to make substantial improvements on Montes DISPGB algorithm. It now includes rewriting of the discussion tree using the Discriminant Ideal and provides a compact and effective discussion. We also describe the new algorithms in the DPGB library containing the improved DISPGB as well as new routines to check whether a given basis is a CGB or not, and to obtain a CGB. Examples and tests are also provided., Comment: 21 pages, see also http://www-ma2.upc.edu/~montes/
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.