Macaulay2 » Documentation
Packages » Chordal :: Chordal
next | previous | forward | backward | up | index | toc

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 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..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

Overview of methods

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

References

Authors

Version

This documentation describes version 0.2 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

  • Types
  • Functions and commands
  • 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
    • 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
    • topComponents(ChordalNet) -- top dimension of a chordal network
    • 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.