Chinese SALSA Project

Introduction

This project is the collaboration of two teams from France and China. The common objective is to work out the resolution of the algebraic systems by exact (or at least certified) calculation. And the ultimate goal is the preferably industrial applications based on considerable software development.

We will achieve the objective by three orders: to share knowledge on certain fundamental fields (Gröbner bases and triangular sets), to develop new methods for the resolution of the (semi-)algebraic systems and to draw apart the diversity from the applicatifs fields approached of the two with dimensions ones to develop this work{原文la diversité des domaines applicatifs abordés des deux cotés pour valoriser ce travail} (cryptography, automatic deduction, robotics, signal processing).

Functionary

Details

Coodinators

Bican Xia is the Chinese coodinator, although the director of the Chinese laboratory (Zhiming Zheng) is in the team.

Bican Xia is associate professor in Peking University and vice chair of the Department of Information Science. He is also in charge of the topic "Computational Complexity, Symbolic Computation and Automated Reasoning" in his laboratory.

He worked out his thesis in 1998 in mathematics at Sichuan University (China) and got his current position since 2000 after two years of post-doctoral training course in Beijing.

Quote mobility, he spent 2 months to the Max-Planck Institute (Germany) in 2002 (February/March) and 7 months to "Free University" of Berlin in 2003 (January/February). {原文Coté mobilité, il a passé 2 mois au Max-Planck Institute (Allemagne) en 2002 (Février/Mars) et 7 mois à la "Free University" de Berlin en 2003 (Janvier/Février).}

Since 2000, he published six articles in international newspapers with good reputation and made six lectures in international conferences.

History of the Collaboration

This proposal is certainly interesing since it is not a problem to support the existing collaboration and the fund between teams established well. We are aiming not only to obtain measurable results in the short run, but rather to weave a durable long term bond between two young teams.

In INRIA, SALSA team is still in the creation and have not officially stated the project yet (but received the positive final opinion from the committee of Rocquencourt  in October 2005). All members will take part in the project (6 permanent 不懂,  6 doctorands).

The Chinese team belongs to a new (2005) laboratory (Key Laboratory of Mathematics, Informatics and Behavioral Semantics of the Ministry of Education of China, Beihang University and Peking University) where Zhiming Zheng (one participant of our project) is the director. This laboratory locates on several sites (Beihang University, Peking University and Chinese Academy of Sciences) and has three broad topics one of which is "Computational Complexity, Symbolic Computation and Automated Reasoning". Bican Xia and Dongming Wang (both are participants of our project) have the responsibility for it.  This team consists of 5 doctorands and 5 permanent: Zhiming Zheng, which is the director of the laboratory and vice-president of the Beihang University,  Bican Xia (University of Peijing),  Mingsheng Wang (Chinese Academy of Sciences), Lihong Zhi (Chinese Academy of Sciences), Zhuojun  Liu (University of Beihang).

A key person of this project is Dongming Wang, representative of "Chinese Mathematical Society" in Europe, former member of the project SPACES from which team SALSA comes. He currently shares his time between the team CALFOR (of which the half constitutes project SALSA) and LIP6, where he affects as the Director of Research CNRS, the team consisted our Chinese colleagues, and is a Professor. Only because of his part-time presence on the French territory, he is not a member of SALSA team now, although his research subjects fitting perfectly with the themes of our team. {原文不理解处： Il partage actuellement son temps entre l'équipe CALFOR (dont la moitié constitue le projet SALSA) du LIP6, où il est affecté comme Directeur de Recherche CNRS, et l'équipe constituée par nos collègues Chinois, ou il occupe un poste de Professeur. }

