Browsing by Author "Bates, Daniel J., advisor"

Now showing 1 - 5 of 5

Open Access
Algorithms in numerical algebraic geometry and applications
(Colorado State University. Libraries, 2015) Hanson, Eric M., author; Bates, Daniel J., advisor; Peterson, Chris, committee member; Cavalieri, Renzo, committee member; Maciejewski, Anthony, committee member
The topics in this dissertation, while independent, are unified under the field of numerical algebraic geometry. With ties to some of the oldest areas in mathematics, numerical algebraic geometry is relatively young as a field of study in its own right. The field is concerned with the numerical approximation of the solution sets of systems of polynomial equations and the manipulation of these sets. Given a polynomial system ƒ : CN → Cn, the methods of numerical algebraic geometry produce numerical approximations of the isolated solutions of ƒ(z) = 0, as well as points on any positive-dimensional components of the solution set, V(ƒ). In a short time, the work done in numerical algebraic geometry has significantly pushed the boundary of what is computable. This dissertation aims to further this work by contributing new algorithms to the field and using cutting edge techniques of the field to expand the scope of problems that can be addressed using numerical methods. We begin with an introduction to numerical algebraic geometry and subsequent chapters address independent topics: perturbed homotopies, exceptional sets and fiber products, and a numerical approach to finding unit distance embeddings of finite simple graphs. One of the most recent advances in numerical algebraic geometry is regeneration, an equation-by-equation homotopy method that is often more efficient than other approaches. However, the basic form of regeneration will not necessarily find all isolated singular solutions of a polynomial system without the additional cost of using deflation. In the second chapter, we present an alternative to deflation in the form of perturbed homotopies for solving polynomial systems. In particular, we propose first solving a perturbed version of the polynomial system, followed by a parameter homotopy to remove the perturbation. The aim of this chapter is two-fold. First, such perturbed homotopies are sometimes more efficient than regular homotopies, though they can also be less efficient. Second, a useful consequence is that the application of this perturbation to regeneration will yield all isolated solutions, including all singular isolated solutions. The third chapter considers families of polynomial systems which depend on parameters. There is a typical dimension for the variety defined by a system in the family; however, this dimension may jump for parameters in algebraic subsets of the parameter space. Sommese and Wampler exploited fiber products to give a numerical method for identifying these special parameter values. In this chapter, we propose a refined numerical approach to fiber products, which uses recent advancements in numerical algebraic geometry, such as regeneration extension. We show that this method is sometimes more efficient then known techniques. This gain in efficiency is due to the fact that regeneration extension allows the construction of the fiber product to be restricted to specified irreducible components. This work is motivated by applications in Kinematics - the study of mechanisms. As such we use an algebraic model of a two link arm to illustrate the algorithms developed in this chapter. The topic of the last chapter is the identification of unit distance embeddings of finite simple graphs. Given a graph G(V,E), a unit distance embedding is a map ɸ from the vertex set V into a metric space M such that if {vi,vj} is an element of E then the distance between ɸ (vi) and ɸ (vj) in M is one. Given G, we cast the question of the existence of a unit distance embedding in Rn as the question of the existence of a real solution to a system of polynomial equations. As a consequence, we are able to develop theoretic algorithms for determining the existence of a unit distance embedding and for determining the smallest dimension of Rn for which a unit distance embedding of G exists (that is, we determine the minimal embedding dimension of G). We put these algorithms into practice using the methods of numerical algebraic geometry. In particular, we consider unit distance embeddings of the Heawood Graph. This is the smallest example of a point-line incidence graph of a finite projective plan. In 1972, Chvátal conjectured that point-line incidence graphs of finite projective planes do not have unit-distance embeddings into R². In other words, Chvátal conjectured that the minimal embedding dimension of any point-line incidence graph of a finite projective plane is at least 3. We disprove this conjecture, adding hundreds of counterexamples to the 11 known counterexamples found by Gerbracht.
Open Access
Avoiding singularities during homotopy continuation
(Colorado State University. Libraries, 2017) Hodges, Timothy E., author; Bates, Daniel J., advisor; Böhm, A. P., committee member; Hulpke, Alexander, committee member; Peterson, Christopher, committee member
In numerical algebraic geometry, the goal is to find solutions to a polynomial system F(x1,x2,...xn). This is done through a process called homotopy continuation. During this process, it is possible to encounter areas of ill-conditioning. These areas can cause failure of homotopy continuation or an increase in run time. In this thesis, we formalize where these areas of ill-conditioning can happen, and give a novel method for avoiding them. In addition, future work and possible improvements to the method are proposed. We also report on related developments in the Bertini software package. In addition, we discuss new infrastructure and heuristics for tuning configurations during homotopy continuation.
Open Access
Gale duality, decoupling, parameter homotopies, and monodromy
(Colorado State University. Libraries, 2014) Niemerg, Matthew E., author; Bates, Daniel J., advisor; Shipman, Patrick, committee member; Peterson, Christopher, committee member; Lee, Chihoon, committee member
Numerical Algebraic Geometry (NAG) has recently seen significantly increased application among scientists and mathematicians as a tool that can be used to solve nonlinear systems of equations, particularly polynomial systems. With the many recent advances in the field, we can now routinely solve problems that could not have been solved even 10 years ago. We will give an introduction and overview of numerical algebraic geometry and homotopy continuation methods; discuss heuristics for preconditioning fewnomial systems, as well as provide a hybrid symbolic-numerical algorithm for computing the solutions of these types of polynomials and associated software called galeDuality; describe a software module of bertini named paramotopy that is scientific software specifically designed for large-scale parameter homotopy runs; give two examples that are parametric polynomial systems on which the aforementioned software is used; and finally describe two novel algorithms, decoupling and a heuristic that makes use of monodromy.
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.
Open Access
The numerical algebraic geometry approach to polynomial optimization
(Colorado State University. Libraries, 2017) Davis, Brent R., author; Bates, Daniel J., advisor; Peterson, Chris, advisor; Kirby, Michael, committee member; Maciejewski, A. A., committee member
Numerical algebraic geometry (NAG) consists of a collection of numerical algorithms, based on homotopy continuation, to approximate the solution sets of systems of polynomial equations arising from applications in science and engineering. This research focused on finding global solutions to constrained polynomial optimization problems of moderate size using NAG methods. The benefit of employing a NAG approach to nonlinear optimization problems is that every critical point of the objective function is obtained with probability-one. The NAG approach to global optimization aims to reduce computational complexity during path tracking by exploiting structure that arises from the corresponding polynomial systems. This thesis will consider applications to systems biology and life sciences where polynomials solve problems in model compatibility, model selection, and parameter estimation. Furthermore, these techniques produce mathematical models of large data sets on non-euclidean manifolds such as a disjoint union of Grassmannians. These methods will also play a role in analyzing the performance of existing local methods for solving polynomial optimization problems.