Collaborative Research: AF: Small: Real Solutions of Polynomial Systems

University Of Notre Dame, Notre Dame IN

Investigators

Abstract

Many problems in science, engineering, and industry can be formulated as computing real solutions to systems of nonlinear polynomial equations. Some examples include synthesizing a mechanical linkage for a robot to perform given tasks, analyzing chemical reaction networks, and computing bifurcations in a biological process. Due to this ubiquity, there is a strong demand to tackle many large systems that naturally arise in real world settings. This project aims to develop new algorithmic approaches for efficiently and rigorously computing real solutions and test these new approaches on a variety of problems in science and engineering. Furthermore, this project will directly support the training and mentoring of graduate and undergraduate students, and will impact many other students through curriculum development in computational real algebraic geometry related to this research project. The technical aims of this project are divided into two thrusts. The first thrust develops efficient and rigorous algorithms for computing real solutions to systems of polynomial equations that have only finitely many solutions. This project focuses on developing new mathematical theories and algorithms using homotopy continuation for computing either at least one or all real solutions without needing to compute all complex solutions. For many real world problems of interest, the number of complex solutions is many orders of magnitude larger than the number of real solutions so avoiding non-real solutions is beneficial for algorithmic efficiency. The second thrust develops an algorithm for sampling smooth points in each connected component of the set of real solutions for polynomial systems with infinitely many solutions. By reducing to sample points, the algorithms from the first thrust can be applied to such positive dimensional systems. Moreover, sampling real smooth points is useful for determining the dimension of the real solution set and deciding connectedness. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.