Under the motivation by Dongming Wang, two workshops have already been organized: the first in France in 2000, the second in Beijing this year. Several person of these workshops were concerned with SALSA project. Although there were some common publications during the last years, the exchanges actually began in 2003, with the reception of Mr. Wang as the associated researcher CNRS from September to November and were reinforced in the following year by the visit of F Rouillier and P. Aubry in Beijing in 2004. In 2005, two researchers of team SALSA (P. Trébuchet and G Moroz) gave talks at a school of Beijing, where F Rouillier will take an interview which is organized by D. Wang and X Bican and is planned for the summer 2006 (http://www.cc4cm.org/sssc2006/english.htm).

Topics and Objectives

The fundamental research topics of the two teams coincide perfectly. To summarize, the two teams work on the resolution of the algebraic systems by exact (or certified) calculation, with the ultimate goal that make out the preferably industrial (not if running in this field) applications based on excessive software development. The two teams have an operation by similar multi-stage subjects which can be summarized as follows:

• [A] basic tools to study the ideals and the algebraic varieties (complex coefficients, 这两个不懂corps finis, réels, etc.)
• [B] algorithms based on [A] to study the algebraic and semi algebraic real sets
• [C] implementation of [A] and [B]
• [D] applications

For examples of the basic objectives, one refer to the document presentation of SALSA project (http://fgbrs.lip6.fr/salsa/salsa.pdf).

Although the principal objectives and topics coincide, the two teams have initially different but completely complementary research directions. In the recent methods developed for point [A] by the participants, there are two distinguishing principles: calculating the Gröbner bases or calculating the triangular sets. The Gröbner bases constitute a privileged research field for SALSA project and Jean-Charles Faugère is the author of the most powerful algorithms of the moment. The triangular sets are very studied historically in China for the principal's initiator is professor Wu. Dongming Wang is a uncontested specialist in this field, being the author of several works and software. These two sights are completely complementary but narrowly connected, as the publications of D. Lazard and P. Aubry (members of team SALSA) confirmed it (for example, one can calculate a decomposition in triangular sets by the bases of Gröbner). Quote Chinese, the point [B] is approached while primarily considering [A] methods based on triangular sets. Although their developments massively use the Gröbner bases for stage [A], the researchers of SALSA showed that the triangular sets were doubtless impossible to circumvent for the point [B]. For example, one can refer to the publications of P. Aubry, F Rouillier and Mr. Safey El Din for the study of the real varieties, and to that of D. Lazard and F Rouillier for the resolution of the systems depending on parameters..

An essential point for calculations on the algebraic varieties is subjacent with point [A]: calculations of decomposition of ideals or varieties in equal-dimensional 不明白and/or radical components and/or first. This subject for the hour is relatively badly encircled for calculation when pass the existing solutions on the scale on significant problems (applications). This topic will probably be central since such decompositions are impossible to circumvent. As one studying the singularities of an algebraic variety, the calculation of those being essential for the algorithms treating the real algebraic sets (and semi-algebraic sets). To summarize, the methods based on triangular sets calculate in a lazy way of the decompositions sufficient (equal-dimensional and radical) for almost all concerned problems, but are difficult to implement. The bases of Gröbner make it possible to extract some components with the remarkable geometrical properties effectively. The idea is to combine the two views, either by helping the triangular decomposition by carrying out some calculations of Gröbnerbases or by recovering the "lazy" strategy of the triangular decompositions to adapt it to calculate Gröbner bases.

For point [B], the researchers of SALSA have considerable experience and are currently leaders of the field, but one assists, under the impulse by Bican Xia, with a rise to remarkable power of our Chinese colleagues. The starting point of collaboration will be doubtless the study of the systems depending on parameters. This subject for the hour is very badly solved in formal calculation although being of capital importance for the applications (see the recent works of D. Lazard and F Rouillier). The objectives are impossible to circumvent (apart from any algorithm) for the study of zero realities of this type of systems were specified very recently (2005) by D. Lazard and F Rouillier. In this study, it appears that for certain situations, the use of triangular sets is essential for an efficient implementation, confirmed by the most recent work of Bican Xia (ISSAC 2005).

As regards the applications, the intersection is currently naturally weak, which is one of the strong points of the project since we will be able to thus multiply the actions of valorization. Quote Chinese, the massive use of triangular sets restricted the potential of calculation (degrees and a number of variables in the equations) but makes it possible to provide formal results of a great interpretation and ease of use. The natural fields of applications are the algorithmic geometry, the automatic evidence of theorems. Quote SALSA, the power of calculating Gröbner bases developed in the project in any case apprehend more important classes of problems.{原文Coté SALSA, la puissance des algorithmes de calcul de bases de Gröbner développés dans le projet permettent certainement d'appréhender des classes de problèmes plus importantes, en tout cas en l'état actuel des choses. } The privileged applicability is cryptography (see Inédit number 40), robotics (see Inédit number 23) and the signal processing (patent in 1998 - ARC in 2005). In spite of these successful progress related to Gröbner bases, the triangular sets remains privileged research by orientation of SALSA since to calculate this type of problem effectively would make significant progress for the point [B]. However this axis is currently withdrawing compared to the other developments, for lack of time: the effective establishment in low-level language requires a considerable investment and this project will make it possible to give an important impulse. Conversely, the interest of the Chinese researchers to calculate Gröbner bases is growing. Within the framework of our project, one can quote the work of Zhaoqiang Yang framed by Dongming Wang on the recent algorithms of J.C. Faugère, the further goal being to diversify the possibilities of point [A] and to increase the concerned applicability. {原文Dans le cadre de notre projet, on peut citer entre autres le travail de Zhaoqiang Yang encadré par Dongming Wang sur les algorithmes récents de J.C. Faugère, le but étant la encore de diversifier les possibilités pour le point [A] et augmenter les domaines d'applications visés}

The point [C] will be easiest to manage. In SALSA, a certain number of developments are carried out in Maple, the critical operations (in terms of computing time) being insulated and implemented in language C and being interfaced with Maple (see http://fgbrs.lip6.fr/Software for software GB, FGb, RS, RAGlib, etc). A contract with company WMI (company developing and marketing the famous Maple software) will be signed at the end of 2005 which will include the developments SALSA into the official version of the Maple software. For Chinese, all the software is established in Maple (see http://www-calfor.lip6.fr/~wang/  for the software CHARSETs and Epsilon,  http://www.math.pku.edu.cn/staff/tquery.asp?TID=104 for DISCOVERER). Thus, no strategic change needs to operate to develop the new results and the developments will in addition increase the number of productions planned for contract WMI.

Impact

For the teams of research, the interests are obvious as all the members of the two teams are directly concerned with the subjects suggested. (原文Du coté des équipes de recherche, les intérêts sont évidents, d'autant que tous les membres des 2 équipes sont directement concernés par les sujets proposés.) For SALSA, it is a question of currently supporting a research orientation in free wheel for lack of human means{原文 de moyens humains} (triangular sets) and of increasing the number of its applicability. For the Chinese part, the situation is symmetrical: it is still a question of increasing the number and the importance of the applicability but also of diversifying the techniques of calculation (bases of Gröbner) or of perfecting certain knowledge (not [B]). Put aside the applications, the progress awaited in the resolution of the systems depending on parameters will constitute a criterion for evaluating the common work in future.

One could be much more ambitious for the Chinese laboratory of our colleagues (of which one of the researchers of this proposal, Zhiming Zheng, is the director) relates to two other topics present at the INRIA: (1) Geometric Theory of Nonlinear Differential Equations, Dynamic Systems and Modular Theory Representation; (2) Theory of Computer Software and Network Environments.

For example propose, in the short run, with the project COFFEE (INRIA-Sophia) to join to some extent (E Hubert for example) the associated team since which they are concerned directly by certain research carried out (triangular sets and differential connections) and could lie within the scope of a collaboration on the topic (1) mentioned above. In the longer term, this project could also concern several teams with whom SALSA collaborates regularly.{原文，整段，前半部分不理解On peut par exemple proposer, à court terme, au projet CAFE (INRIA-Sophia) de rejoindre pour partie (E. Hubert par exemple) l'équipe associée puisque qu'ils sont concernés directement par certaines recherches effectuées (ensembles triangulaires et systèmes différentiels) et pourraient s'inscrire dans le cadre d'une collaboration sur le thème (1) mentionné ci-dessus. A plus long terme, ce projet pourrait également concerner plusieurs équipes avec lesquelles SALSA collabore régulièrement}

Prospect of 2006

The work of project for the year 2006 relates primarily to the points [A] and [B].

For point [A], a work of formation on the algorithms F4 and F5 (J.C. Faugère) for calculating Gröbner bases will be carried out. In addition, we will make a complete view on the algorithms and implementation for the calculation of decompositions in triangular sets.

For the point [B], we will work to homogenize the results of D. Lazard and F Rouillier on the one hand and Bican Xia on the other hand, concerning the algebraic semi systems depending on parameters. Besides this work will make it possible to give precise specifications for the algorithms of part [A].

For point [D], we will calibrate each methods developed for applications that we already know to solve. The idea is to release the classes of the most favorable (or unfavourable) examples with the various methods, being ideally classify these classes of examples mathematically.

This work will make it possible to plan the part [C] which should be the principal point of the activities of the second year on the applications.