Combinatorial Resultants in the Algebraic Rigidity Matroid
| Autor: | Malić, Goran, Streinu, Ileana |
|---|---|
| Jazyk: | angličtina |
| Předmět: |
General and reference → Performance
rigidity matroid Computing methodologies → Combinatorial algorithms circuit polynomial Theory of computation → Computational geometry inductive construction General and reference → Experimentation 16. Peace & justice combinatorial resultant Mathematics of computing → Mathematical software performance ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Mathematics of computing → Matroids and greedoids Computing methodologies → Algebraic algorithms Cayley-Menger ideal Gröbner basis elimination |
| Popis: | Motivated by a rigidity-theoretic perspective on the Localization Problem in 2D, we develop an algorithm for computing circuit polynomials in the algebraic rigidity matroid CM_n associated to the Cayley-Menger ideal for n points in 2D. We introduce combinatorial resultants, a new operation on graphs that captures properties of the Sylvester resultant of two polynomials in the algebraic rigidity matroid. We show that every rigidity circuit has a construction tree from K₄ graphs based on this operation. Our algorithm performs an algebraic elimination guided by the construction tree, and uses classical resultants, factorization and ideal membership. To demonstrate its effectiveness, we implemented our algorithm in Mathematica: it took less than 15 seconds on an example where a Gröbner Basis calculation took 5 days and 6 hrs. LIPIcs, Vol. 189, 37th International Symposium on Computational Geometry (SoCG 2021), pages 52:1-52:16 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|