Polynomial System Solving


POSSO - 6846

Work Area: Symbolic Computation

Keywords computer algebra, polynomials, ideals, equations, real geometry


Start Date: 1 September 92 / Duration: 36 months / Status: running

[ participants / contact ]


Abstract Polynomial Systems occur everywhere in Mathematics, Science and Technology. Very small systems are easily solved by hand, but larger systems cannot reliably be so solved, if at all. Moreover, a systematic study of these systems reveals many features that are not intuitively obvious. POSSO will investigate these problems from an algorithmic point of view, produce a solver in package form, and develop some application areas also with specific versions of the solver with suitable front-ends.


Aims

The project aims to produce a portable software solver using the latest in polynomial system solving algorithms and capable of being incorporated into applications programs. Research will be carried out to advance the state of the art and our understanding of polynomial systems, and various application areas will be studied, such as control theory, geometric modelling, and biochemistry in which problems reducible to polynomial system solving arise. These aims are not independent: the software will incorporate as much of the newly-discovered material as possible, and the applications will benefit from the facilities in the solver. Conversely, the solver will benefit from the experience of having been used on real problems. This project aims to produce a portable software solver using the latest in polynomial system solving algorithms and capable of being incorporated into applications programs. Research will be carried out to advance the state-of-the-art and our understanding of polynomial systems, and various application areas will be studied, such as control theory, geometric modelling and biochemistry, in all of which problems reducible to polynomial system solving arise.

These aims are not independent: the software will incorporate as much of the newly discovered material as possible, and the applications will benefit from the facilities in the solver. Conversely, the solver will benefit from the experience of having been used on real problems.

Approach and Methods

Purely numerical solving of polynomial systems leads to many problems: numerical inaccuracy; not finding all solutions, and not recognising under-determined systems; not understanding the structure of the solutions; and inability to handle over-determined systems. These problems are not purely theoretical: they have caused major practical problems in areas ranging from aerospace engineering to pharmacology. The solution to these problems is to perform symbolic computation on the set of polynomial equations (and inequalities) instead of, or as well as, numeric computation. Such computations require the careful use of advanced mathematical ideas.

The structure of the solver that we propose to produce will be radically different from what is customary in symbolic computation systems with built-in solvers that can be used only inside the system itself. POSSO will develop a solver in ``package'' form, so that to build an application only those parts that are necessary need to be obtained.

The advanced research issues developed inside the projects are aimed at algorithmic advances related to the solver. Whilst the current methods are satisfactory for zero dimensional systems, they are not completely suitable for higher dimensional systems, for which many qualitative aspects of solving still need to be clarified.

POSSO will investigate the problems connected to polynomial system solving, and for some application areas we will probably develop application-specific extensions to, or front-ends for, the solver.

Progress and Results

In the first year of POSSO considerable progresses have been achieved, and some relevant results have been obtained in the three domains of the project: solver, algorithms, applications.

In the solver construction, a customisable memory management (CMM) in C++ has been produced; the solver C++ library will be built in top of it. The CMM will be suitable of use outside of the project. It is currently in alpha test.

Protocols for data related to polynomial systems and symbolic computing have been proposed, and will be experimented.

Software for computing Gröbner bases (GB) has been provided (beta test). It includes a preliminary version of CMM, big and modular integers, ability to split the work on a net of computer and a full interface with Axiom. As it is designed on principles which are close to those of our solver, it is a tool for experimenting during the construction of the solver, and some parts of GB are under adaptation for being included in the solver.

A collection of tests for polynomial system solving has been prepared and continuously updated, and is currently distributed.

Algorithmic advances have been obtained, that allow in several examples of polynomial systems relevant for applications a speed-up of a factor larger than ten. This has been included in some experimental software, and the inclusion in the future distribution of the C++ library is planned.

The complexity theory of problems related to polynomial system solving has been considerably improved, with better estimates in a sparse complexity model.

Two different experimental implementations for working with real algebraic numbers have been produced. Moreover new theoretical advances have been attained concerning real root counting and isolation in the multivariate case.

Applications have been studied, obtaining interesting results linking Polynomial System Solving with Robot Kinematics (Stewart Platform, path lifting), Motion Planning, Curve and Surface Tracing, Geometric Modelling and Singularity Theory.

Potential

The solver will be linked to several existing or future computer algebra systems, enhancing their performances. It is likely that the algorithmic research developed will allow considerable progress in the area of polynomial system solving, especially in higher dimension, and that several application areas will benefit from our application-specific versions.

The customisable memory management might be used as a basis for the construction of symbolic software including a default memory management and the possibility of customised memory management in some time-critical parts; in particular, an implementation of COMMON-LISP with these features might be easily produced, and could be the basis of many efficient computer algebra systems.

Latest Publications

Information Dissemination Activies

Together with internal workshops devoted to specific topics related to the Project, the POSSO Project has been presented at several international scientific meetings. A Workshop aimed to present the results obtained in the first year is planned in Sophia-Antipolis from Sept. 6 to Sept. 9.

Further information about POSSO is available from the POSSO home page <URL:http://posso.dm.unipi.it/>.


Coordinator

Università di Pisa - I
Dipartimento di Matematica
Via Buonarroti 2
I - 56123 PISA

Partners

RISC-Linz - A
Fernuniversität Hagen - D
Universidad de Cantabria - E
Université de Nice-Sophia Antipolis - F
Université Pierre et Marie Curie - F
Università di Genova - I
Stockholms Universitet - S
University of Bath - UK

CONTACT POINT

Prof. C. Traverso
tel +39/50-59.95.13
fax +39/50-59.95.24
e-mail: traverso@dm.unipi.it


LTR synopses home page LTR work area index LTR acronym index LTR number index LTR Projects index
All synopses home page all acronyms index all numbers index

POSSO - 6846, August 1994


please address enquiries to the ESPRIT Information Desk

html version of synopsis by Nick Cook