Algorithms for Regular Chains of Dimension One

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.

Name thesis:degree_name

M Sc

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

The University of Western Ontario

Year dc:date.issued

2022

Author dc:creator

• Gonzalez Trochez, Juan P

Advisor dc:contributor.advisor

• Moreno Maza, Marc

• Regular chains
• modular method
• evaluation and interpolation
• Laurent series
• power series
• subresultant chains

Language dc:language.iso

en_ca

Handle dc:identifier.uri

https://hdl.handle.net/20.500.14721/32042

OAI identifier oai:identifier

oai:uwo.scholaris.ca:20.500.14721/32042