Chordal Structure and Polynomial Systems
summary
Proposes a chordal elimination algorithm that preserves sparsity by eliminating variables along a perfect elimination order, computes elimination ideals for maximal cliques, and then glues projections via the clique tree. Claims complexity linear in number of variables and exponential in treewidth, with memory bounded by maximum clique size. Implements a prototype in Sage + Singular (and an F2 poly solver), solves an AES-like instance of 288 variables / 528 equations, and outperforms Gröbner methods as instances grow under zero-dimensionality or a simplicial leading-term condition.
AI-written summary · about
chapters (10)
- 0:00Introduction to graph mapping
- 1:26Graph theory foundations
- 3:28Chordal graphs and treewidth
- 5:55Complexity and algorithms
- 8:35Polynomial systems challenges
- 10:48Chordal elimination algorithm
- 14:10Theoretical constraints
- 17:32Clique-based solving
- 21:47Experimental results
- 25:53Conclusion and Q&A
related talks
01h 03mQuery Optimization and Evaluation 3: Variable Elimination and Tensor Decomposition
01h 08mAlgebraic Structures in Logic and Query Evaluation 4
18mParikh's Theorem Made Symbolic
52mVariety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory
28mAlgorithmic Aspects of Semiring Provenance for Stratified Datalog
01h 05mAlgebraic Structures in Logic and Query Evaluation 2
01h 24mIntroduction to Constraint Logic Programming
19mRamsey Quantifiers in Linear Arithmetics