Thematic Einstein Semester on

Geometric and Topological Structure of Materials

Summer Semester 2021

Speaker


Ileana Streinu   (Smith College)


Title


Rigidity, Circuits and Resultants: a combinatorial elimination approach to localization


Abstract


Localization problems arise in many areas of materials science, e.g. in molecular structure determination from NMR or X-ray crystallographic data. The goal is to find the positions of n points, given a subset of the pairwise distances between them. The Single unknown distance problem asks for the possible values of only one of the unknown distances. Such problems can be easily formulated algebraically and could, in principle, be addressed with variations of the doubly-exponential time Groebner Basis algorithm. But of course this is not feasible in practice, even for small cases.

Known results from rigidity theory, together with techniques involving algebraic matroids and a theorem of Dress and Lovász help reduce the single-distance problem to the computation of a so-called circuit polynomial in the Cayley-Menger ideal.

By taking into account combinatorial rigidity properties of the underlying graphs, we develop a new algorithm that significantly outperforms Groebner Bases for computing such polynomials. We introduce a new operation on graphs called a combinatorial resultant, which captures properties of the Sylvester resultant of two polynomials in the algebraic rigidity matroid. We show that every rigidity-circuit graph has a construction tree with this operation marking the tree's interior nodes and with K4 graphs at the leaves. Our algorithm performs a resultant-based algebraic elimination guided by the construction tree. Along the way, a wealth of intriguing open questions (combinatorial, algebraic and computational) emerged.

To demonstrate the effectiveness of our new method, we implemented it in Mathematica: it took less than 15 seconds on an example where a Groebner Basis calculation took 5 days and 6 hrs.

This is joint work with Goran Malic.



Contact


tes-summer2021@math.tu-berlin.de