Examples
User documentation for Morse Graph
Via the Morse Graph we are able to compute a free resolution of a
polynomial ideal via the JBMill
. We can compute a free
resolution and, if the ideal is homogeneous, the minimal free resolution
and the graded Betti numbers of the ideal.
Using the Morse Graph
In the following let mill
a JBMill
with degrevlex
order
The following command computes a free resolution as vector<matrix>
Resolution(mill)
Now we assume thatmill
contains a homogeneous ideal andcol
androw
are of typelong
MinimalResolution(mill)
-- Returns the minimal free resolution ofmill
asvector<matrix>
BettiDiagramm(mill)
-- Returns a matrix ofZZ
, which represents the graded Betti numbers in Macaulay-StyleBettiColumn(mill, col)
-- Returns a matrix with only one column. This column represents thecol
th column of the Betti diagram (The first column/row has index0
).BettiNumber(mill, row, col)
-- Returns aRingElem
of typeRingZZ
which represents the Betti number at position (row
,col
) in the Betti diagram (The first column/row has index0
).
Maintainer documentation for TmpMorseGraph.C, TmpMorseBetti.C, TmpMorseResolution.C, TmpPartialMorseBetti.C TmpMorseElement.C, TmpMorsePaths.C, TmpResolutionMinimization.C
For computing free resolutions and graded Betti diagramms with a Janet basis we using algebraic discrete Morse theory. (More information about the mathematical background the user can find in "On the free resolution induced by a Pommaret basis").
MorseElement and JBElem
The basic datastructure is a, so called, MorseGraph
. The nodes are represented by the class MorseElement
. A MorseElement
consists of three main data members:
myWedgeProduct
-- ADynamicBitset
which represents a wedge product.myRightProduct
-- APPMonoidElem
.myBasis
-- AJBElemConstIter
. This is a constant iterator to a vector ofJBElem
. The classJBElem
is contained in the classMorseElement
. The set of allJBElem
s should represent the given Janet basis. It consists of the basis element (elem
) asRingElem
, the multiplicative variables (multVars
) asDynamicBitset
and the lexicographic position above all elements in the given Janet basis (lexPos
) aslong
. We store this additional attributes to avoid redundant computations.MorseElement
implements several methods to construct and modifyMorseElement
s. In addition to that it implements several methods which we need to compute the resolution. For detailed descriptions the user should take a look at the inline documentation. === StandardRepresentationContainer === During the computation of the free resolution we need to compute standard representations of the formx[i] * basis_element
very often. Due to that we often compute the same standard representation. To avoid redundant computations we store every already computed standard representation in the container. A standard representation is represented by a vector ofRingElem
s. These vector corresponds to the given Janet basis (e.g. The standard representation ofr
is (1. element of the vector) * (1. basis element) + (2. element of the vector) * (2. basis element) + ...). Together withr
we save the standard representation in apair
. We store all standard representations in a multimap (myContainer
), where the key is the corresponding LPP. If we want to compute the standard representation ofr
. We first searching for the range with the same LPP inmyContainer
. If this is range is not empty we try to find an pair with the sameRingElem
thanr
. If we do not find such an element we compute the standard representation, save it inmyContainer
and return the standard representation to the user. === MorseGraph and MorsePaths === For modelling a Graph we need some additional data structures beside aMorseElement
. Essentially we need again a map where the beginning of an edge should be the key and a vector of the tail of all edges with same beginning should be the value. For efficiency and simplicity we invert this natural datastructure, e.g. the tail of an edge is the key of the map and the beginning of all edges with this tail is the value (this list is calledmyResolution
and is of typemap<MorseElement, MorsePaths>
). The edges have additionally values. Therefore we join the beginnings of all edges with the value (a simpleRingElem
) of the corresponding edges. These list is represented by the classMorsePaths
.MorsePaths
implements an intelligent version of this list. It notices if we add an already known edge and sums up the values of this edges. If a edge has value0
it removes this edge from the list. The implementation of the list is quite complicated: The beginning of the edges areMorseElement
s. To avoid memory consumption we only save aconst_iterator
to the correspondingMorseElement
inmyResolution
. For efficiency we save these const iters as a key of map, where the values areRingElem
s, representing the value of the corresponding edges. If there is aMorseElement
which is not the end of an edge we simply store it inmyComputer
with an emptyMorsePaths
.MorseGraph
does not only consists ofmyContainer
. It also contains the aJBMill
(myMill
), the correspondingSparsePolyRing
(myRing
), the corresponding Janet basis asvector<MorseElement::JBElem>
(myBasis
) and aring
(myMapRing
).MorseGraph
is purely virtual class. It concrete subclasses areMorseBetti
andMorseResolution
. InMorseBetti
all values of the edges in our graph are of typeCoeffRing(myRing)
and inMorseResolution
they are of typemyRing
. The variablemyMapRing
keeps track of this information. The implementation ofMorseBetti
andMorseResolution
is quite similar. They compute and minimize the MorseGraph, but theMorseBetti
class only computes the part of the graph where all edges have only a constant value. For further information look at the cited paper or at the inline documentation. Another difference betweenMorseBetti
andMorseResolution
is the expected output.MorseBetti
computes the graded betti diagram of an ideal. The betti diagramm is represented bymatrix
.MorseResolution
computes a graded free resolution of an ideal. The resolution is represented byvector<matrix>
. === PartialMorseBetti === We use this class to compute a single Betti column or Betti number. It is a child class ofMorseBetti
. The algorithms to compute these partial datas are nearly the same as in the classMorseBetti
. The only difference are the restriction to one column or only one number. For more informations take a look at the inline documentation. === ResolutionMinimization === This class takes a vector of matrices ofRingElem
s which should represent a free resolution and minimizes it with the standard algorithm. == Bugs, Shortcomings and other ideas == === ResolutionMinimization === Implementing a own specialized myAddRowMul function (skipping zeros...). === MorseGraph === Waiting for general free resolution object.