Regina Calculation Engine
|
A matrix class for use with linear programming. More...
#include <enumerate/ntreelp.h>
Public Member Functions | |
LPMatrix () | |
Creates an uninitialised matrix with no memory storage. More... | |
LPMatrix (unsigned rows, unsigned cols) | |
Creates a fully initialised rows by cols matrix with all elements set to zero. More... | |
~LPMatrix () | |
Destroys this matrix and all of the data it contains. More... | |
void | reserve (unsigned maxRows, unsigned maxCols) |
Reserves enough space to store the elements of a maxRows by maxCols matrix. More... | |
void | initClone (const LPMatrix &clone) |
Initialises this matrix to a copy of the given matrix. More... | |
void | initIdentity (unsigned size) |
Initialises this matrix to the identity matrix of the given size. More... | |
Integer & | entry (unsigned row, unsigned col) |
Returns a read-write reference to the given element of this matrix. More... | |
const Integer & | entry (unsigned row, unsigned col) const |
Returns a read-only reference to the given element of this matrix. More... | |
unsigned | rows () const |
Returns the number of rows in this matrix. More... | |
unsigned | columns () const |
Returns the number of columns in this matrix. More... | |
void | swapRows (unsigned r1, unsigned r2) |
Swaps the two given rows of this matrix. More... | |
void | combRow (const Integer &destCoeff, unsigned dest, const Integer &srcCoeff, unsigned src, const Integer &div) |
Applies a particular row operation to this matrix. More... | |
Integer | combRowAndNorm (const Integer &destCoeff, unsigned dest, const Integer &srcCoeff, unsigned src) |
Applies a particular row operation to this matrix, and then normalises. More... | |
void | negateRow (unsigned row) |
Negates all elements in the given row of this matrix. More... | |
void | dump (std::ostream &out) const |
Writes this matrix to the given output stream. More... | |
A matrix class for use with linear programming.
This class is used in the tree traversal algorithms for enumerating and locating vertex 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 operations on this matrix class are tailored and optimised specifically for use with the dual simplex method in the context of a repetitive backtracking search. As a result, the API is cumbersome and highly specialised, which makes this matrix class inappropriate for general use.
It is critical that, before using such a matrix, you reserve space for its elements, and then fix a specific size. A matrix for which both tasks have been done will be called initialised. You can initialise a matrix in one of two ways:
You may call the initialisation initClone() and initIdentity() routines more than once (e.g., during a backtracking search), and you may use different matrix sizes each time. However, you may never use more elements than you originally reserved space for.
This matrix is stored in dense form. All elements are of the integer class Integer, which is supplied as a template argument.