next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
Chordal :: Chordal

Chordal -- exploiting chordal structure in polynomial ideals

Description

This package provides several specialized routines for structured polynomial ideals. The sparsity structure of a polynomial set can be described with a graph. By exploiting some suitable "chordal completion" of this graph, it is possible to develop more efficient algorithms for several problems in computational algebraic geometry.

See installation and configuration for instructions on how to install this package.

The examples below illustrate how to use this package to get the following properties of a structured ideal: compute elimination ideals, count the number of zeros, determine the dimension, decompose the variety.

graphical structure of an ideal
We can abstract the sparsity structure of a polynomial system in a graph. By exploiting the chordal completions of this graph more efficient algorithms can be developed.
i1 : R = QQ[a,b,c,d];
i2 : I = ideal {a^2-1, a^2+a*b+1, a^3+c^2, b*d + d, c^3+c*d};

o2 : Ideal of R
i3 : G = constraintGraph I

o3 = Graph{a => {b, c}}
           b => {a, d}
           c => {a, d}
           d => {b, c}

o3 : Graph
i4 : Gc = chordalGraph G

o4 = ChordalGraph{a => {b, c} }
                  b => {c, d}
                  c => {d}
                  d => {}

o4 : ChordalGraph
chordal elimination
Consider the 3-chromatic ideal of the cycle graph. Its elimination ideals have have a simple generating set.
i5 : I = chromaticIdeal(QQ, cycleGraph 10, 3);

o5 : Ideal of QQ[a, b, c, d, e, f, g, h, i, j]
i6 : N = chordalNet I;
i7 : chordalElim N;
i8 : N

                                     2    2   2          2
o8 = ChordalNet{ a => {{a*b - a*j + b  - j , a  + a*j + j }} }
                        2          2
                 b => {b  + b*c + c }
                        2          2
                 c => {c  + c*d + d }
                        2          2
                 d => {d  + d*e + e }
                        2          2
                 e => {e  + e*f + f }
                        2          2
                 f => {f  + f*g + g }
                        2          2
                 g => {g  + g*h + h }
                        2                2
                 h => {h  + h*i - i*j - j }
                        2          2
                 i => {i  + i*j + j }
                        3
                 j => {j  - 1}

o8 : ChordalNet
On the other hand, its Groebner basis is complicated.
i9 : sum for f in gbList I list #terms f

o9 = 253
chordal networks
Consider the ideal of adjacent minors of a 2xn matrix. This ideal decomposes into Fn components, where Fn is the Fibonacci number. These (exponentially many) components can be represented compactly with a chordal network.
i10 : I = adjacentMinorsIdeal(QQ,2,10);

o10 : Ideal of QQ[a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t]
i11 : N = chordalNet I;
i12 : chordalTria N;
i13 : N

o13 = ChordalNet{ a => { , a*d - b*c}                     }
                  b => { , b,  }
                  c => {c,  ,  , c*f - d*e}
                  d => {d, d,  ,  }
                  e => { ,  , e*h - f*g, e,  , e*h - f*g}
                  f => { , f,  , f,  ,  }
                  g => {g,  ,  , g*j - h*i,  , g*j - h*i}
                  h => {h, h,  ,  ,  ,  }
                  i => { ,  , i*l - j*k, i,  , i*l - j*k}
                  j => { , j,  , j,  ,  }
                  k => {k,  ,  , k*n - l*m,  , k*n - l*m}
                  l => {l, l,  ,  ,  ,  }
                  m => { ,  , m*p - n*o, m,  , m*p - n*o}
                  n => { , n,  , n,  ,  }
                  o => {o,  ,  , o*r - p*q,  , o*r - p*q}
                  p => {p, p,  ,  ,  ,  }
                  q => { ,  , q*t - r*s, q,  , q*t - r*s}
                  r => { , r,  , r,  ,  }
                  s => {s,  ,  ,  }
                  t => {t,  ,  }

o13 : ChordalNet
Several properties of an ideal can be computed efficiently given a chordal representation; for instance, its dimention.
i14 : dim N

o14 = 11
We can also extract the top dimensional part, and count the number of components.
i15 : topComponents N
i16 : codimCount N

         9
o16 = 55t

o16 : ZZ[t]

For further example see

Overview of methods

Graphical structure of a polynomial ideal: Elimination routines: Methods for triangular chordal networks:

References

  • D. Cifuentes, P.A. Parrilo (2016), "Exploiting chordal structure in polynomial ideals: a Groebner basis approach", in "SIAM J. Discrete Math", 30(3):1534-–1570
  • D. Cifuentes, P.A. Parrilo (2017), "Chordal networks of polynomial ideals", in "SIAM J. Appl. Algebra Geometry", 1(1):73-–170

Authors

Version

This documentation describes version 0.1 of Chordal.

Source code

The source code from which this documentation is derived is in the file Chordal.m2. The auxiliary files accompanying it are in the directory Chordal/.

Exports