Computing Circuit Polynomials in the Algebraic Rigidity Matroid
SIAM Journal on Applied Algebra and Geometry · 30.06.2023 · 7 (2) · 345-385
DOI: 10.1137/21m1437986 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Applied Algebra and Geometry, online erschienen am 23.05.2023. Verfasst von Goran Malić und 1 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 55 Literaturangaben. Gefördert von: National Science Foundation.
Abstract (Originalsprache)
We present an algorithm for computing circuit polynomials in the algebraic rigidity matroid [Formula: see text] associated to the Cayley–Menger ideal [Formula: see text] for [Formula: see text] points in 2D. It relies on combinatorial resultants, a new operation on graphs that captures properties of the Sylvester resultant of two polynomials in this ideal. We show that every rigidity circuit has a construction tree from [Formula: see text] graphs based on this operation. Our algorithm performs an algebraic elimination guided by such a construction tree and uses classical resultants, factorization, and ideal membership. To highlight its effectiveness, we implemented the algorithm in Mathematica: it took less than 15 seconds on an example where a Gröbner basis calculation took 5 days and 6 hours. Additional speed-ups are obtained using non-[Formula: see text] generators of the Cayley–Menger ideal and simple variations on our main algorithm.
Förderung
- National Science Foundation
Zitieren
APA
Malić, G., & Streinu, I. (2023). Computing Circuit Polynomials in the Algebraic Rigidity Matroid. SIAM Journal on Applied Algebra and Geometry, 7(2), 345-385. https://doi.org/10.1137/21m1437986
Vancouver
Malić G, Streinu I. Computing Circuit Polynomials in the Algebraic Rigidity Matroid. SIAM Journal on Applied Algebra and Geometry. 2023;7(2):345-385. doi:10.1137/21m1437986
BibTeX
@article{Mali2023,
author = {Malić, Goran and Streinu, Ileana},
title = {Computing Circuit Polynomials in the Algebraic Rigidity Matroid},
journal = {SIAM Journal on Applied Algebra and Geometry},
year = {2023},
volume = {7},
number = {2},
pages = {345--385},
doi = {10.1137/21m1437986}
}
EUVIMED