Finding all real solutions of polynomial systems

Abstract

In this thesis we give numerical algorithms to find theone-dimensional and two-dimensional parts of the solution sets on$RN$ of systemsegin{equation}label{realSystem}f(x):=left[egin{array}{c} f{1}(x{1},ldots,x{N}) \\ vdots \\ f{n}(x{1},ldots,x{N}) end{array}ight]=0end{equation}of $n$ polynomials on $RN$.Typically, we want to find the solutions on $RN$ as opposed to the solutions on $CN$ when we need to solve such a system of $n$polynomials. However, the real solutions are much more complicated and expensive to compute than the complex solutions. Our approach is to find the real solutions starting with the known complex components. Recently in cite{SVW1,SVW2,SVW3}, new techniques have been successfully developed to numerically decompose complex algebraic sets into irreducible components. With the help of this decomposition and a Morse-theoretic decomposition, we give algorithms for numerically computing the real solution sets. The Morse-theoretic decomposition only works for multiplicity one components. For the components of multiplicity at least two, we use the technique of deflation to make them into reduced components in a higher dimensional space. The one-dimensional and two-dimensional real sets are the most interesting ones in applications. We focus on these two cases in this thesis. An application of our algorithms to mechanisms, specifically the Stewart-Gough platform robot, is presented.