Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImproved Polynomial Remainder Sequences for Ore Polynomials
93
0
0.0
(
0
)
Added by
Maximilian Jaroschek
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Authors
Maximilian Jaroschek
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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; desingularization; 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 discuss 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 such 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 provided 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
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
