regina::LPInitialTableaux< LPConstraint > Class Template Reference
Vertex Enumeration

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

## Detailed Description

### template<class LPConstraint>
class regina::LPInitialTableaux< LPConstraint >

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:

- the rows of the matching equation matrix have been reordered so that the first rank() rows are full rank;
- the columns of the matching equation matrix have been reordered according to the permutation returned by columnPerm(). This is a heuristic reordering designed to improve the performance of the tree traversal algorithm; see columnPerm() for a list of constraints that such a reordering must satisfy.

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.

Warning
  The implementation of this class relies on the fact that the sum of absolute values of all coefficients in each column is at most four (not counting the rows for any optional extra constraints). If you are extending this class to work with more general matching equation matrices, you may need to change the implementation accordingly.

Precondition
  The template parameter LPConstraint must be one of the subclasses of LPConstraintBase. See the LPConstraintBase class notes for further details.

Headers:
  Parts of this template class are implemented in a separate header (treelp-impl.h), which is not included automatically by this file. Most end users should not need this extra header, since Regina's calculation engine already includes explicit instantiations for common combinations of template arguments.

Warning
  The API for this class has not yet been finalised. This means that the class interface may change in new versions of Regina, without maintaining backward compatibility. If you use this class directly in your own code, please watch the detailed changelogs upon new releases to see if you need to make changes to your code.

Python:
  Not present.

## Constructor & Destructor Documentation

## LPInitialTableaux()

template<class LPConstraint >

regina::LPInitialTableaux< LPConstraint >::LPInitialTableaux | ( | const Triangulation< 3 > * | tri,
|  | NormalCoords | coords,
|  | bool | enumeration
| ) |  |

Construts this adjusted sparse matrix of matching equations.

Precondition
  The given triangulation is non-empty.

Parameters

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

## ~LPInitialTableaux()

template<class LPConstraint >

regina::LPInitialTableaux< LPConstraint >::~LPInitialTableaux | ( |  | ) |

inline

Destroys this matrix.

## Member Function Documentation

## columnPerm()

template<class LPConstraint >

const int * regina::LPInitialTableaux< LPConstraint >::columnPerm | ( |  | ) | const

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.

- The quadrilateral coordinate columns must appear as the first 3n columns of the adjusted matrix. In particular, when working in the 7n-dimensional standard normal coordinate system, the remaining 4n triangle coordinate columns must appear last.
- The quadrilateral coordinate columns must be grouped by tetrahedron and ordered by quadrilateral type. In other words, for each i = 0,...,n-1, there will be some tetrahedron j for which the three columns 3i, 3i+1 and 3i+2 refer to the quadrilaterals in tetrahedron j of types 0, 1 and 2 respectively. Phrased loosely, we are allowed to reorder the tetrahedra, but not the quadrilateral coordinates within each tetrahedron.
- The triangle coordinate columns (if we are working in standard normal coordinates) must likewise be grouped by tetrahedron, and these tetrahedra must appear in the same order as for the quadrilateral types. In other words, for each i = 0,...,n-1, the quadrilateral columns 3i, 3i+1 and 3i+2 and the triangle columns 3n+4i, 3n+4i+1, 3n+4i+2 and 3n+4i+3 all refer to the same tetrahedron.
- For angle structure coordinates, the constraints are analogous to those for quadrilateral coordinates: the angle coordinates must be grouped by tetrahedron and ordered by angle type, and the final scaling coordinate must remain last.

Returns
  details of the permutation describing how columns were reordered.

## columns()

template<class LPConstraint >

unsigned regina::LPInitialTableaux< LPConstraint >::columns | ( |  | ) | const

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.

Returns
  the number of columns.

## constraintsBroken()

template<class LPConstraint >

bool regina::LPInitialTableaux< LPConstraint >::constraintsBroken | ( |  | ) | const

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.

Returns
  `true` if the constraints were not added successfully, or `false` if the constraints were added successfully.

## coordinateColumns()

template<class LPConstraint >

unsigned regina::LPInitialTableaux< LPConstraint >::coordinateColumns | ( |  | ) | const

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.

Returns
  the number of normal or angle structure coordinate columns.

## coords()

template<class LPConstraint >

NormalCoords regina::LPInitialTableaux< LPConstraint >::coords | ( |  | ) | const

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.

Returns
  the coordinate system.

## fillInitialTableaux()

template<class LPConstraint >
template<typename IntType >

void regina::LPInitialTableaux< LPConstraint >::fillInitialTableaux | ( | LPMatrix< IntType > & | m | ) | const

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.

Precondition
  The given matrix has already been initialised to size rank() * columns(), and all of its elements have already been set to zero. Note that this can all be arranged by calling the constructor LPMatrix::LPMatrix(unsigned, unsigned).

Parameters

  m | the matrix to fill.

## multColByRow()

template<class LPConstraint >
template<typename IntType >

IntType regina::LPInitialTableaux< LPConstraint >::multColByRow | ( | const LPMatrix< IntType > & | m,
|  | unsigned | mRow,
|  | unsigned | thisCol
| ) |  | const

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.

Precondition
  The given matrix m has precisely rank() columns.

Parameters

  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.

Returns
  the resulting inner product.

## multColByRowOct()

template<class LPConstraint >
template<typename IntType >

IntType regina::LPInitialTableaux< LPConstraint >::multColByRowOct | ( | const LPMatrix< IntType > & | m,
|  | unsigned | mRow,
|  | unsigned | thisCol
| ) |  | const

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.

Precondition
  The given matrix m has precisely rank() columns.
  Column thisCol of this matrix describes one of the two quadrilateral coordinates that are being combined to form an octagon type within some tetrahedron.

Parameters

  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.

Returns
  the resulting adjusted inner product.

## rank()

template<class LPConstraint >

unsigned regina::LPInitialTableaux< LPConstraint >::rank | ( |  | ) | const

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.

Returns
  the matrix rank.

## tri()

template<class LPConstraint >

const Triangulation< 3 > * regina::LPInitialTableaux< LPConstraint >::tri | ( |  | ) | const

inline

Returns the underlying 3-manifold triangulation from which the matching equations were derived.

Returns
  the underlying triangulation.

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

- enumerate/treeconstraint.h
- enumerate/treelp.h

Copyright © 1999-2016, 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@maths.uq.edu.au).