In this paper, we consider the non-trivial problem of converting a zero-dimensional parametric Grobner basis w.r.t. a given monomial ordering to a Grobner basis w.r.t. any other monomial ordering. We present a new alg...
详细信息
In this paper, we consider the non-trivial problem of converting a zero-dimensional parametric Grobner basis w.r.t. a given monomial ordering to a Grobner basis w.r.t. any other monomial ordering. We present a new algorithm, so-called parametric fglm algorithm, that takes as input a monomial ordering and a finite parametric set which is a Grobner basis w.r.t a given set of parametric constraints, and outputs a decomposition of the given space of parameters as a finite set of (parametric) cells and for each cell a finite set of parametric polynomials which is a Grobner basis w.r.t. the target monomial ordering and the corresponding cell. For this purpose, we develop computationally efficient algorithms to deal with parametric linear systems that are applicable in computing comprehensive Grobner systems of parametric linear ideals also in the theory of parametric linear algebra to compute Gaussian elimination and minimal polynomial of a parametric matrix. All proposed algorithms have been implemented in MAPLE and their efficiency is discussed on a diverse set of benchmark polynomials. (C) 2017 Elsevier Ltd. All rights reserved.
Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Grobner bases taking into account the valuation of K. Because of the use of the valuation, the theory of tropical G...
详细信息
ISBN:
(纸本)9781450371001
Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Grobner bases taking into account the valuation of K. Because of the use of the valuation, the theory of tropical Grobner bases has proved to provide settings for computations over polynomial rings over a p-adic field that are more stable than that of classical Grobner bases. In this article, we investigate how the fglm change of ordering algorithm can be adapted to the tropical setting. As the valuations of the polynomial coefficients are taken into account, the classical fglm algorithm's incremental way, monomomial by monomial, to compute the multiplication matrices and the change of basis matrix can not be transposed at all to the tropical setting. We mitigate this issue by developing new linear algebra algorithms and apply them to our new tropical fglm algorithms. Motivations are twofold. Firstly, to compute tropical varieties, one usually goes through the computation of many tropical Grobner bases defined for varying weights (and then varying term orders). For an ideal of dimension 0, the tropical fglm algorithm provides an efficient way to go from a tropical Grobner basis from one weight to one for another weight. Secondly, the fglm strategy can be applied to go from a tropical Grobner basis to a classical Grobner basis. We provide tools to chain the stable computation of a tropical Grobner basis (for weight [0,..., 0]) with the p-adic stabilized variants of fglm of [RV16] to compute a lexicographical or shape position basis. All our algorithms have been implemented into SageMath. We provide numerical examples to illustrate time-complexity. We then illustrate the superiority of our strategy regarding to the stability of p-adic numerical computations.
In this paper, we study the complexity of performing some linear algebra operations such as Gaussian elimination and minimal polynomial computation over an algebraic extension field. For this, we use the theory of Gro...
详细信息
ISBN:
(数字)9783031417245
ISBN:
(纸本)9783031417238;9783031417245
In this paper, we study the complexity of performing some linear algebra operations such as Gaussian elimination and minimal polynomial computation over an algebraic extension field. For this, we use the theory of Grobner bases to employ linear algebra methods as well as to work in an algebraic extension. We show that this has good complexity. Finally, we report an implementation of our algorithms in WOLFRAM MATHEMATICA and illustrate its effectiveness via several examples.
Given several n-dimensional sequences, we first present an algorithm for computing the Grobner basis of their module of linear recurrence relations. A P-recursive sequence (u(i))i is an element of N-n, satisfies linea...
详细信息
ISBN:
(纸本)9781450343800
Given several n-dimensional sequences, we first present an algorithm for computing the Grobner basis of their module of linear recurrence relations. A P-recursive sequence (u(i))i is an element of N-n, satisfies linear recurrence relations with polynomial coefficients in i, as defined by Stanley in 1980. Calling directly the aforementioned algorithm on the tuple of sequences ((ij u(i))i is an element of N-n)(j) for retrieving the relations yields redundant relations. Since the module of relations of a P-recursive sequence also has an extra structure of a O-dimensional right ideal of an Ore algebra, we design a more efficient algorithm that takes advantage of this extra structure for computing the relations. Finally, we show how to incorporate Grobner bases computations in an Ore algebra K (ti,, t, xi,,x), with commutators x(k) x(l) - x(e) x(l) = t(k) t(l) t(e) - t(k) = t(k) x(e) - x(e) t(k) = 0 for k and t(k) x(k) - x(k) t(k) = x(k), into the algorithm designed for P-recursive sequences. This allows us to compute faster the Grobner basis of the ideal spanned by the first relations, such as in 2D/3D-space walks examples.
Let I subset of K[x(1), ... , x(n)] be a 0-dimensional ideal of degree D where K is a field. It is well-known that obtaining efficient algorithms for change of ordering of Grobner bases of I is crucial in polynomial s...
详细信息
ISBN:
(纸本)9781450306751
Let I subset of K[x(1), ... , x(n)] be a 0-dimensional ideal of degree D where K is a field. It is well-known that obtaining efficient algorithms for change of ordering of Grobner bases of I is crucial in polynomial system solving. Through the algorithmfglm, this task is classically tackled by linear algebra operations in K[x(1), ... , x(n)]/I. With recent progress on Grobner bases computations, this step turns out to be the bottleneck of the whole solving process. Our contribution is an algorithm that takes advantage of the sparsity structure of multiplication matrices appearing during the change of ordering. This sparsity structure arises even when the input polynomial system defining I is dense. As a by-product, we obtain an implementation which is able to manipulate 0-dimensional ideals over a prime field of degree greater than 30000. It outperforms the Magma/Singular/FGb implementations of fglm. First, we investigate the particular but important shape position case. The obtained algorithm performs the change of ordering within a complexity O(D(N-1 + n log(D))), where N-1 is the number of nonzero entries of a multiplication matrix. This almost matches the complexity of computing the minimal polynomial of one multiplication matrix. Then, we address the general case and give corresponding complexity results. Our algorithm is dynamic in the sense that it selects automatically which strategy to use depending on the input. Its key ingredients are the Wiedemann algorithm to handle 1-dimensional linear recurrence (for the shape position case), and the Berlekamp-Massey-Sakata algorithm from Coding Theory to handle multi-dimensional linearly recurring sequences in the general case.
Using a Forney formula to solve for the error magnitudes in decoding AG codes requires producing functions sigma(P), which are 0 at all but one point P of the variety of the error-locator ideal. The best such function...
详细信息
Using a Forney formula to solve for the error magnitudes in decoding AG codes requires producing functions sigma(P), which are 0 at all but one point P of the variety of the error-locator ideal. The best such function is produced here in a reasonably efficient way from a lex Grobner basis. This lex basis is, in turn, produced efficiently from a weighted, grevlex basis by using the fglm algorithm. These two steps essentially complete the efficient decoding scheme based on a Forney formula started in the author's previous work.
暂无评论