Electronic Thesis and Dissertation Repository

Thesis Format

Monograph

Degree

Master of Science

Program

Computer Science

Supervisor

Moreno Maza, Marc

Abstract

In this manuscript we generalize Fulton's bivariate intersection multiplicity algorithm to a partial intersection multiplicity algorithm in the n-variate setting. We extend this generalization of Fulton's algorithm to work at any point, rational or not, using the theory of regular chains. We implement these algorithms in Maple and provide experimental testing. The results indicate the proposed algorithm often outperforms the existing standard basis-free intersection multiplicity algorithm in Maple, typically by one to two orders of magnitude. Moreover, we also provide some examples where the proposed algorithm outperforms intersection multiplicity algorithms which rely on standard bases, indicating the proposed algorithm is a viable alternative as a standard basis-free intersection multiplicity algorithm.

Summary for Lay Audience

In this manuscript we describe a new, partial algorithm for computing intersection multiplicities. Given a system of polynomial equations, the intersection multiplicity of a solution point is a mathematically meaningful way of assigning a weight to that solution. To compute intersection multiplicities, complete algorithms exist which rely on a tool known as a standard basis. Standard bases are a powerful tool with many applications but suffer from some practical drawbacks. Although theoretically, it is always possible to compute a standard basis, practically this is not true; for some systems, standard bases can take hours, days, or weeks to compute. Moreover, intersection multiplicity algorithms which use standard bases assume the solution is the origin. If one wishes to compute the intersection multiplicity at a solution which is not the origin, they can in some cases apply mathematical techniques to shift their system in a way that makes the desired solution the origin, but practically this only works for a subset of "nice" solutions (points with rational coordinates). When the desired solution is not the origin and does not behave nicely (points with non-rational coordinates), intersection multiplicity algorithms which use standard bases cannot be used.

In this manuscript, we propose and implement an alternative, partial algorithm to address both of the above issues. By extending a solution to this problem which works for systems with two polynomials in two variables to a partial solution for systems with n polynomials in n variables, we obtain a powerful means of computing intersection multiplicities, which can work when techniques using standard bases may not. Moreover, we extend this partial algorithm to work at any point, rational or not, greatly extending the breadth of systems and solutions for which we can compute intersection multiplicities. Lastly, we implement these algorithmic improvements in Maple and show experiments where the proposed algorithm outperforms other intersection multiplicity algorithms.

Download

Share

COinS