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..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 F_n components, where F_n 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..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 dimension.

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

chordal networks examples -- a new representation of polynomial ideals

Overview of methods

Graphical structure of a polynomial ideal:

constraintGraph -- constraint graph of a polynomial set
chordalGraph -- chordal completion of a graph
chordalNet -- constructs a chordal network from a polynomial set

Elimination routines:

chordalElim -- performs elimination on the chordal network
chordalTria -- makes a chordal network triangular

Methods for triangular chordal networks:

rootCount -- counts the number of roots of a chordal network
dim(ChordalNet) -- dimension of a chordal network
codim(ChordalNet) -- dimension of a chordal network
codimCount -- codimension counts of the chains of a chordal network
topComponents(ChordalNet) -- top dimension of a chordal network
RingElement % ChordalNet -- ideal membership test
nextChain -- iterates over the chains of a chordal network
components(ChordalNet) -- components of a chordal network

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.2 of Chordal.

Citation

If you have used this package in your research, please cite it as follows:

@misc{ChordalSource,
  title = {{Chordal: routines that exploit chordal structure. Version~0.2}},
  author = {Diego Cifuentes and Pablo A. Parrilo},
  howpublished = {A \emph{Macaulay2} package available at
    \url{https://github.com/Macaulay2/M2/tree/master/M2/Macaulay2/packages}}
}

Exports

Types
- ChordalGraph -- a chordal graph
- ChordalNet -- a chordal network
- ChordalNetChain -- a chain of a chordal network
- ChordalNetNode -- a node of a chordal network
- ChordalNetRank -- a rank of a chordal network
- ElimTree -- the elimination tree of a chordal graph
Functions and commands
- adjacentMinorsIdeal -- ideal of adjacent minors
- chordalElim -- performs elimination on the chordal network
- chordalGraph -- chordal completion of a graph
- structure -- see ChordalNet -- a chordal network
- chordalNet -- constructs a chordal network from a polynomial set
- chordalTria -- makes a chordal network triangular
- chromaticIdeal -- chromatic ideal of a graph
- codimCount -- codimension counts of the chains of a chordal network
- constraintGraph -- constraint graph of a polynomial set
- displayNet -- displays a chordal network using Graphivz
- elimTree -- elimination tree of a chordal graph
- isTriangular -- whether a chordal network is triangular
- label (missing documentation)
- nextChain -- iterates over the chains of a chordal network
- nextOrderedPartition -- iterates over ordered partitions of a number
- nodes -- list of nodes of a chordal network
- reduceDimension -- removes arcs of a chordal network of small dimension
- reduceNet -- reduces a chordal network
- rootCount -- counts the number of roots of a chordal network
- setDefaultConfiguration -- default configuration of a package
- subsetsProductsIdeal -- ideal of subset products
- suggestVariableOrder -- suggests a good variable ordering
- toLex -- change monomial order to lexicographic
- treewidth -- treewidth of a graph
Methods
- chordalElim(ChordalNet) -- see chordalElim -- performs elimination on the chordal network
- chromaticNumber(ChordalGraph) -- see ChordalGraph -- a chordal graph
- cliqueNumber(ChordalGraph) -- see ChordalGraph -- a chordal graph
- inducedSubgraph(ChordalGraph) -- see ChordalGraph -- a chordal graph
- isChordal(ChordalGraph) -- see ChordalGraph -- a chordal graph
- isPerfect(ChordalGraph) -- see ChordalGraph -- a chordal graph
- net(ChordalGraph) -- see ChordalGraph -- a chordal graph
- chordalGraph(Digraph) -- see chordalGraph -- chordal completion of a graph
- chordalGraph(Graph) -- see chordalGraph -- chordal completion of a graph
- chordalGraph(Graph,List) -- see chordalGraph -- chordal completion of a graph
- net(ChordalNet) -- see ChordalNet -- a chordal network
- ring(ChordalNet) -- see ChordalNet -- a chordal network
- chordalNet(Ideal) -- see chordalNet -- constructs a chordal network from a polynomial set
- chordalNet(Ideal,List) -- see chordalNet -- constructs a chordal network from a polynomial set
- chordalNet(Ideal,String) -- see chordalNet -- constructs a chordal network from a polynomial set
- chordalNet(HashTable,HashTable,ElimTree,Digraph) -- construct chordal network from a digraph
- codim(ChordalNetChain) -- see ChordalNetChain -- a chain of a chordal network
- dim(ChordalNetChain) -- see ChordalNetChain -- a chain of a chordal network
- triaSystem(ChordalNet,ChordalNetChain) -- see ChordalNetChain -- a chain of a chordal network
- children(ChordalNetNode) -- see ChordalNetNode -- a node of a chordal network
- generators(ChordalNetNode) -- see ChordalNetNode -- a node of a chordal network
- ineqs(ChordalNetNode) -- see ChordalNetNode -- a node of a chordal network
- label(ChordalNetNode) -- see ChordalNetNode -- a node of a chordal network
- net(ChordalNetNode) -- see ChordalNetNode -- a node of a chordal network
- parents(ChordalNetNode) -- see ChordalNetNode -- a node of a chordal network
- rank(ChordalNetNode) -- see ChordalNetNode -- a node of a chordal network
- net(ChordalNetRank) -- see ChordalNetRank -- a rank of a chordal network
- chordalTria(ChordalNet) -- see chordalTria -- makes a chordal network triangular
- codimCount(ChordalNet) -- see codimCount -- codimension counts of the chains of a chordal network
- components(ChordalNet) -- see components(ChordalNet,ZZ) -- components of a chordal network
- components(ChordalNet,ZZ) -- components of a chordal network
- constraintGraph(Ideal) -- see constraintGraph -- constraint graph of a polynomial set
- constraintGraph(Ring,List) -- see constraintGraph -- constraint graph of a polynomial set
- digraph(ChordalNet) -- digraph associated to a chordal network
- codim(ChordalNet) -- see dim(ChordalNet) -- dimension of a chordal network
- dim(ChordalNet) -- dimension of a chordal network
- displayGraph(ElimTree) -- see displayGraph(String,String,ElimTree) -- displays an elimination tree using Graphviz
- displayGraph(String,String,ElimTree) -- displays an elimination tree using Graphviz
- displayNet(ChordalNet) -- see displayNet -- displays a chordal network using Graphivz
- displayNet(Function,ChordalNet) -- see displayNet -- displays a chordal network using Graphivz
- displayNet(String,String,Function,ChordalNet) -- see displayNet -- displays a chordal network using Graphivz
- chordalGraph(ElimTree) -- see ElimTree -- the elimination tree of a chordal graph
- elimTree(ChordalNet) -- see ElimTree -- the elimination tree of a chordal graph
- net(ElimTree) -- see ElimTree -- the elimination tree of a chordal graph
- elimTree(ChordalGraph) -- see elimTree -- elimination tree of a chordal graph
- elimTree(List,HashTable,HashTable) (missing documentation)
- isPrimeSimple(ChordalNet) -- simple primality test of a chordal network
- isTriangular(ChordalNet) -- see isTriangular -- whether a chordal network is triangular
- leaves(ElimTree) -- leaves of an elimination tree
- nextChain(ChordalNet) -- see nextChain -- iterates over the chains of a chordal network
- nextChain(ChordalNetChain,ChordalNet) -- see nextChain -- iterates over the chains of a chordal network
- nextChain(ChordalNetChain,Sequence,ZZ,ChordalNet) -- see nextChain -- iterates over the chains of a chordal network
- nextChain(ZZ,ChordalNet) -- see nextChain -- iterates over the chains of a chordal network
- nextOrderedPartition(List,ZZ,List) -- see nextOrderedPartition -- iterates over ordered partitions of a number
- nextOrderedPartition(ZZ,List) -- see nextOrderedPartition -- iterates over ordered partitions of a number
- nodes(ChordalNet) -- see nodes -- list of nodes of a chordal network
- nodes(ChordalNet,RingElement) -- see nodes -- list of nodes of a chordal network
- reduceNet(ChordalNet) -- see reduceNet -- reduces a chordal network
- pseudoRemainder(RingElement,ChordalNet) -- see RingElement % ChordalNet -- ideal membership test
- RingElement % ChordalNet -- ideal membership test
- RingMap ChordalNet -- apply ring map to a chordal network
- RingMap ElimTree -- see RingMap ChordalNet -- apply ring map to a chordal network
- rootCount(ChordalNet) -- see rootCount -- counts the number of roots of a chordal network
- setDefaultConfiguration(Package,String,String) -- see setDefaultConfiguration -- default configuration of a package
- setDefaultConfiguration(String,String,String) -- see setDefaultConfiguration -- default configuration of a package
- size(ChordalNet) -- size of a chordal network
- suggestVariableOrder(Ideal) -- see suggestVariableOrder -- suggests a good variable ordering
- treewidth(ChordalGraph) -- see treewidth -- treewidth of a graph
- treewidth(ElimTree) -- see treewidth -- treewidth of a graph
- writeDotFile(String,ElimTree) -- see writeDotFile(String,Function,ChordalNet) -- writes a chordal network to a dot file
- writeDotFile(String,Function,ChordalNet) -- writes a chordal network to a dot file
Symbols
- cliques -- see ElimTree -- the elimination tree of a chordal graph
- GetTable -- get dynamic programming table

For the programmer

The object Chordal is a package, defined in Chordal.m2, with auxiliary files in Chordal/.

The source of this document is in Chordal/ChordalDoc.m2:121:0.