检索结果-内蒙古大学图书馆

JOURNAL OF SYMBOLIC COMPUTATION 2017年 82卷 38-56页

作者： Darmian, Mahdi Dehghani Hashemi, Amir Univ Tehran Sch Math Stat & Comp Sci Coll Sci Tehran 141556455 Iran Isfahan Univ Technol Dept Math Sci Esfahan *** Iran Inst Res Fundamental Sci IPM Sch Math Tehran 193955746 Iran

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.

关键词： Grobner bases fglm algorithm Comprehensive Grobner system Parametric fglm algorithm Parametric linear algebra Comprehensive Grobner system conversion

来源：评论

学校读者我要写书评

暂无评论

On fglm algorithms with Tropical Grobner bases 20

On FGLM Algorithms with Tropical Grobner bases

引用

45th International Symposium on Symbolic and Algebraic Computation

作者： Ishihara, Yuki Vaccon, Tristan Yokoyama, Kazuhiro Rikkyo Univ Grad Sch Sci Tokyo Japan Univ Limoges Limoges France CNRS XLIM UMR 7252 Limoges France Rikkyo Univ Dept Math Tokyo Japan

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.

关键词： algorithms Tropical Geometry Grobner bases fglm algorithm p-adic precision

来源：评论

学校读者我要写书评

暂无评论

Efficient Forney functions for decoding AG codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 1999年第1期45卷 260-265页

作者： Leonard, DA Auburn Univ Dept Discrete & Stat Sci Auburn AL 36849 USA

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.

关键词： algebraic-geometric (AG) codes fglm algorithm Forney formula Grobner bases

来源：评论

学校读者我要写书评

暂无评论

Fast algorithm for Change of Ordering of Zero-dimensional Grobner Bases with Sparse Multiplication Matrices 11

Fast Algorithm for Change of Ordering of Zero-dimensional Gr...

引用

36th International Symposium on Symbolic and Algebraic Computation

作者： Faugere, Jean-Charles Mou, Chenqi Univ Paris 06 INRIA Paris Rocquencourt SALSA Project CNRSUMR 7606LIP 6 F-75005 Paris France

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 algorithm fglm, 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.

关键词： Grobner bases Change of ordering Zero-dimensional ideals Sparse matrix fglm algorithm Wiedemann algorithm BMS algorithm

来源：评论

学校读者我要写书评

暂无评论

On the Complexity of Linear Algebra Operations over Algebraic Extension Fields 1

引用

25th International Workshop on Computer Algebra in Scientific Computing (CASC)

作者： Hashemi, Amir Lichtblau, Daniel Isfahan Univ Technol Dept Math Sci Esfahan *** Iran Inst Res Fundamental Sci IPM Sch Math Tehran 193955746 Iran Wolfram Res 100 Trade Ctr Dr Champaign IL 61820 USA

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.

关键词： Gaussian elimination Minimal polynomial Polynomial ideals Grobner bases fglm algorithm Algebraic extension fields Complexity analysis

来源：评论

学校读者我要写书评

暂无评论

Guessing Linear Recurrence Relations of Sequence Tuples and P-recursive Sequences with Linear Algebra 16

Guessing Linear Recurrence Relations of Sequence Tuples and ...

引用

41st ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Berthomieu, Jeremy Faugere, Jean-Charles Univ Paris 06 Sorbonne Univ Lab Informat Paris 6 CNRSINRIAEquipe PolSys 4 Pl Jussieu F-75252 Paris 05 France

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.

关键词： Grobner bases P-recursive sequences fglm algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：