Algebraic Algorithms

Polynomial system solving, sparse/toric elimination theory, structured matrices. Resultants reduce the problem of solving a nonlinear 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.

Resultant formulae.
Optimal sparse resultant matrices for unmixed and certain
classes of mixed multihomogeneous polynomial systems, by means of complexes.
(cf. arXiv:0904.4064).
MAPLE software MHRES constructs these matrices.
An efficient representation of complexes is implemented and
used to output Sylvester, Bezouttype or even hybrid resultant matrices free of extraneous factors.
Macaulaytype 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 and Benchmarking.
In
Mathemagix, we developed
module Realroot, solvers for univariate polynomials (e.g. continued
fractions), for systems of polynomials (subdivision methods);
intervalNewton method.
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 stateoftheart blackbox univariate real solvers (isolating real roots over the integers). To the best of our knowledge, this is the largest number of tests for univariate real solving up to date.
Geometric Algorithms

Nonlinear computational geometry and geometric design.
Voronoi diagrams of circles and ellipses
(IMA nugget), using the incremental algorithm of
CGAL.
Arrangements of curved objects
(talk).
Computeraided Geometric design on modeler "Axel"
(video of A.Mantzaflaris' talk).

Implicitization of parametric hypersurfaces:
Prediction of the implicit support by projecting the Newton polytope of the
sparse resultant, and computation of a matrix kernel for exploiting sparseness.
Approximate implicitization by interpolation and numerical linear algebra
(webpage).

Convex geometry in general dimension.
Convex hull and symbolic perturbation, mixed volume
(software).
Regular fine mixed subdivisions of Minkowski sums,
regular triangulations, secondary polytopes, resultant polytopes
(software).
Pictured is an illustration of Cayley's trick.

Approximate geometric algorithms in high dimensions.
kdGeRaf:
randomized kdtrees for approximate nearestneighbors (ANN)
in very high dimensions.
Dimensionality reduction by a weak version of the JL lemma,
and new complexity results for ANN
[SoCG 2015].
Clustering for big data: We improve kmeans by reverse assignment and
combine it with Product Quantization to cluster 100 million SIFT images
in seconds [ICCV 2015].
Minkowski decomposition, pictured
(webpage):
optimal algorithms with a fixedsize summand, approximation of general (NPhard) problem.

Python projects and CGALPython bindings, including visibility tools:
webpage.
The goal is to provide a userfriendly interface, especially for educational purposes,
as well as visibility tools for algorithms and objects from
CGAL, and
to develop geometric algorithms in Python.
Applications

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.
We combine nonlinear least square minimization and a genetic algorithm.
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.
TbBTool is the software.

Robot kinematics.
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 embdedding.
Graph embedding in Euclidean spaces, distance graphs, and rigidity theory.
Distributed routing in graphs, and applications to
sensor networks.

Lakes
is a program for the prediction of protein binding sites.
It analyzes the solvent and its contacts with proteins
(obtained by Xray 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: Dr Thanassis Tartas.
Picture: black is the protein, colored are the Oxygen atoms of the clusters, red being the largest cluster.