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.
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 that mill contains a homogeneous ideal and col and row are of type long
MinimalResolution(mill) -- Returns the minimal free resolution of mill as vector<matrix>
BettiDiagramm(mill) -- Returns a matrix of ZZ, which represents the graded Betti numbers in Macaulay-Style
BettiColumn(mill, col) -- Returns a matrix with only one column. This column represents the colth column of the Betti diagram (The first column/row has index 0).
BettiNumber(mill, row, col) -- Returns a RingElem of type RingZZ which represents the Betti number at position (row, col) in the Betti diagram (The first column/row has index 0).
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").
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 -- A DynamicBitset which represents a wedge product.
myRightProduct -- A PPMonoidElem.
myBasis -- A JBElemConstIter. This is a constant iterator to a vector of JBElem.
The class JBElem is contained in the class MorseElement. The set of all JBElems should represent the given Janet basis. It consists of the basis element (elem) as RingElem, the multiplicative variables (multVars) as DynamicBitset and the lexicographic position above all elements in the given Janet basis (lexPos) as long. We store this additional attributes to avoid redundant computations.
MorseElement implements several methods to construct and modify MorseElements. 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 form x[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 of RingElems. These vector corresponds to the given Janet basis (e.g. The standard representation of r is (1. element of the vector) * (1. basis element) + (2. element of the vector) * (2. basis element) + ...). Together with r we save the standard representation in a pair.
We store all standard representations in a multimap (myContainer), where the key is the corresponding LPP.
If we want to compute the standard representation of r. We first searching for the range with the same LPP in myContainer. If this is range is not empty we try to find an pair with the same RingElem than r. If we do not find such an element we compute the standard representation, save it in myContainer and return the standard representation to the user.
=== MorseGraph and MorsePaths ===
For modelling a Graph we need some additional data structures beside a MorseElement.
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 called myResolution and is of type map<MorseElement, MorsePaths>).
The edges have additionally values. Therefore we join the beginnings of all edges with the value (a simple RingElem) of the corresponding edges.
These list is represented by the class MorsePaths.
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 value 0 it removes this edge from the list.
The implementation of the list is quite complicated:
The beginning of the edges are MorseElements. To avoid memory consumption we only save a const_iterator to the corresponding MorseElement in myResolution.
For efficiency we save these const iters as a key of map, where the values are RingElems, representing the value of the corresponding edges.
If there is a MorseElement which is not the end of an edge we simply store it in myComputer with an empty MorsePaths.
MorseGraph does not only consists of myContainer. It also contains the a JBMill (myMill), the corresponding SparsePolyRing (myRing), the corresponding Janet basis as vector<MorseElement::JBElem> (myBasis) and a ring (myMapRing).
MorseGraph is purely virtual class. It concrete subclasses are MorseBetti and MorseResolution.
In MorseBetti all values of the edges in our graph are of type CoeffRing(myRing) and in MorseResolution they are of type myRing.
The variable myMapRing keeps track of this information.
The implementation of MorseBetti and MorseResolution is quite similar.
They compute and minimize the MorseGraph, but the MorseBetti 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 between MorseBetti and MorseResolution is the expected output.
MorseBetti computes the graded betti diagram of an ideal. The betti diagramm is represented by matrix.
MorseResolution computes a graded free resolution of an ideal. The resolution is represented by vector<matrix>.
=== PartialMorseBetti ===
We use this class to compute a single Betti column or Betti number. It is a child class of MorseBetti. The algorithms to compute these partial datas are nearly the same as in the class MorseBetti. 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 of RingElems 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.