Regina Calculation Engine
|
Implements a modified primal algorithm for enumerating Hilbert bases. More...
#include <enumerate/nhilbertprimal.h>
Static Public Member Functions | |
template<class RayClass , class RayIterator , class OutputIterator > | |
static void | enumerateHilbertBasis (OutputIterator results, const RayIterator &raysBegin, const RayIterator &raysEnd, const NEnumConstraintList *constraints, NProgressTracker *tracker=0) |
Determines the Hilbert basis that generates all integer points in the intersection of the n-dimensional non-negative orthant with some linear subspace. More... | |
Implements a modified primal algorithm for enumerating Hilbert bases.
This incorporates the primal algorithm described in "Normaliz: Algorithms for affine monoids and rational cones", Winfried Bruns and Bogdan Ichim, J. Algebra 324 (2010), 1098-1113, and has been modified to allow for additional constraints (such as the quadrilateral constraints from normal surface theory).
To summarise: the algorithm first enumerates extremal rays of the rational cone, and then decomposes the admissible region of the cone (where the extra constraints are satisfied) into maximal admissible faces. It calls Normaliz directly to enumerate the Hilbert basis for each maximal admissible faces, and finally combines these into a basis for the entire space.
All routines of interest within this class are static; no object of this class should ever be created.
|
static |
Determines the Hilbert basis that generates all integer points in the intersection of the n-dimensional non-negative orthant with some linear subspace.
The resulting basis elements will be of the class RayClass, will be newly allocated, and will be written to the given output iterator. Their deallocation is the responsibility of whoever called this routine.
The intersection of the non-negative orthant with this linear subspace is a pointed polyhedral cone with apex at the origin, and this routine requires the extremal rays of this cone to be provided as input. The extremal rays can be computed using NDoubleDescription::enumerate() in general cases, though sometimes (such as with normal surface theory) more efficient methods are available.
This routine computes the Hilbert basis of all integer points in this cone. The resulting list of basis vectors will contain no duplicates or redundancies.
The parameter constraints may contain a set of validity constraints, in which case this routine will only return valid basis elements. Each validity constraint is of the form "at most one of these coordinates may be non-zero"; see the NEnumConstraintList class for details. These contraints have the important property that, although validity is not preserved under addition, invalidity is.
An optional progress tracker may be passed. If so, this routine will update the percentage progress and poll for cancellation requests. It will be assumed that an appropriate stage has already been declared via NProgressTracker::newStage() before this routine is called, and that NProgressTracker::setFinished() will be called after this routine returns.
results | the output iterator to which the resulting basis elements will be written; this must accept objects of type RayClass* . |
raysBegin | an iterator pointing to the beginning of the list of extremal rays. |
raysEnd | an iterator pointing past the end of the list of extremal rays. |
constraints | a set of validity constraints as described above, or 0 if no additional constraints should be imposed. |
tracker | a progress tracker through which progress will be reported, or 0 if no progress reporting is required. |