Polynomial system solving, sparse/toric elimination theory, structured matrices. Resultants reduce the problem of solving a non-linear system of equations to linear algebra. Sparse elimination exploits the structure of polynomials. Newton polytopes model the sparseness of polynomials and provide the bridge between algebra and combinatorial geometry.
Some related Algebraic software.
Real solving, Real algebraic numbers.
Fast solvers based on Continued Fractions and Sturm sequences,
implemented in C++ (library SYNAPS, now Mathemagix).
MAPLE software SLV for operations on real algebraic numbers (comparison, sign determination), real solving of a polynomial equation and of bivariate systems. The software handles arbitrary inputs, and outputs all real solutions in isolating interval representation.
Optimal sparse resultant matrices for unmixed and certain
classes of mixed multihomogeneous polynomial systems, by means of complexes.
MAPLE software MHRES constructs these matrices.
An efficient representation of complexes is implemented and
used to output Sylvester, Bezout-type or even hybrid resultant matrices free of extraneous factors.
Macaulay-type formulae for sparse resultants of generalized unmixed polynomial systems,
by means of a single lifting function of the input Newton polytopes (cf. article).
Software development in
In module Realroot, solvers for univariate polynomials (e.g. continued
fractions), extensions to systems of polynomials (subdivision methods);
Polytopal computations for algebraic manipulation:
normals, faces, ridges, extreme or interior points,
Minkowski sums and Mixed volumes; connection to polynomial representation
to exploit toric elimination theory (module Polytopix).
Experiments on univariate real solvers: We compared black-box implementations of state-of-the-art algorithms for isolating real roots of univariate polynomials over the integers (implemented in Mathemagix or CGAL), with respect to various aspects such as degree, bitsize or root separation of the input polynomials. To the best of our knowledge, this is the largest number of tests for univariate real solving up to date.
Nonlinear computational geometry and geometric design.
Voronoi diagrams of circles and ellipses
(IMA nugget), using the incremental algorithm of
Relying on exact and certified algebraic operations developed in Synaps / Mathemagix. Arrangements of curved objects
Computer-aided Geometric design on modeler "Axel"
(video of A.Mantzaflaris' talk).
Convex geometry in general dimension.
Convex hull and symbolic perturbation, mixed volume
Regular fine mixed subdivisions of Minkowski sums,
regular triangulations, secondary polytopes, resultant polytopes
Pictured is an illustration of Cayley's trick.
Implicitization of parametric hypersurfaces using enumeration algorithms of regular triangulations.
Prediction of the implicit support and computation of a matrix kernel for exploiting sparseness of the implicit equation.
Approximate implicitization by means of numerical linear algebra. Experimental results on
curves and surfaces (webpage).
Approximate geometric algorithms.
Nearest neighbors and data structures for searching
Minkowski (approximate) decomposition, pictured
Python code for the computation/approximation of the decomposition
of a convex lattice polygon as Minkowski sum of two convex lattice polygons.
Optimal algorithms for fixed-size summands, approximation of general (NP-hard) problem.
Approximation algorithms for visibility.
Python projects and CGAL-Python bindings, including visibility tools: see the project's
The goal is (a) to provide a user-friendly interface, especially for educational purposes,
as well as visibility tools for algorithms and objects from the
CGAL library, and
(b) to develop geometric algorithms in Python (art gallery, kd-trees, etc).
Molecular conformations in Structural bioinformatics.
Enumeration of all possible conformations of (small) molecules/proteins under some geometric constrains.
The problem is formulated in algebraic terms as a system of polynomial equations which is then solved using sparse elimination and matrix methods.
Utilizing data from NMR and RDC, reduces the problem to linear algebra.
Structure of Transmembrane proteins.
Geometric modelling of β-barrels and detection of the transmembrane region of a β-barrel transmembrane protein.
The geometric modelling algorithm combines a non-linear least square minimization method and a genetic algorithm in order to find the characteristics (axis, radius) of a shape with axial symmetry which best models a β-barrel. The transmembrane region is detected by profiling the external residues of the β-barrel along its axis in terms of hydrophobicity and existence of aromatic and charged residues.
TbB-Tool implements these algorithms.
"Lakes" is a program for the prediction of protein binding sites.
It analyzes the solvent and its contacts with proteins
(obtained by X-ray crystallography) and defines clusters of water molecules,
which mark potentially exposed interaction and binding sites
of the protein.
You can download the program here.
Contact person: Dr Thanassis Tartas
(in the photo black is the protein, colored are the Oxygen atoms of the clusters, with red being the largest cluster).
Robust calibration of parallel robots (by applying elimination techniques),
forward kinematics of Stewart/Gough platforms (by exploiting the structure
of the underlying polynomial system),
and design of robotic platforms for medical applications such as physiotherapy.
Graph embedding in Euclidean spaces, rigid graphs and rigidity theory.
Geometric graphs, distributed routing in graphs, and applications to