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

Complexity results for triangular sets

JOURNAL OF SYMBOLIC COMPUTATION 2003年第3-4期36卷 555-594页

作者： Schost, É Ecole Polytech Lab GAGE F-91128 Palaiseau France

We study the representation of the solutions of a polynomial system by triangular sets, and concentrate on the positive-dimensional case. We reduce to dimension zero by placing the free variables in the base field, so the solutions can be represented by triangular sets with coefficients in a rational function field. We give intrinsic-type bounds on the degree of the coefficients in such a triangular set, and on the degree of an associated degeneracy hypersurface. Then we show how to apply lifting techniques in this context, and point out the role played by the evaluation properties of the input system. Our algorithms are implemented in Magma;we present three applications, relevant to geometry and number theory. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： triangular sets complexity symbolic Newton operator

来源：评论

学校读者我要写书评

暂无评论

Homotopy techniques for multiplication modulo triangular sets

引用

JOURNAL OF SYMBOLIC COMPUTATION 2011年第12期46卷 1378-1402页

作者： Bostan, Alin Chowdhury, Muhammad F. I. van der Hoeven, Joris Schost, Eric INRIA Rocquencourt Algorithms Project F-78153 Le Chesnay France Univ Western Ontario Dept Comp Sci London ON Canada Univ Paris 11 CNRS Dept Math F-91405 Orsay France

We study the cost of multiplication modulo triangular families of polynomials. Following previous work by Li et al. (2007), we propose an algorithm that relies on homotopy and fast evaluation-interpolation techniques. We obtain a quasi-linear time complexity for substantial families of examples, for which no such result was known before. Applications are given notably to additions of algebraic numbers in small characteristic. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： triangular sets Multiplication Complexity

来源：评论

学校读者我要写书评

暂无评论

On the complexity of computing with zero-dimensional triangular sets

引用

JOURNAL OF SYMBOLIC COMPUTATION 2013年 50卷 110-138页

作者： Poteaux, Adrien Schost, Eric UMR Lille1 CNRS 8022 LIFL Lille France Univ Western Ontario Dept Comp Sci London ON Canada

We study the complexity of some fundamental operations for triangular sets in dimension zero. Using Las Vegas algorithms, we prove that one can perform such operations as change of order, equiprojectable decomposition, or quasi-inverse computation with a cost that is essentially that of modular composition. Over an abstract field, this leads to a subquadratic cost (with respect to the degree of the underlying algebraic set). Over a finite field, in a boolean RAM model, we obtain a quasi-linear running time using Kedlaya and Umans' algorithm for modular composition. Conversely, we also show how to reduce the problem of modular composition to change of order for triangular sets, so that all these problems are essentially equivalent. Our algorithms are implemented in Maple;we present some experimental results. (C) 2012 Published by Elsevier B.V.

关键词： triangular sets Modular composition Power projection Change of order Equiprojectable decomposition

来源：评论

学校读者我要写书评

暂无评论

Some properties of triangular sets and improvement upon algorithm CharSer

引用

8th International Conference on Artificial Intelligence and Symbolic Computation

作者： Li, Yong-Bin Chinese Acad Sci Chengdu Inst Comp Applicat Chengdu 610041 Sichuan Peoples R China Univ Elect Sci & Technol China Sch Appl Math Chengdu 610054 Sichuan Peoples R China

ISBN: (纸本)3540397280

We present some new properties of triangular sets, which have rather theoretical contribution to understand the structure of the affine varieties of triangular sets. Based on these results and the famous aigorithm CharSet, we present two modified versions of the algorithm CharSer that can decompose any nonempty polynomial set into characteristic series. Some examples show that our improvement can efficiently avoid for redundant decompositions, and reduce the branches of the decomposition tree at times.

关键词： triangular sets quasi-normal zero characteristic set algorithm CharSer

来源：评论

学校读者我要写书评

暂无评论

Resolving Zero-Divisors of Radical triangular sets using Hensel Lifting and Applications

Resolving Zero-Divisors of Radical Triangular Sets using Hen...

引用

作者： John Kluesner Simon Fraser University

学位级别：硕士

This thesis aims to create efficient algorithms for computing in the ring R = Q[z 1,..., z n ]/T where T is a zero-dimensional triangular set. The presence of zero-divisors in R makes it a computational challenge to use modular algorithms. In particular, there has never been a proper modular algorithm for computing greatest common divisors of polynomials in R[x]. We present two new ways of resolving zero-divisors: Hensel lifting and fault tolerant rational reconstruction, which allows us to create a new modular gcd algorithm for R[x] as well as a new inversion algorithm for R. We have implemented our algorithms in Maple using the recden library, and we show that they outperform the methods currently implemented in Maple's RegularChains package. The method of Hensel lifting for resolving zero-divisors should give rise to other new modular algorithms for computing modulo triangular sets and our applications show that this approach is fruitful.

关键词： Computer Algebra Modular Algorithms triangular sets Radical Ideals Inversion Greatest Common Divisors Maple

来源：评论

学校读者我要写书评

暂无评论

A moment approach to analyze zeros of triangular polynomial sets

引用

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY 2006年第4期358卷 1403-1420页

作者： Lasserre, JB CNRS LAAS F-31077 Toulouse France LAAS Inst Math F-31077 Toulouse France

Let I = be a zero-dimensional ideal of R[x(1),..., x(n)] such that its associated set G of polynomial equations g(i)(x) = 0 for all i = 1,..., n is in triangular form. By introducing multivariate Newton sums we provi... 详细信息

Let I = < g(1),..., gn > be a zero-dimensional ideal of R[x(1),..., x(n)] such that its associated set G of polynomial equations g(i)(x) = 0 for all i = 1,..., n is in triangular form. By introducing multivariate Newton sums we provide a numerical characterization of polynomials in root I. We also provide a necessary and sufficient ( numerical) condition for all the zeros of G to be in a given set K subset of C-n, without explicitly computing the zeros. In addition, we also provide a necessary and sufficient condition on the coefficients of the g(i)'s for G to have (a) only real zeros, (b) to have only real zeros, all contained in a given semi-algebraic set K subset of R-n. In the proof technique, we use a deep result of Curto and Fialkow ( 2000) on the K-moment problem, and the conditions we provide are given in terms of positive definiteness of some related moment and localizing matrices depending on the g(i)'s via the Newton sums of G. In addition, the number of distinct real zeros is shown to be the maximal rank of a related moment matrix.

关键词： system of polynomial equations triangular sets moment problem

来源：评论

学校读者我要写书评

暂无评论

Chordal Networks of Polynomial Ideals

引用

SIAM JOURNAL ON APPLIED ALGEBRA AND GEOMETRY 2017年第1期1卷 73-110页

作者： Cifuentes, Diego Parrilo, Pablo A. MIT LIDS 77 Massachusetts Ave Cambridge MA 02139 USA

We introduce a novel representation of structured polynomial ideals, which we refer to as chordal networks. The sparsity structure of a polynomial system is often described by a graph that captures the interactions among the variables. Chordal networks provide a computationally convenient decomposition into simpler (triangular) polynomial sets, while preserving the underlying graphical structure. We show that many interesting families of polynomial ideals admit compact chordal network representations (of size linear in the number of variables), even though the number of components is exponentially large. Chordal networks can be computed for arbitrary polynomial systems using a refinement of the chordal elimination algorithm from [D. Cifuentes and P.A. Parrilo, SIAM J. Discrete Math., 30 (2016), pp. 1534-1570]. Furthermore, they can be effectively used to obtain several properties of the variety, such as its dimension, cardinality, and equidimensional components, as well as an efficient probabilistic test for radical ideal membership. We apply our methods to examples from algebraic statistics and vector addition systems;for these instances, algorithms based on chordal networks outperform existing techniques by orders of magnitude.

关键词： chordal graphs structured polynomials chordal networks triangular sets

来源：评论

学校读者我要写书评

暂无评论

Resolving zero divisors using Hensel lifting 19

Resolving zero divisors using Hensel lifting

引用

19th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)

作者： Kluesner, John Monagan, Michael Simon Fraser Univ Dept Math Burnaby BC Canada

ISBN: (纸本)9781538626269

Algorithms which compute modulo triangular sets must respect zero divisors. We present Hensel lifting as a tool for resolving them. We give an application: a modular algorithm for computing gcds of univariate polynomials with coefficients modulo a radical triangular set over the rational numbers. We have implemented our algorithm using Maple's RECDEN package. We compare our implementation with the procedure RegularGcd in the RegularChains package.

关键词： Modular algorithms triangular sets Radical ideals Hensel lifting GCD

来源：评论

学校读者我要写书评

暂无评论

Using computer algebra tools to classify serial manipulators 4th

引用

4th International Workshop on Automated Deduction in Geometry

作者： Corvez, S Rouillier, F Univ Rennes 1 IRMAR F-35042 Rennes France INRIA LORIA Nancy France

ISBN: (纸本)3540209271

In this paper we present a classification of 3-revolute-jointed manipulators based on the cuspidal behaviour. It., was shown in a previous work (16) that this ability to change posture without meeting a singularity is equivalent to the existence of a point in the workspace, such that a polynomial of degree, four depending on the parameters of the manipulator and on the cartesian coordinates of the, effector has a triple. root. More precisely, from a partition of the parameters'space, such that in any connected component of this partition the number of triple roots is constant, we need to compute one sample point by cell, in order to have a full description, in terms of cuspidality, of the different possible configurations. This kind of work can be divided into two parts. First of all, thanks to Groebner Bases computations, the goal is to obtain an algebraic set in the parameters'space describing the cuspidality behavior and then to compute a CAD adapted to this set. In order to simplify the problem, we use strongly the fact that a manipulator cannot be constructed with exact parameters, in other words, we are just interested in the generic solutions of our problem. This consideration leads us to work with triangular sets rather than with the global Groebner Bases and to adapt the CAD of Collins as we will just take care of the cells of maximal dimension.

关键词： Groebner basis cylindrical algebraic decomposition triangular sets serial manipulators semialgebraic sets

来源：评论

学校读者我要写书评

暂无评论

A new bound on Hrushovski's algorithm for computing the Galois group of a linear differential equation

引用

COMMUNICATIONS IN ALGEBRA 2019年第9期47卷 3553-3566页

作者： Sun, Mengxiao CUNY Grad Sch & Univ Ctr New York NY 10016 USA

The complexity of computing the Galois group of a linear differential equation is of general interest. In a recent work, Feng gave the first degree bound on Hrushovski's algorithm for computing the Galois group of a linear differential equation. This bound is the degree bound of the polynomials used in the first step of the algorithm for finding a proto-Galois group (see Definition 2.7) and is sextuply exponential in the order of the differential equation. In this paper, we use Szanto's algorithm of triangular representation for algebraic sets to analyze the complexity of computing the Galois group of a linear differential equation and we give a new bound which is triple exponential in the order of the given differential equation.

关键词： Algorithms differential Galois groups linear differential equations triangular sets

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：