Browsing by Author "Ihde, Steven L., author"

Now showing 1 - 2 of 2

Open Access
Preconditioning polynomial systems for homotopy continuation
(Colorado State University. Libraries, 2011) Ihde, Steven L., author; Bates, Dan, advisor; Peterson, Chris, committee member; Young, Peter, committee member
Polynomial systems are ubiquitous in today's scientific world. These systems need to be solved quickly and efficiently. One key solution method comes from Numerical Algebraic Geometry, specifically Homotopy Continuation. This method involves following paths from the solutions of a simpler system to the solutions of the target system. If we can follow fewer or better conditioned paths to the solution set, the result is better efficiency. Our goal is to precondition the original system in order to achieve such efficiency. Using dual spaces and H-bases, we are able to remove poorly conditioned paths and at worst replace them with, possibly more, better conditioned paths. At best we can trim the system down so that we track only the paths that lead to solutions. These techniques require only numerical linear algebra and are therefore easily computed. In this thesis we will introduce H-bases and dual spaces, show some promising preliminary results, and discuss further work in this area.
Open Access
Preconditioning polynomial systems using Macaulay dual spaces
(Colorado State University. Libraries, 2015) Ihde, Steven L., author; Bates, Daniel J., advisor; Peterson, Chris, committee member; Hulpke, Alexander, committee member; Young, Peter, committee member
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.