Regina Calculation Engine
|
Stores an adjusted matrix of homogeneous linear matching equations based on a given triangulation, in sparse form. More...
#include <enumerate/ntreelp.h>
Classes | |
struct | Col |
Stores a single column of the adjusted matching equation matrix in sparse form. More... | |
Public Member Functions | |
LPInitialTableaux (const NTriangulation *tri, NormalCoords coords, bool enumeration) | |
Construts this adjusted sparse matrix of matching equations. More... | |
~LPInitialTableaux () | |
Destroys this matrix. More... | |
const NTriangulation * | 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 Integer > | |
Integer | multColByRow (const LPMatrix< Integer > &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 Integer > | |
Integer | multColByRowOct (const LPMatrix< Integer > &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 Integer > | |
void | fillInitialTableaux (LPMatrix< Integer > &m) const |
Fills the given matrix with the contents of this matrix. More... | |
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.