Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach
Chordal structure and bounded treewidth allow for efficient computation in numerical linear algebra, graphical models, constraint satisfaction, and many other areas. In this paper, we begin the study of how to exploit chordal structure in computational algebraic geometry---in particular, for solving...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2017
|
| Online Access: | http://hdl.handle.net/1721.1/107708 https://orcid.org/0000-0003-0222-3761 https://orcid.org/0000-0003-1132-8477 |
| _version_ | 1826208716186189824 |
|---|---|
| author | Cifuentes, Diego Fernando Parrilo, Pablo A |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Cifuentes, Diego Fernando Parrilo, Pablo A |
| author_sort | Cifuentes, Diego Fernando |
| collection | MIT |
| description | Chordal structure and bounded treewidth allow for efficient computation in numerical linear algebra, graphical models, constraint satisfaction, and many other areas. In this paper, we begin the study of how to exploit chordal structure in computational algebraic geometry---in particular, for solving polynomial systems. The structure of a system of polynomial equations can be described in terms of a graph. By carefully exploiting the properties of this graph (in particular, its chordal completions), more efficient algorithms can be developed. To this end, we develop a new technique, which we refer to as chordal elimination, that relies on elimination theory and Gröbner bases. By maintaining graph structure throughout the process, chordal elimination can outperform standard Gröbner bases algorithms in many cases. The reason is because all computations are done on “smaller” rings of size equal to the treewidth of the graph (instead of the total number of variables). In particular, for a restricted class of ideals, the computational complexity is linear in the number of variables. Chordal structure arises in many relevant applications. We demonstrate the suitability of our methods in examples from graph colorings, cryptography, sensor localization, and differential equations. |
| first_indexed | 2024-09-23T14:10:21Z |
| format | Article |
| id | mit-1721.1/107708 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:10:21Z |
| publishDate | 2017 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/1077082022-10-01T19:37:06Z Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach Cifuentes, Diego Fernando Parrilo, Pablo A Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Cifuentes, Diego Fernando Parrilo, Pablo A Chordal structure and bounded treewidth allow for efficient computation in numerical linear algebra, graphical models, constraint satisfaction, and many other areas. In this paper, we begin the study of how to exploit chordal structure in computational algebraic geometry---in particular, for solving polynomial systems. The structure of a system of polynomial equations can be described in terms of a graph. By carefully exploiting the properties of this graph (in particular, its chordal completions), more efficient algorithms can be developed. To this end, we develop a new technique, which we refer to as chordal elimination, that relies on elimination theory and Gröbner bases. By maintaining graph structure throughout the process, chordal elimination can outperform standard Gröbner bases algorithms in many cases. The reason is because all computations are done on “smaller” rings of size equal to the treewidth of the graph (instead of the total number of variables). In particular, for a restricted class of ideals, the computational complexity is linear in the number of variables. Chordal structure arises in many relevant applications. We demonstrate the suitability of our methods in examples from graph colorings, cryptography, sensor localization, and differential equations. United States. Air Force Office of Scientific Research (grant FA9550-11-1-0305) 2017-03-27T13:53:33Z 2017-03-27T13:53:33Z 2016-08 2016-05 Article http://purl.org/eprint/type/JournalArticle 0895-4801 1095-7146 http://hdl.handle.net/1721.1/107708 Cifuentes, Diego, and Pablo A. Parrilo. "Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach." SIAM Journal on Discrete Mathematics 30.3 (2016): 1534-570. https://orcid.org/0000-0003-0222-3761 https://orcid.org/0000-0003-1132-8477 en_US http://dx.doi.org/10.1137/151002666 SIAM Journal on Discrete Mathematics 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 and Applied Mathematics SIAM |
| spellingShingle | Cifuentes, Diego Fernando Parrilo, Pablo A Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach |
| title | Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach |
| title_full | Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach |
| title_fullStr | Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach |
| title_full_unstemmed | Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach |
| title_short | Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach |
| title_sort | exploiting chordal structure in polynomial ideals a grobner bases approach |
| url | http://hdl.handle.net/1721.1/107708 https://orcid.org/0000-0003-0222-3761 https://orcid.org/0000-0003-1132-8477 |
| work_keys_str_mv | AT cifuentesdiegofernando exploitingchordalstructureinpolynomialidealsagrobnerbasesapproach AT parrilopabloa exploitingchordalstructureinpolynomialidealsagrobnerbasesapproach |