Document Open Access Logo

Combinatorial Resultants in the Algebraic Rigidity Matroid

Authors Goran Malić , Ileana Streinu

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.52.pdf
  • Filesize: 0.87 MB
  • 16 pages

Document Identifiers

Author Details

Goran Malić
  • Computer Science Department, Smith College, Northampton, MA, USA
Ileana Streinu
  • Computer Science Department, Smith College, Northampton, MA, USA

Funding

Both authors acknowledge funding from the NSF CCF:1703765 grant to Ileana Streinu.

Cite AsGet BibTex

Goran Malić and Ileana Streinu. Combinatorial Resultants in the Algebraic Rigidity Matroid. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.52

Abstract

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.

Subject Classification

ACM Subject Classification
  • General and reference → Performance
  • General and reference → Experimentation
  • Theory of computation → Computational geometry
  • Mathematics of computing → Matroids and greedoids
  • Mathematics of computing → Mathematical software performance
  • Computing methodologies → Combinatorial algorithms
  • Computing methodologies → Algebraic algorithms
Keywords
  • Cayley-Menger ideal
  • rigidity matroid
  • circuit polynomial
  • combinatorial resultant
  • inductive construction
  • Gröbner basis elimination

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Evangelos Bartzos, Ioannis Z. Emiris, Jan Legerský, and Elias Tsigaridas. On the maximal number of real embeddings of minimally rigid graphs in R² , R³ and S². Journal of Symbolic Computation, 102:189-208, 2021. URL: https://doi.org/10.1016/j.jsc.2019.10.015.
  2. Alex R Berg and Tibor Jordán. A proof of Connelly’s conjecture on 3-connected circuits of the rigidity matroid. Journal of Combinatorial Theory, Series B, 88(1):77-97, 2003. URL: https://doi.org/10.1016/S0095-8956(02)00037-0.
  3. Ciprian S. Borcea. Point configurations and Cayley-Menger varieties, 2002. ArXiv math/0207110. URL: http://arxiv.org/abs/math/0207110.
  4. Ciprian S. Borcea and Ileana Streinu. The number of embeddings of minimally rigid graphs. Discrete and Computational Geometry, 31:287-303, February 2004. URL: https://doi.org/10.1007/s00454-003-2902-0.
  5. B. Buchberger. Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems. Aequationes Math., 4:374-383, 1970. URL: https://doi.org/10.1007/BF01844169.
  6. Jose Capco, Matteo Gallet, Georg Grasegger, Christoph Koutschan, Niels Lubbes, and Josef Schicho. Computing the number of realizations of a Laman graph. Electronic notes in Discrete Mathematics, 61:207-213, 2017. URL: https://doi.org/10.1016/j.endm.2017.06.040.
  7. David A. Cox, John Little, and Donal O'Shea. Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer, Cham, fourth edition, 2015. Google Scholar
  8. A. Dress and L. Lovász. On some combinatorial properties of algebraic matroids. Combinatorica, 7(1):39-48, 1987. URL: https://doi.org/10.1007/BF02579199.
  9. I. Emiris and B. Mourrain. Computer algebra methods for studying and computing molecular conformations. Algorithmica, 25:372-402, 1999. URL: https://doi.org/10.1007/PL00008283.
  10. Ioannis Z. Emiris, Elias P. Tsigaridas, and Antonios Varvitsiotis. Mixed Volume and Distance Geometry Techniques for Counting Euclidean Embeddings of Rigid Graphs. In Mucherino, Antonio and Lavor, Carlile and Liberti, Leo and Maculan, Nelson, editor, Distance Geometry. Theory, Methods, and Applications, chapter 2, pages 23-46. Springer, New York, Heidelberg, Dordrecht, London, 2013. URL: https://doi.org/10.1007/978-1-4614-5128-0.
  11. I.M. Gelfand, M. Kapranov, and A. Zelevinsky. Discriminants, Resultants, and Multidimensional Determinants. Modern Birkhäuser Classics. Birkhäuser Boston, 2009. URL: https://doi.org/10.1016/0001-8708(90)90047-Q.
  12. G.Z. Giambelli. Sulle varietá rappresentate coll'annullare determinanti minori contenuti in un determinante simmetrico od emisimmetrico generico di forme. Atti della R. Acc. Sci, di Torino, 44:102-125, 1905/06. Google Scholar
  13. J. Harris and L.W. Tu. On symmetric and skew-symmetric determinantal varieties. Topology, 23:71-84, 1984. URL: https://doi.org/10.1016/0040-9383(84)90026-0.
  14. Lebrecht Henneberg. Die graphische Statik der starren Systeme. B. G. Teubner, 1911. Google Scholar
  15. John E. Hopcroft and Robert Endre Tarjan. Dividing a graph into triconnected components. SIAM J. Comput., 2(3):135-158, 1973. URL: https://doi.org/10.1137/0202012.
  16. T. Józefiak, A. Lascoux, and P. Pragacz. Classes of determinantal varieties associated with symmetric and skew-symmetric matrices. Math. USSR Izvestija, 18:575-586, 1982. URL: https://doi.org/10.1070/im1982v018n03abeh001400.
  17. Gerard Laman. On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics, 4:331-340, 1970. URL: https://doi.org/10.1007/BF01534980.
  18. Audrey Lee-St. John and Ileana Streinu. Pebble game algorithms and sparse graphs. Discrete Mathematics, 308(8):1425-1437, April 2008. URL: https://doi.org/10.1016/j.disc.2007.07.104.
  19. Goran Malić and Ileana Streinu. CayleyMenger - Circuit Polynomials in the Cayley Menger ideal, a GitHub repository. https://github.com/circuitPolys/CayleyMenger, 2020.
  20. Goran Malić and Ileana Streinu. Circuit polynomial for the K_3,3-plus-one circuit, 2021. In preparation. Google Scholar
  21. Goran Malić and Ileana Streinu. Combinatorial resultants in the algebraic rigidity matroid, 2021. ArXiv/2103.08432 [Math.CO]. URL: http://arxiv.org/abs/2103.08432.
  22. James Oxley. Matroid theory, volume 21 of Oxford Graduate Texts in Mathematics. Oxford University Press, Oxford, second edition, 2011. Google Scholar
  23. Zvi Rosen. Algebraic Matroids in Applications. PhD thesis, University of California, Berkeley, 2015. URL: https://digitalassets.lib.berkeley.edu/etd/ucb/text/Rosen_berkeley_0028E_15261.pdf.
  24. Zvi Rosen. algebraic-matroids, a GitHub repository. https://github.com/zvihr/algebraic-matroids, 2017.
  25. Zvi Rosen, Jessica Sidman, and Louis Theran. Algebraic matroids in action. The American Mathematical Monthly, 127(3):199-216, February 2020. URL: https://doi.org/10.1080/00029890.2020.1689781.
  26. Meera Sitharam and Heping Gao. Characterizing graphs with convex and connected Cayley configuration spaces. Discrete and Computational Geometry, 43(3):594-625, 2010. URL: https://doi.org/10.1007/s00454-009-9160-8.
  27. William T. Tutte. Connectivity in graphs. Toronto University Press, Toronto, 1966. Google Scholar
  28. D. Walter and M.L. Husty. On a nine-bar linkage, its possible configurations and conditions for flexibility. In Merlet J.-P. and M. Dahan, editors, Proceedings of IFFToMM 2007, Besançon, France, 2007. URL: http://geometrie.uibk.ac.at/cms/datastore/husty/A681.pdf.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact