Algorithms for Regular Chains of Dimension One
Abstract
One of the core commands in the RegularChains library inside Maple is Triangularize. The underlying decomposes the solution set of a polynomial system into geometrically meaningful components represented by regular chains. This algorithm works by repeatedly calling a procedure, called Intersect, which computes the common zeros of a polynomial p and a regular chain T .
As the number of variables of p and T , as well as their degrees, increase, the call to the function Intersect(p, T ) becomes more and more computationally expensive. It was observed in that when the input polynomial system is zero-dimensional and T is one-dimensional then this cost can be substantially reduced. The method proposed by the authors is a probabilistic algorithm based on evaluation and interpolation techniques. This is the type of method which is typically challenging to implement in a high-level language like Maple’s language, as a sharp control of computing resources (in particular memory) is needed. In this document, we report on a successful implementation of this algorithm in Maple as well as in the BPAS library.
On the other hand, multivariate Laurent series are a generalization of multivariate power series. They play an important roll when defining Puiseux series, and in consequence, they are required to implement Nowak’s version of the famous Newton-Puiseux algorithm. In this document, we also report a first implementation of a Laurent series object inside Maple together with the challenges that we have encountered during its development.