Bienvenu sur le site du projet ANR SingCAST:
Singular Curves and Surfaces Topology
RÉSUME DE LA PROPOSITION DE PROJET / EXECUTIVE SUMMARY
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.
Figures 1 and 2 display geometric approximations of curves and illustrate the difficulty of guessing the topology with limited precision.
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.
