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

Implements a modified Contejean-Devie algorithm for enumerating Hilbert bases. More...

#include <enumerate/nhilbertcd.h>

Static Public Member Functions

template<class RayClass , class OutputIterator >
static void enumerateHilbertBasis (OutputIterator results, const NMatrixInt &subspace, const NEnumConstraintList *constraints)
 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 Contejean-Devie algorithm for enumerating Hilbert bases.

This is based on the stack-based algorithm described in "An efficient incremental algorithm for solving systems of linear Diophantine equations", Inform. and Comput. 113 (1994), 143-172, and has been modified to allow for additional constraints (such as the quadrilateral constraints from normal surface theory).

All routines of interest within this class are static; no object of this class should ever be created.

Warning
For normal surface theory, the Contejean-Devie algorithm is extremely slow, even when modified to incorporate admissibility constraints. Consider using the much faster NHilbertPrimal or NHilbertDual instead.
Python:
Not present.

Member Function Documentation

template<class RayClass , class OutputIterator >
static void regina::NHilbertCD::enumerateHilbertBasis ( OutputIterator  results,
const NMatrixInt subspace,
const NEnumConstraintList constraints 
)
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 non-negative orthant is an n-dimensional cone with its vertex at the origin. The extremal rays of this cone are the n non-negative coordinate axes. This cone also has n facets, where the ith facet is the non-negative orthant of the plane perpendicular to the ith coordinate axis.

This routine takes a linear subspace, defined by the intersection of a set of hyperplanes through the origin (this subspace is described as a matrix, with each row giving the equation for one hyperplane).

The purpose of this routine is to compute the Hilbert basis of the set of all integer points in the intersection of the original cone with this linear subspace. 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.

Precondition
The template argument RayClass is derived from NRay (or may possibly be NRay itself).
Warning
For normal surface theory, the Contejean-Devie algorithm is extremely slow, even when modified to incorporate admissibility constraints. Consider using the much faster NHilbertPrimal or NHilbertDual instead.
Parameters
resultsthe output iterator to which the resulting basis elements will be written; this must accept objects of type RayClass*.
subspacea matrix defining the linear subspace to intersect with the given cone. Each row of this matrix is the equation for one of the hyperplanes whose intersection forms this linear subspace. The number of columns in this matrix must be the dimension of the overall space in which we are working.
constraintsa set of validity constraints as described above, or 0 if no additional constraints should be imposed.

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

Copyright © 1999-2013, 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).