Algorithms in numerical algebraic geometry and applications

Abstract

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.