Chordal Networks of Polynomial Ideals
We introduce a novel representation of structured polynomial ideals, which we refer to as chordal networks. The sparsity structure of a polynomial system is often described by a graph that captures the interactions among the variables. Chordal networks provide a computationally convenient decomposit...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Society for Industrial & Applied Mathematics (SIAM)
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121461 |
| _version_ | 1826210315092623360 |
|---|---|
| author | Cifuentes, Diego Fernando Parrilo, Pablo A. |
| author2 | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems |
| author_facet | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Cifuentes, Diego Fernando Parrilo, Pablo A. |
| author_sort | Cifuentes, Diego Fernando |
| collection | MIT |
| description | We introduce a novel representation of structured polynomial ideals, which we refer to as chordal networks. The sparsity structure of a polynomial system is often described by a graph that captures the interactions among the variables. Chordal networks provide a computationally convenient decomposition into simpler (triangular) polynomial sets, while preserving the underlying graphical structure. We show that many interesting families of polynomial ideals admit compact chordal network representations (of size linear in the number of variables), even though the number of components is exponentially large. Chordal networks can be computed for arbitrary polynomial systems using a refinement of the chordal elimination algorithm from [Cifuentes-Parrilo-2016]. Furthermore, they can be effectively used to obtain several properties of the variety, such as its dimension, cardinality, and equidimensional components, as well as an efficient probabilistic test for radical ideal membership. We apply our methods to examples from algebraic statistics and vector addition systems; for these instances, algorithms based on chordal networks outperform existing techniques by orders of magnitude. Key words. chordal graphs, structured polynomials, chordal networks, triangular sets |
| first_indexed | 2024-09-23T14:47:52Z |
| format | Article |
| id | mit-1721.1/121461 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:47:52Z |
| publishDate | 2019 |
| publisher | Society for Industrial & Applied Mathematics (SIAM) |
| record_format | dspace |
| spelling | mit-1721.1/1214612022-09-29T10:37:50Z Chordal Networks of Polynomial Ideals Cifuentes, Diego Fernando Parrilo, Pablo A. Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Department of Mathematics Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science We introduce a novel representation of structured polynomial ideals, which we refer to as chordal networks. The sparsity structure of a polynomial system is often described by a graph that captures the interactions among the variables. Chordal networks provide a computationally convenient decomposition into simpler (triangular) polynomial sets, while preserving the underlying graphical structure. We show that many interesting families of polynomial ideals admit compact chordal network representations (of size linear in the number of variables), even though the number of components is exponentially large. Chordal networks can be computed for arbitrary polynomial systems using a refinement of the chordal elimination algorithm from [Cifuentes-Parrilo-2016]. Furthermore, they can be effectively used to obtain several properties of the variety, such as its dimension, cardinality, and equidimensional components, as well as an efficient probabilistic test for radical ideal membership. We apply our methods to examples from algebraic statistics and vector addition systems; for these instances, algorithms based on chordal networks outperform existing techniques by orders of magnitude. Key words. chordal graphs, structured polynomials, chordal networks, triangular sets United States. Air Force. Office of Scientific Research (Grant FA9550-11-1-0305) 2019-07-01T13:47:50Z 2019-07-01T13:47:50Z 2017-01 2017-04-11 2019-06-28T18:36:56Z Article http://purl.org/eprint/type/JournalArticle 2470-6566 https://hdl.handle.net/1721.1/121461 Cifuentes, Diego, and Pablo A. Parrilo. “Chordal Networks of Polynomial Ideals.” SIAM Journal on Applied Algebra and Geometry 1, no. 1 (January 2017): 73–110. © 2017 Society for Industrial and Applied Mathematics en 10.1137/16m106995x Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial & Applied Mathematics (SIAM) SIAM |
| spellingShingle | Cifuentes, Diego Fernando Parrilo, Pablo A. Chordal Networks of Polynomial Ideals |
| title | Chordal Networks of Polynomial Ideals |
| title_full | Chordal Networks of Polynomial Ideals |
| title_fullStr | Chordal Networks of Polynomial Ideals |
| title_full_unstemmed | Chordal Networks of Polynomial Ideals |
| title_short | Chordal Networks of Polynomial Ideals |
| title_sort | chordal networks of polynomial ideals |
| url | https://hdl.handle.net/1721.1/121461 |
| work_keys_str_mv | AT cifuentesdiegofernando chordalnetworksofpolynomialideals AT parrilopabloa chordalnetworksofpolynomialideals |