A3 · Algebraic Algorithms and Applications
FP7 — People (Marie Curie Actions)
- Duration
- 2013-05-01 → 2017-04-30
- EU contribution
- €100,000
- Participants
- 1
- Scheme
- MC-CIG
Lines connect the coordinator with its partners.
Results in brief
Algebraic Algorithms and Applications
Traditional techniques in algorithms usually treat/compute linear objects and quantities. In recent years, there have been efforts to extend the range of our techniques using tools from (real) algebraic geometry, which pertain to basic questions about the real roots of equations, to handle non-linear objects. A3 addressed the challenge to provide solid mathematical and algorithmic foundations, and efficient implementations for computations with curved objects. The overall objectives of the project span the following main axes. • Algebraic algorithms Improved algorithms for solving univariate polynomials. • Non-linear computational geometry Computations with non-linear geometric objects using algebraic tools. • Game theory Applications of algebraic algorithms and techniques to problems in game theory. • Effective implementations Software libraries for computations with real algebraic numbers and solving of polynomials. There has been progress in all main axes, which is detailed in the next section (Work progress and achievements during the period) Our work on the foundations of algebraic algorithms resulted optimal, up to poly-logarithmic factors, algorithms for approximating the real and complex roots of univariate polynomials, improving the previously known bounds by a factor. In addition, we presented new zero-bounds for the roots of polynomial systems that lead to novel effective bounds for polynomial optimization problems. From the application point of view, we considered problems in non-linear computational geometry and game theory. We extended the limits of the state-of-the-art in non-linear computational geometry by proposing the first complete and exact algorithm for computing the Voronoi diagram of ellipses in the plane. In the game-theoretic field we presented exact bounds for the optimal strategies of matrix games based on zero-bounds. Finally, we developed an open source, complete, robust and efficient software package for isolating and refining the real roots of univariate polynomials able to compute the roots of univariate polynomials having degree 1 000 and coefficients of 10 000 bits in about 30 seconds. Currently, the fellow of the project has obtained a permanent researcher position at Inria, working in the research team POLSYS.
Data: CORDIS, © European Union
Project objective
The project Algebraic Algorithms and Applications (A3) is an interdisciplinary and multidisciplinary project, with strong international synergy.It consists of four work packagesThe first (Algebraic Algorithms) focuses on fundamentalproblems of computational (real) algebraic geometry: effective zerobounds, that is estimations for the minimum distance of the roots of apolynomial system from zero, algorithms for solving polynomials andpolynomial systems, derivation of non-asymptotic bounds for basicalgorithms of real algebraic geometry and application of polynomialsystem solving techniques in optimization.We propose a novel approach thatexploits structure and symmetry, combinatorial properties of highdimensional polytopes and tools from mathematical physics.Despite the great potential of the modern tools from algebraicalgorithms, their use requires a combined effort to transfer thistechnology to specific problems. In the second package (Stochastic Games)we aim to derive optimal algorithms for computingthe values of stochastic games, using techniques from real algebraicgeometry, and to introduce a whole new arsenal of algebraic tools tocomputational game theory.The third work package (Non-linear Computational Geometry), wefocus on exact computations with implicitly defined plane andspace curves. These are challenging problems that commonly arise ingeometric modeling and computer aided design,but they also have applications in polynomial optimization.The final work package (Efficient Implementations) describes our plansfor complete, robust and efficient implementations of algebraicalgorithms.
Original text from CORDIS.
Participants
- INSTITUT NATIONAL DE RECHERCHE EN INFORMATIQUE ET AUTOMATIQUE · Le Chesnay CedexCoordinatorFrance
Links
Data: CORDIS, © European Union