Regina Calculation Engine
|
Stores an adjusted matrix of matching equations from the underlying 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 (NTriangulation *tri, NormalCoords coords, bool enumeration) | |
Construts this adjusted sparse matrix of matching equations. More... | |
~LPInitialTableaux () | |
Destroys this matrix. More... | |
NTriangulation * | tri () const |
Returns the underlying 3-manifold triangulation from which the matching equations were derived. 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. 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 matching equations from the underlying triangulation, in sparse form.
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 (to appear), DOI 10.1007/s00453-012-9645-3, and "A fast branching algorithm for unknot recognition with experimental polynomial-time behaviour", Burton and Ozlen, arXiv:1211.1079.
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). 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) or standard normal coordinates (NS_STANDARD). No other coordinate systems are supported.