Repository logo
 

Algorithms in numerical algebraic geometry and applications

Simple item page
dc.contributor.authorHanson, Eric M., author
dc.contributor.authorBates, Daniel J., advisor
dc.contributor.authorPeterson, Chris, committee member
dc.contributor.authorCavalieri, Renzo, committee member
dc.contributor.authorMaciejewski, Anthony, committee member
dc.date.accessioned2015-08-28T14:35:26Z
dc.date.available2015-08-28T14:35:26Z
dc.date.issued2015
dc.description.abstractThe 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.
dc.format.mediumborn digital
dc.format.mediumdoctoral dissertations
dc.identifierHanson_colostate_0053A_13157.pdf
dc.identifier.urihttp://hdl.handle.net/10217/167182
dc.languageEnglish
dc.language.isoeng
dc.publisherColorado State University. Libraries
dc.relation.ispartof2000-2019
dc.rightsCopyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright.
dc.subjectnumerical algebraic geometry
dc.titleAlgorithms in numerical algebraic geometry and applications
dc.typeText
dcterms.rights.dplaThis Item is protected by copyright and/or related rights (https://rightsstatements.org/vocab/InC/1.0/). You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
thesis.degree.disciplineMathematics
thesis.degree.grantorColorado State University
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy (Ph.D.)

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Hanson_colostate_0053A_13157.pdf
Size:
830.82 KB
Format:
Adobe Portable Document Format
Download

Collections

2000-2019
Theses and Dissertations