## Search

# SYNAPS, New developments in solution of systems of polynomial

The idea behind SYNAPS is that solving polynomial equations is ubiquitous in many area, including robotics, computer vision, computational biology, computer aided (geometric) design. Though this is an old problem, going back to the ancient Greek or Chinese period, it is still an active domain of research. The need to combine certification and efficiency leads to new tools, which can be used nowadays in a large variety of applications.

In the fp5 IST FET project IST-2001-35512 “Intersection algorithms for geometry based ITapplications using approximate algebraic methods” new approaches combining numeric and algebraic techniques are developed for solving systems of polynomial equations. The project results have a substantial potential use outside of CADalthough surface intersections and self-intersection within high end CAD is the main focus. Parts of the results of the GAIA II project are assembled in the SYNAPA library.

While classical algebraic geometry is not concerned with coordinate systems, choices of polynomial bases or floating point precision, these topics play a central role when developing industrial type algorithms within CAGD. While classical algebraic geometry supplies insight into the problems addressed, CAGD supplies a number of important tools for solving challenging problems formulated as polynomial equations:

- Polynomial bases that are a partition of unity over the domain of interest (e.g. the Bernstein basis) supplies tools that helps determine if a solution is possible or not.
- The coefficients of a polynomial represented in a basis that is a partition of unity mimics the behavior of the polynomial.
- Recursive subdivision is useful when establishing simpler sub problems.

The need to combine symbolic and numeric computations is ubiquitous in many problems. Starting with an exact description of the equations, in most cases, we will eventually have to compute an approximation of the solutions. Even more, in many problems the coefficients of the equations may only be known with some inaccuracy (due, for instance, to measurement errors). This leads to new, interesting and challenging questions either from a theoretical or practical point of view at the frontier between Algebra and Analysis and witnesses the emergence of new investigations.

The aim of SYNAPS (http://www-sop.inria.fr/galaad/software/synaps/) is to provide a coherent platform for this new type of scientific computation. The library provides datastructures and classes for the manipulation of basic objects, such as (dense, sparse, structured) vectors, matrices, and univariate and multivariate polynomials. As SYNAPS is targeting different domains of application, it makes it possible to define parameterized but efficient data structures for fundamental algebraic objects such as (dense, sparse, structured) vectors, matrices, univariate and multivariate polynomials . . . which can be used easily in the construction of more elaborated algorithms. We pay a special attention to genericity, or more precisely to parameterized types (templates in C++ parlance) which allow us to tune easily the data structure to each specific problem at hand.

Special efforts have been developed to provide, in this library, a family of efficient polynomial solvers. This includes univariate polynomial solvers, using the Bernstein representation, Weierstrass type solvers for complex univariate roots, but also multivariate polynomial solvers either based on algebraic approaches, using resultants or generalised normal forms methods or subdivision methods, based on multivariate Bernstein basis representation. We will demonstrate these solvers combining numeric and symbolic techniques. Their use will be illustrated on CAD, robotics, and design applications.

- Login to post comments