Regina Calculation Engine
Static Public Member Functions | List of all members
regina::NHilbertPrimal Class Reference

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

Detailed Description

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.

Python:
Not present.

Member Function Documentation

template<class RayClass , class RayIterator , class OutputIterator >
static void regina::NHilbertPrimal::enumerateHilbertBasis ( OutputIterator  results,
const RayIterator &  raysBegin,
const RayIterator &  raysEnd,
const NEnumConstraintList constraints,
NProgressTracker tracker = 0 
)
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.

Precondition
If constraints is passed, then the given list of extremal rays contains only those extremal rays that satisfy all of the given constraints.
The template argument RayClass is derived from NRay (or may possibly be NRay itself).
The template argument RayIterator is a forward iterator type, and when dereferenced can be cast to (const NRay*).
Warning
If a progress tracker is passed, be aware that the present implementation updates percentage progress very infrequently, and may take a very long time to honour cancellation requests.
Parameters
resultsthe output iterator to which the resulting basis elements will be written; this must accept objects of type RayClass*.
raysBeginan iterator pointing to the beginning of the list of extremal rays.
raysEndan iterator pointing past the end of the list of extremal rays.
constraintsa set of validity constraints as described above, or 0 if no additional constraints should be imposed.
trackera progress tracker through which progress will be reported, or 0 if no progress reporting is required.

The documentation for this class was generated from the following file:

Copyright © 1999-2014, The Regina development team
This software is released under the GNU General Public License, with some additional permissions; see the source code for details.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@debian.org).