اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدImproved Polynomial Remainder Sequences for Ore Polynomials
93
0
0.0
(
0
)
نشر من قبل
Maximilian Jaroschek
تاريخ النشر
2015
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
تأليف
Maximilian Jaroschek
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Polynomial remainder sequences contain the intermediate results of the Euclidean algorithm when applied to (non-)commutative polynomials. The running time of the algorithm is dependent on the size of the coefficients of the remainders. Different ways have been studied to make these as small as possible. The subresultant sequence of two polynomials is a polynomial remainder sequence in which the size of the coefficients is optimal in the generic case, but when taking the input from applications, the coefficients are often larger than necessary. We generalize two improvements of the subresultant sequence to Ore polynomials and derive a new bound for the minimal coefficient size. Our approach also yields a new proof for the results in the commutative case, providing a new point of view on the origin of the extraneous factors of the coefficients.
قيم البحث
اقرأ أيضاً
We present a Sage implementation of Ore algebras. The main features for the most common instances include basic arithmetic and actions; gcrd and lclm; D-finite closure properties; natural transformations between related algebras; guessing; desingular
ization; solvers for polynomials, rational functions and (generalized) power series. This paper is a tutorial on how to use the package.
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.
Desingularization is the problem of finding a left multiple of a given Ore operator in which some factor of the leading coefficient of the original operator is removed. An order-degree curve for a given Ore operator is a curve in the $(r,d)$-plane su
ch that for all points $(r,d)$ above this curve, there exists a left multiple of order $r$ and degree $d$ of the given operator. We give a new proof of a desingularization result by Abramov and van Hoeij for the shift case, and show how desingularization implies order-degree curves which are extremely accurate in examples.
This paper describes and analyzes a method for computing border bases of a zero-dimensional ideal $I$. The criterion used in the computation involves specific commutation polynomials and leads to an algorithm and an implementation extending the one p
rovided in [MT05]. This general border basis algorithm weakens the monomial ordering requirement for grob bases computations. It is up to date the most general setting for representing quotient algebras, embedding into a single formalism Grobner bases, Macaulay bases and new representation that do not fit into the previous categories. With this formalism we show how the syzygies of the border basis are generated by commutation relations. We also show that our construction of normal form is stable under small perturbations of the ideal, if the number of solutions remains constant. This new feature for a symbolic algorithm has a huge impact on the practical efficiency as it is illustrated by the experiments on classical benchmark polynomial systems, at the end of the paper.
The polynomial multiplication problem has attracted considerable attention since the early days of computer algebra, and several algorithms have been designed to achieve the best possible time complexity. More recently, efforts have been made to improve the space complexity, developing modifi
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
