ترغب بنشر مسار تعليمي؟ اضغط هنا

A New Algorithmic Scheme for Computing Characteristic Sets

227   0   0.0 ( 0 )
 نشر من قبل Meng Jin
 تاريخ النشر 2011
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

Ritt-Wus algorithm of characteristic sets is the most representative for triangularizing sets of multivariate polynomials. Pseudo-division is the main operation used in this algorithm. In this paper we present a new algorithmic scheme for computing generalized characteristic sets by introducing other admissible reductions than pseudo-division. A concrete subalgorithm is designed to triangularize polynomial sets using selected admissible reductions and several effective elimination strategies and to replace the algorithm of basic sets (used in Ritt-Wus algorithm). The proposed algorithm has been implemented and experimental results show that it performs better than Ritt-Wus algorithm in terms of computing time and simplicity of output for a number of non-trivial test examples.



قيم البحث

اقرأ أيضاً

113 - Paolo Lella 2012
Borel-fixed ideals play a key role in the study of Hilbert schemes. Indeed each component and each intersection of components of a Hilbert scheme contains at least one Borel-fixed point, i.e. a point corresponding to a subscheme defined by a Borel-fi xed ideal. Moreover Borel-fixed ideals have good combinatorial properties, which make them very interesting in an algorithmic perspective. In this paper, we propose an implementation of the algorithm computing all the saturated Borel-fixed ideals with number of variables and Hilbert polynomial assigned, introduced from a theoretical point of view in the paper Segment ideals and Hilbert schemes of points, Discrete Mathematics 311 (2011).
162 - Pierre Lairez 2019
Let $Ssubset R^n$ be a compact basic semi-algebraic set defined as the real solution set of multivariate polynomial inequalities with rational coefficients. We design an algorithm which takes as input a polynomial system defining $S$ and an integer $ pgeq 0$ and returns the $n$-dimensional volume of $S$ at absolute precision $2^{-p}$.Our algorithm relies on the relationship between volumes of semi-algebraic sets and periods of rational integrals. It makes use of algorithms computing the Picard-Fuchs differential equation of appropriate periods, properties of critical points, and high-precision numerical integration of differential equations.The algorithm runs in essentially linear time with respect to~$p$. This improves upon the previous exponential bounds obtained by Monte-Carlo or moment-based methods. Assuming a conjecture of Dimca, the arithmetic cost of the algebraic subroutines for computing Picard-Fuchs equations and critical points is singly exponential in $n$ and polynomial in the maximum degree of the input.
72 - Raphael Pag`es 2021
We design a fast algorithm that computes, for a given linear differential operator with coefficients in $Z[x ]$, all the characteristic polynomials of its p-curvatures, for all primes $p < N$ , in asymptotically quasi-linear bit complexity in N. We d iscuss implementations and applications of our algorithm. We shall see in particular that the good performances of our algorithm are quickly visible.
100 - Monique Laurent 2008
In this note we prove a generalization of the flat extension theorem of Curto and Fialkow for truncated moment matrices. It applies to moment matrices indexed by an arbitrary set of monomials and its border, assuming that this set is connected to 1. When formulated in a basis-free setting, this gives an equivalent result for truncated Hankel operators.
Let $f_1,...,f_s in mathbb{K}[x_1,...,x_m]$ be a system of polynomials generating a zero-dimensional ideal $I$, where $mathbb{K}$ is an arbitrary algebraically closed field. We study the computation of matrices of traces for the factor algebra $A := CC[x_1, ..., x_m]/ I$, i.e. matrices with entries which are trace functions of the roots of $I$. Such matrices of traces in turn allow us to compute a system of multiplication matrices ${M_{x_i}|i=1,...,m}$ of the radical $sqrt{I}$. We first propose a method using Macaulay type resultant matrices of $f_1,...,f_s$ and a polynomial $J$ to compute moment matrices, and in particular matrices of traces for $A$. Here $J$ is a polynomial generalizing the Jacobian. We prove bounds on the degrees needed for the Macaulay matrix in the case when $I$ has finitely many projective roots in $mathbb{P}^m_CC$. We also extend previous results which work only for the case where $A$ is Gorenstein to the non-Gorenstein case. The second proposed method uses Bezoutian matrices to compute matrices of traces of $A$. Here we need the assumption that $s=m$ and $f_1,...,f_m$ define an affine complete intersection. This second method also works if we have higher dimensional components at infinity. A new explicit description of the generators of $sqrt{I}$ are given in terms of Bezoutians.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا