Regina Calculation Engine
|
Stores an adjusted matrix of homogeneous linear matching equations based on a given triangulation, in sparse form.
More...
#include <enumerate/treelp.h>
Public Member Functions | |
LPInitialTableaux (const Triangulation< 3 > *tri, NormalCoords coords, bool enumeration) | |
Construts this adjusted sparse matrix of matching equations. More... | |
~LPInitialTableaux () | |
Destroys this matrix. More... | |
const Triangulation< 3 > * | tri () const |
Returns the underlying 3-manifold triangulation from which the matching equations were derived. More... | |
NormalCoords | coords () const |
Returns the coordinate system that is used for the matrix of matching equations. More... | |
unsigned | rank () const |
Returns the rank of this matrix. More... | |
unsigned | columns () const |
Returns the number of columns in this matrix. More... | |
unsigned | coordinateColumns () const |
Returns the number of columns that correspond to normal coordinates or angle structure coordinates. More... | |
bool | constraintsBroken () const |
Indicates whether or not the extra constraints from the template parameter LPConstraints were added successfully. More... | |
const int * | columnPerm () const |
Returns the permutation that describes how the columns of the matching equation matrix were reordered. More... | |
template<typename IntType > | |
IntType | multColByRow (const LPMatrix< IntType > &m, unsigned mRow, unsigned thisCol) const |
Computes the inner product of (i) the given row of the given matrix with (ii) the given column of this matrix. More... | |
template<typename IntType > | |
IntType | multColByRowOct (const LPMatrix< IntType > &m, unsigned mRow, unsigned thisCol) const |
A variant of multColByRow() that takes into account any adjustments to the tableaux that are required when this is a quadrilateral column being used to represent an octagon type. More... | |
template<typename IntType > | |
void | fillInitialTableaux (LPMatrix< IntType > &m) const |
Fills the given matrix with the contents of this matrix. More... | |
LPInitialTableaux (const LPInitialTableaux &)=delete | |
LPInitialTableaux & | operator= (const LPInitialTableaux &)=delete |
Stores an adjusted matrix of homogeneous linear matching equations based on a given triangulation, in sparse form.
Typically these will be the normal surface matching equations in some coordinate system, or the angle structure equations.
This class forms part of the tree traversal algorithms for enumerating and locating normal surfaces, as described in "A tree traversal algorithm for decision problems in knot theory and 3-manifold topology", Burton and Ozlen, Algorithmica 65:4 (2013), pp. 772-801, and "A fast branching algorithm for unknot recognition with experimental polynomial-time behaviour", Burton and Ozlen, arXiv:1211.1079. It is also used for locating a single strict angle structure, and for enumerating all taut angle structures.
The adjustments (which are all carried out in the LPInitialTableaux class constructor) are as follows:
There is also optional support for adding extra linear constraints (such as a constraint on Euler characteristic for normal surfaces). These extra constraints are supplied by the template parameter LPConstraint, and will generate LPConstraint::nConstraints additional rows and columns (used by the additional variables that evaluate the corresponding linear functions). If there are no additional constraints, simply use the template parameter LPConstraintNone.
In some cases, it may be impossible to add the extra linear constraints that you would like (for instance, the constraints might require some preconditions on the underlying triangulation that are not met). If this is a possibility in your setting, you should call constraintsBroken() to test this as soon as the LPInitialTableaux has been constructed. Even if the constraints could not be added correctly, the tableaux will be left in a consistent state (the constraints will just be treated as zero functions instead).
This class is optimised for working with columns of the matrix (in particular, multiplying columns of this matrix by rows of some other matrix).
This class can only work in quadrilateral normal coordinates (NS_QUAD), standard normal coordinates (NS_STANDARD), or angle structure coordinates (NS_ANGLE). No other coordinate systems are supported.
regina::LPInitialTableaux< LPConstraint >::LPInitialTableaux | ( | const Triangulation< 3 > * | tri, |
NormalCoords | coords, | ||
bool | enumeration | ||
) |
Construts this adjusted sparse matrix of matching equations.
tri | the underlying 3-manifold triangulation. |
coords | the coordinate system to use for the matrix of matching equations; this must be one of NS_QUAD, NS_STANDARD, or NS_ANGLE. |
enumeration | true if we should optimise the tableaux for a full enumeration of vertex surfaces or taut angle structures, or false if we should optimise the tableaux for an existence test (such as searching for a non-trivial normal disc or sphere, or a strict angle structure). |
|
inline |
Destroys this matrix.
|
inline |
Returns the permutation that describes how the columns of the matching equation matrix were reordered.
This permutation maps column numbers in this adjusted matching equation matrix to column numbers in the original (unmodified) matching equation matrix that was originally derived from the triangulation.
The permutation is returned as an array of columns() integers, such that column i of this adjusted matrix corresponds to column columnPerm()[i]
of the original matrix.
If you are imposing additional constraints through the template parameter LPConstraint, then the corresponding extra variables will be included in the permutation; however, these are never moved and will always remain the rightmost variables in this system (i.e., the columns of highest index).
As well as the requirement that this is a genuine permutation of 0,...,columns()-1, this array will also adhere to the following constraints. In the following discussion, n refers to the number of tetrahedra in the underlying triangulation.
|
inline |
Returns the number of columns in this matrix.
Note that, if we are imposing extra constraints through the template parameter LPConstraint, then there will be extra variables to enforce these, and so the number of columns will be larger than in the original matching equation matrix.
|
inline |
Indicates whether or not the extra constraints from the template parameter LPConstraints were added successfully.
This query function is important because some constraints require additional preconditions on the underlying triangulation, and cannot be added if these preconditions are not satisfied.
Even if the extra constraints were not added successfully, this tableaux will be left in a consistent state (the extra constraints will be treated as zero functions). See the LPInitialTableaux class notes for further details.
true
if the constraints were not added successfully, or false
if the constraints were added successfully.
|
inline |
Returns the number of columns that correspond to normal coordinates or angle structure coordinates.
This is precisely the number of columns in the original matrix of matching equations.
|
inline |
Returns the coordinate system that is used for the matrix of matching equations.
This will be the same coordinate system that was passed to the LPInitialTableaux constructor; in particular, it will always be one of NS_QUAD, NS_STANDARD, or NS_ANGLE.
|
inline |
Fills the given matrix with the contents of this matrix.
This effectively copies this sparse but highly specialised matrix representation into a dense but more flexible matrix representation.
m | the matrix to fill. |
|
inline |
Computes the inner product of (i) the given row of the given matrix with (ii) the given column of this matrix.
This routine is optimised to use the sparse representation of columns in this matrix.
m | the matrix whose row we will use in the inner product. |
mRow | the row of the matrix m to use in the inner product. |
thisCol | the column of this matrix to use in the inner product. |
|
inline |
A variant of multColByRow() that takes into account any adjustments to the tableaux that are required when this is a quadrilateral column being used to represent an octagon type.
The LPData class offers support for octagonal almost normal surfaces, in which exactly one tetrahedron is allowed to have exactly one octagon type. We represent such an octagon as a pair of incompatible quadrilaterals within the same tetrahedron. See the LPData class notes for details on how this works.
In some settings where we are using additional constraints through the template parameter LPConstraint, these extra constraints behave differently in the presence of octagons (i.e., the coefficient of the octagon type is not just the sum of coefficients of the two constituent quadrilateral types). This routine effectively allows us to adjust the tableaux accordingly.
Specifically: this routine computes the inner product of (i) the given row of the given matrix with (ii) the given column of this matrix. We assume that the given column of this matrix describes one of the two quadrilateral coordinates in some tetrahedron that together form an octagon type, and (via the helper routine LPConstraint::Coefficients::innerProductOct) we implicitly adjust the coefficients of our extra constraints accordingly.
This routine is optimised to use the sparse representation of columns in this matrix.
This routine is not used with angle structure coordinates.
m | the matrix whose row we will use in the adjusted inner product. |
mRow | the row of the matrix m to use in the adjusted inner product. |
thisCol | the column of this matrix to use in the adjusted inner product. |
|
inline |
Returns the rank of this matrix.
Note that, if we are imposing extra constraints through the template parameter LPConstraint, then there will be extra variables to enforce these, and so the rank will be larger than the rank of the original matching equation matrix.
|
inline |
Returns the underlying 3-manifold triangulation from which the matching equations were derived.