Repository logo

Preconditioning polynomial systems using Macaulay dual spaces


Polynomial systems arise in many applications across a diverse landscape of subjects. Solving these systems has been an area of intense research for many years. Methods for solving these systems numerically fit into the field of numerical algebraic geometry. Many of these methods rely on an idea called homotopy continuation. This method is very effective for solving systems of polynomials in many variables. However, in the case of zero-dimensional systems, we may end up tracking many more solutions than actually exist, leading to excess computation. This project preconditions these systems in order to reduce computation. We present the background on homotopy continuation and numerical algebraic geometry as well as the theory of Macaulay dual spaces. We show how to turn an algebraic geometric preconditioning problem into one of numerical linear algebra. Algorithms for computing an H-basis and thereby preconditioning the original system to remove extraneous calculation are presented. The concept of the Closedness Subspace is introduced and used to replace a bottleneck computation. A novel algorithm employing this method is introduced and discussed.


Rights Access


dual space
algebraic geometry


Associated Publications