Computing Circuit Polynomials in the Algebraic Rigidity Matroid

DOI10.1137/21M1437986MaRDI QIDQ6161559zbMATH OpenOpenAlexFDO

Authors Goran Malić, Ileana Streinu

Publication date 27 June 2023

Published in SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2304.12435

zbMATH Keywords

Cayley-Menger idealcircuit polynomialcombinatorial resultantGröbner basis eliminationinductive constructionrigidity matroid

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Solving polynomial systems; resultants (13P15) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25) Networks and circuits as models of computation; circuit complexity (68Q06) Symbolic computation and algebraic computation (68W30)

Abstract: We present an algorithm for computing circuit polynomials in the algebraic rigidity matroid $mathcalA(ext{CM}_n)$ associated to the Cayley-Menger ideal CM${}_n$ for $n$ 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 K4 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"obner Basis calculation took 5 days and 6 hrs. Additional speed-ups are obtained using non-$K_4$ generators of the Cayley-Menger ideal and simple variations on our main algorithm.

Recommendations

• Algorithms for the d-Dimensional Rigidity Matroid of Sparse Graphs
• Complexity of linear circuits and geometry
• Efficient algorithms for the d-dimensional rigidity matroid of sparse graphs
• Software engineering and complexity in effective algebraic geometry
• Subspace arrangements, graph rigidity and derandomization through submodular optimization

Cites work

• A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid.
• Absolute irreducibility of polynomials via Newton polytopes
• Algebraic matroids and Frobenius flocks
• Algebraic matroids in action
• Apolarity and canonical forms for homogeneous polynomials
• Characterizing graphs with convex and connected Cayley configuration spaces
• CLASSES OF DETERMINANTAL VARIETIES ASSOCIATED WITH SYMMETRIC AND SKEW-SYMMETRIC MATRICES
• Construction of the Lindström valuation of an algebraic extension
• Distance Geometry
• Dividing a Graph into Triconnected Components
• Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems
• scientific article; zbMATH DE number 1703931 (Why is no real title available?)
• scientific article; zbMATH DE number 4214184 (Why is no real title available?)
• scientific article; zbMATH DE number 501471 (Why is no real title available?)
• scientific article; zbMATH DE number 1069614 (Why is no real title available?)
• scientific article; zbMATH DE number 952952 (Why is no real title available?)
• scientific article; zbMATH DE number 790015 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• scientific article; zbMATH DE number 2188749 (Why is no real title available?)
• scientific article; zbMATH DE number 3222940 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• scientific article; zbMATH DE number 3305793 (Why is no real title available?)
• scientific article; zbMATH DE number 3331438 (Why is no real title available?)
• scientific article; zbMATH DE number 3351601 (Why is no real title available?)
• Ideals, Varieties, and Algorithms
• Newton polytopes of the classical resultant and discriminant
• Numerically solving polynomial systems with Bertini
• On graphs and rigidity of plane skeletal structures
• On some combinatorial properties of algebraic matroids
• On symmetric and skew-symmetric determinantal varieties
• On the maximal number of real embeddings of minimally rigid graphs in \(\mathbb{R}^2,\mathbb{R}^3\) and \(S^2\)
• Pebble game algorithms and sparse graphs
• Slider-pinning rigidity: a Maxwell-Laman-type theorem
• The m-Bézout bound and distance geometry
• The membership problem for unmixed polynomial ideals is solvable in single exponential time
• The number of embeddings of minimally rigid graphs
• The number of realizations of a Laman graph
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• The Space Complexity of Elimination Theory: Upper Bounds
• What can be computed in algebraic geometry?

Cited in

(2)

• Enumerating combinatorial resultant trees
• Globally rigid circuits of the direction-length rigidity matroid

This page was built for publication: Computing Circuit Polynomials in the Algebraic Rigidity Matroid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6161559)