ECCA Project

subglobal1 link | subglobal1 link | subglobal1 link | subglobal1 link | subglobal1 link | subglobal1 link | subglobal1 link
subglobal2 link | subglobal2 link | subglobal2 link | subglobal2 link | subglobal2 link | subglobal2 link | subglobal2 link
subglobal3 link | subglobal3 link | subglobal3 link | subglobal3 link | subglobal3 link | subglobal3 link | subglobal3 link
subglobal4 link | subglobal4 link | subglobal4 link | subglobal4 link | subglobal4 link | subglobal4 link | subglobal4 link
subglobal5 link | subglobal5 link | subglobal5 link | subglobal5 link | subglobal5 link | subglobal5 link | subglobal5 link
subglobal6 link | subglobal6 link | subglobal6 link | subglobal6 link | subglobal6 link | subglobal6 link | subglobal6 link
subglobal7 link | subglobal7 link | subglobal7 link | subglobal7 link | subglobal7 link | subglobal7 link | subglobal7 link
subglobal8 link | subglobal8 link | subglobal8 link | subglobal8 link | subglobal8 link | subglobal8 link | subglobal8 link

Objective

Algebraic systems are fundamental mathematical objects used in the formulation, modeling, and investigation of scientific, engineering, and industrial problems, of complex information, biological, and social systems, and of natural, financial, and economic phenomena. Computational studies of algebraic systems are foundational research in information science that requires sophisticated mathematical theories and methods and that has numerous applications in other domains. The main objective of this project is to study and compute the solutions of nonlinear algebraic systems and their structures and properties with selected target applications using exact or certified computation. The project consists of one main task of basic research on the design and implementation of fundamental algorithms and four tasks of applied research on computational geometry, algebraic cryptanalysis, global optimization, and algebraic biology.

The foundational research will be based on the classical methods of Groebner bases, characteristic sets, and cylindrical algebraic decomposition introduced by three distinguished scientists, B. Buchberger, W.-T. Wu, and G. E. Collins, as well as many subsequent and significant developments and extensions made by prominent researchers, including some of the participants of this project, in the last two decades. The four domains of applied research have been chosen in view of their scientific and technological importance and the expertise and ongoing work of the project participants therein. The focus of investigation is placed on the design and analysis of fundamental algorithms for basic operations on polynomials and advanced computations with algebraic systems, efficient implementations of fundamental algorithms and software tools, and applications of the algorithms and tools to challenging problems from the four selected domains. The methodology of using exact or certified computation will take and combine the advantages of symbolic computation in producing rigorous results and numeric computation with high speed.

The consortium is composed of increasingly strong research teams from France and China in the area of solving algebraic systems with applications. It is expected that this project will strengthen the already close cooperation between French and Chinese specialists for productive research and development on exact and certified computation, result in substantial advances on the design and implementation of fundamental algorithms and software tools for studying algebraic systems, expand the applications of such algorithms and tools in the four application domains, and produce a number of joint publications and software packages.

Tasks

  • Fundamental algorithms

This task of basic research is devoted to the design, analysis, and implementation of fundamental algorithms for studying and solving algebraic systems and the underlying basic operations (elimination of variables through Grobner bases or triangular sets, approximate GCD, fast linear algebra routines, etc.). The results obtained from this task will not only lead to theoretical, algorithmic, and software advances on the subject of research, but also serve as a basis for the success of our investigations on the four application tasks described below.

  • Computational geometry

Computational geometry is an area for the algorithmic treatment of geometric problems. Such problems may arise from computer vision, computer graphics, solid modeling, robotics, etc. In computational geometry, linear objects (lines, planes, segments) are traditionally considered, leading to dicult combinatorial problems when an intrinsically nonlinear problem is modeled. A recent and deep trend in this area is to consider and integrate nonlinear objects (such as curves and surfaces) by preserving the robustness of their algorithmic treatment. To this end, the use of exact algorithms is relevant but requires some speci c algorithmic development in order to ensure a high level of eciency that is suitable for this application domain. We plan to focus our investigations on the computational determination of curves and surfaces and dynamic geometric constraint solving.

  • Algebraic cryptanalysis

A fundamental problem in cryptography is to evaluate the security of cryptosystems against the most powerful techniques. To this end, several general methods have been proposed: linear cryptanalysis, di erential cryptanalysis, etc. The aim of this task is to apply another general method - algebraic cryptanalysis - to study the security of selected public-key and secret-key cryptosystems. Algebraic cryptanalysis can be described as a general framework that permits to assess the security of a wide range of cryptographic schemes. In fact, the recent proposal and development of algebraic cryptanalysis is now widely considered as an important breakthrough in the analysis of cryptographic primitives. It is a powerful technique that applies potentially to a large range of cryptosystems. The basic principle of such cryptanalysis is to model a cryptographic primitive by a system of algebraic equations. The system of equations is constructed in such a way as to have a correspondence between the solutions of this system and secret information of the cryptographic primitive (for instance, the secret key of an encryption scheme). In this task, we will focus our attention to algebraic cryptanalysis of multivariate schemes and selected symmetric ciphers. We will also study various methods for solving algebraic systems arising in algebraic cryptanalysis.

  • Global optimization

Problems of global optimization under (semi-) algebraic constraints have many applications in engineering sciences such as aerospace, digital control, and signal processing. We will focus on end-user questions arising in applications, such as deciding if the global optimum exists and is reached, and/or nd a point in each component of the space where the global optimum is reached if it is. Researchers involved in this task have begun the development of two methods for computing the global optimum of a multivariate polynomial which appear to be complementary and may advantageously interact. The rst one is based on certifying a polynomial or rational function with rational coecients to be non-negative for all real values of the variables by decomposing it into sums of squares (SOSes) of rational fractions. The second one is based on the socalled critical point method that proceeds to computations of generalized critical values. Our goal is to provide more general algorithms, taking into account algebraic constraints, or giving algebraic certi cates for the non-negativity of a multivariate polynomial even if it cannot be written as an SOSes, for example.

  • Algebraic biology

Algebraic biology is an emerging area of research on the frontiers of biology, mathematics, and computer science. To study biological networks mathematically and computationally, the rst step is to model such networks, e.g., as discrete or continuous dynamical systems. Then the analysis of the local and global behaviors of such systems becomes a crucial and challenging problem. This analysis is carried out in the literature of experimental biology often by purely numerical simulation. The novelty of our work in this task is to use and develop e ective algebraic methods and software tools for the modeling and rigorous analysis of biological networks with exact symbolic or certi ed numerical computation.

 

 

About Us | Site Map | Privacy Policy | Contact Us | ©2012 ECCA