Electronic Thesis and Dissertation Repository

Thesis Format

Monograph

Degree

Master of Science

Program

Computer Science

Supervisor

Moreno Maza, Marc

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.

Summary for Lay Audience

Regular chains are triangular sets of polynomials used to solve systems of polynomial equations. In this work, we focused in one dimensional regular chains. That is, regular chains where the number of equations is one less than the number of variables. In particularly, we solve the intersection between a one dimensional regular chain and a polynomial by means of evaluation and interpolation, under certain hypothesis. A Maple and a C version of this modular algorithm is presented. In addition, we also report a first implementation of a Laurent series object inside Maple as a first step to achieve multivariate Puiseux series. Multivariate Laurent series are a generalization of multivariate power series; and Puiseux series are key when computing limit points of one dimensional regular chains.

Download

Share

COinS