English
Many applications in scientific computing can be modeled via polynomial systems possibly with parameters. Most information about the initial problem is thus encoded in the solution set of such systems. In the simplest examples, the solutions are a finite set of points, but to model more complex applications, more variables and constraints are needed and the set of solutions can be a curve, a surface or an even higher dimensional object. Some applications, such as robotics or visualization, require a description of the solution set with guarantees. One can distinguish two types of guarantees: topological, all the components and all the singularities (isolated points or self-intersections) must be reported; geometrical, the solution set must be approximated within a given distance. Theoretically, symbolic methods from computer algebra can guarantee the topology of any polynomial system via resultants, Gröbner basis or Cylindrical algebraic decomposition. However, the high complexity of these purely algebraic methods prevents them to be applied in practice on difficult instances. On the other hand, purely numerical methods such as interval arithmetic or subdivision are efficient in practice for non-singular set, but are lacking topological guarantees near singular points. This issue is a long-time challenge in the community of numerical computation. This exposition of the strengths and weaknesses of symbolic/numeric methods advocates for a new trend of work combining symbolic and numeric methods together. The objective of our project is to intertwine further symbolic/numeric approaches to compute efficiently solution sets of polynomial systems with TOPOLOGICAL and geometrical guarantees in the SINGULAR case. Technically, we will explore the use of local algebraic properties (local rings at singularities) and interval arithmetic (Krawczyk operator) to isolate singularities. Currently, certifying the topology around one singular point requires the certification of the topology around all singular points (e.g. homotopy methods) or the usage of non-practical separation bounds (e.g. subdivision). Our new singular certification criteria will be local and will naturally improve algorithms based on subdivision and algorithms based on path tracking. We are aware of the a priori high complexity of the worst-case scenario for general polynomial systems. Hence, instead of working on general systems, one objective is to identify classes of problems with restricted types of singularities and develop dedicated methods that take advantage of the structure of the associated polynomial systems. We focus on two applications: the visualization of algebraic curves and surfaces and the mechanical design of robots. We plan to extend the class of manipulators that can be analyzed, and the class of algebraic curves and surfaces that can be visualized with certification. The partners of the project are selected for the complementarity of their expertises. Guillaume Moroz is an expert of computer algebra and developed the Maple package RootFinding[Parametric] and specific tools for robotics (ANR SIROPA 2007-2011). Marc Pouget is an expert of topology and geometry of curves and surfaces and developed visualization software (CGAL and Isotop). G. Moroz and M. Pouget are both in the INRIA VEGAS team, G. Moroz is new in the team and strengthens the non-linear computational geometry theme of VEGAS. We also have two teams of external collaborators. Joris Van Der Hoven and Grégoire Lecerf are experts in numerical and symbolic computations and computer algebra systems (Mathemagix). Finally, Philippe Wenger and Damien Chablat, from the robotic team at IRCCyN, who work on the mechanical design of manipulators will validate our methods with our prototype implementations.
