Collaborative Research: Numerical Algorithms and Software for Solving Polynomial Systems with Parameters

University Of Notre Dame, Notre Dame IN

Investigators

Abstract

In this collaborative project the investigators Sommese, Wampler, and Verschelde construct and implement new algorithms to numerically describe algebraic sets defined by systems of parameterized polynomial equations. The scope of work goes beyond conventional problems, where one seeks the solution set when the parameters are given, to include the determination of parameter sets that change the nature of solution components in a specified manner. Of special interest are solution sets whose dimension is exceptionally large. Problems such as these, e.g., the discovery and classification of overconstrained mechanisms, can be reduced to computing the irreducible decomposition of certain exceptional loci of polynomial systems with parameters. This is then reduced to finding the numerical irreducible decomposition of a finite number of associated polynomial systems. As this leads to large systems, a new equation-by-equation approach to solving polynomial systems is developed. To tackle nontrivial problems, the algorithms is implemented on parallel computers. Solving a polynomial equation -- finding the roots of the polynomial -- is an old problem that occurs over and over in more complicated forms throughout science and engineering. In applications involving mechanical design, finding the solution of a system of polynomial equations is only one step in a larger scheme: to arrive at better designs by describing how the set of solutions of a polynomial system depends on parameters of the system. This problem arises in design of industrial robots, for example. The investigators develop new methods for describing the solution sets of polynomial systems with parameters. The methods have the potential to become a standard tool in the design of robots and mechanisms. Furthermore, the methods promise to have a wider impact on the research fields of numerical analysis and computer algebra, especially in efforts seeking to provide the scientific community with software to solve mathematical problems. An important result of this work is publicly available software based on these new methods, with interfaces facilitating use by the wider community. By solving some difficult polynomial systems that arise in science and engineering, the team stimulates interest in these advanced methods and provides illustration of their usage for the nonspecialist. The project includes collaboration with and training of students.