Mathematical Support

Underlying mathematical gruntwork. More...

## Classes

class | regina::NNativeInteger< bytes >
| A wrapper class for a native, fixed-precision integer type of the given size. More...
struct | regina::InfinityBase< supportInfinity >
| Internal base classes for use with NIntegerBase, templated on whether we should support infinity as an allowed value. More...
class | regina::NIntegerBase< supportInfinity >
| Represents an arbitrary precision integer. More...
class | regina::NMatrix< T >
| Represents a matrix of elements of the given type T. More...
class | regina::NMatrixRing< T >
| Represents a matrix of elements from a given ring T. More...
class | regina::NMatrix2
| Represents a 2-by-2 integer matrix. More...
class | regina::NMatrixInt
| Represents a matrix of arbitrary precision integers. More...
class | regina::NPerm3
| Represents a permutation of {0,1,2}. More...
class | regina::NPerm4
| Represents a permutation of {0,1,2,3}. More...
class | regina::NPerm5
| Represents a permutation of {0,1,2,3,4}. More...
class | regina::NPrimes
| A helper class for finding primes and factorising integers. More...
class | regina::NRational
| Represents an arbitrary precision rational number. More...
class | regina::NRay
| A fast class for storing a ray rooted at the origin whose coordinates are rational. More...
class | regina::NVector< T >
| An optimised vector class of elements from a given ring T. More...

## Typedefs

typedef NIntegerBase< true > | regina::NLargeInteger
| NLargeInteger is a typedef for NIntegerBase<true>, which offers arbitrary precision integers with support for infinity. More...
typedef NIntegerBase< false > | regina::NInteger
| NInteger is a typedef for NIntegerBase<false>, which offers arbitrary precision integers without support for infinity. More...

## Enumerations

enum | { regina::NPerm3::nPerms = 6, regina::NPerm3::nPerms_1 = 2 }
enum | { regina::NPerm3::code012 = 0, regina::NPerm3::code021 = 1, regina::NPerm3::code120 = 2, regina::NPerm3::code102 = 3, regina::NPerm3::code201 = 4, regina::NPerm3::code210 = 5 }
enum | { regina::NPerm4::nPerms = 24, regina::NPerm4::nPerms_1 = 6 }
enum | { regina::NPerm5::nPerms = 120, regina::NPerm5::nPerms_1 = 24 }

## Functions

template<class R >
bool | regina::isZero (R x)
| Determines whether the given real number is zero. More...
template<class R >
bool | regina::isNonZero (R x)
| Determines whether the given real number is non-zero. More...
template<class R >
bool | regina::isPositive (R x)
| Determines whether the given real number is strictly positive. More...
template<class R >
bool | regina::isNegative (R x)
| Determines whether the given real number is strictly negative. More...
template<class R >
bool | regina::isNonNegative (R x)
| Determines whether the given real number is non-negative. More...
template<class R >
bool | regina::isNonPositive (R x)
| Determines whether the given real number is non-positive. More...
REGINA_API void | regina::smithNormalForm (NMatrixInt &matrix)
| Transforms the given integer matrix into Smith normal form. More...
REGINA_API void | regina::smithNormalForm (NMatrixInt &matrix, NMatrixInt &rowSpaceBasis, NMatrixInt &rowSpaceBasisInv, NMatrixInt &colSpaceBasis, NMatrixInt &colSpaceBasisInv)
| A Smith normal form algorithm that also returns change of basis matrices. More...
REGINA_API void | regina::metricalSmithNormalForm (NMatrixInt &matrix, NMatrixInt *rowSpaceBasis=0, NMatrixInt *rowSpaceBasisInv=0, NMatrixInt *colSpaceBasis=0, NMatrixInt *colSpaceBasisInv=0)
| An alternative Smith normal form algorithm that also returns change of basis matrices. More...
REGINA_API unsigned | regina::rowBasis (NMatrixInt &matrix)
| Find a basis for the row space of the given matrix. More...
REGINA_API unsigned | regina::rowBasisAndOrthComp (NMatrixInt &input, NMatrixInt &complement)
| Finds a basis for the row space of the given matrix, as well as an "incremental" basis for its orthogonal complement. More...
REGINA_API void | regina::columnEchelonForm (NMatrixInt &M, NMatrixInt &R, NMatrixInt &Ri, const std::vector< unsigned > &rowList)
| Transforms a given matrix into column echelon form with respect to a collection of rows. More...
REGINA_API std::auto_ptr< NMatrixInt > | regina::preImageOfLattice (const NMatrixInt &hom, const std::vector< NLargeInteger > &sublattice)
| Given a homomorphism from Z^n to Z^k and a sublattice of Z^k, compute the preimage of this sublattice under this homomorphism. More...
REGINA_API std::auto_ptr< NMatrixInt > | regina::torsionAutInverse (const NMatrixInt &input, const std::vector< NLargeInteger > &invF)
| Given an automorphism of an abelian group, this procedure computes the inverse automorphism. More...
template<bool supportInfinity>
REGINA_API std::ostream & | regina::operator<< (std::ostream &out, const NIntegerBase< supportInfinity > &i)
| Writes the given integer to the given output stream. More...
template<bool supportInfinity>
REGINA_API NIntegerBase< supportInfinity > | regina::operator+ (long lhs, const NIntegerBase< supportInfinity > &rhs)
| Adds the given native integer to the given large integer. More...
template<bool supportInfinity>
REGINA_API NIntegerBase< supportInfinity > | regina::operator* (long lhs, const NIntegerBase< supportInfinity > &rhs)
| Multiplies the given native integer with the given large integer. More...
REGINA_API std::ostream & | regina::operator<< (std::ostream &out, const NMatrix2 &mat)
| Writes the given matrix to the given output stream. More...
REGINA_API bool | regina::simpler (const NMatrix2 &m1, const NMatrix2 &m2)
| Determines whether the first given matrix is more aesthetically pleasing than the second. More...
REGINA_API bool | regina::simpler (const NMatrix2 &pair1first, const NMatrix2 &pair1second, const NMatrix2 &pair2first, const NMatrix2 &pair2second)
| Determines whether the first given pair of matrices is more aesthetically pleasing than the second pair. More...
REGINA_API std::ostream & | regina::operator<< (std::ostream &out, const NPerm3 &p)
| Writes a string representation of the given permutation to the given output stream. More...
REGINA_API std::ostream & | regina::operator<< (std::ostream &out, const NPerm4 &p)
| Writes a string representation of the given permutation to the given output stream. More...
REGINA_API NPerm4 | regina::faceOrdering (int face)
| Returns a permutation mapping (0,1,2) to the vertices of the given tetrahedron face in their canonical order. More...
REGINA_API NPerm4 | regina::edgeOrdering (int edge)
| Returns a permutation mapping (0,1) to the vertices of the given tetrahedron edge in their canonical order. More...
REGINA_API std::string | regina::faceDescription (int face)
| Returns a string representation of the permutation mapping (0,1,2) to the vertices of the given tetrahedron face in their canonical order, as described in faceOrdering(). More...
REGINA_API std::string | regina::faceDescription (const NPerm4 &facePerm)
| Returns a string representation of the given permutation with only the images of 0, 1 and 2 included. More...
REGINA_API std::string | regina::edgeDescription (int edge)
| Returns a string representation of the permutation mapping (0,1) to the vertices of the given tetrahedron edge in their canonical order, as described in edgeOrdering(). More...
REGINA_API std::string | regina::edgeDescription (const NPerm4 &edgePerm)
| Returns a string representation of the given permutation with only the images of 0 and 1 included. More...
REGINA_API std::ostream & | regina::operator<< (std::ostream &out, const NPerm5 &p)
| Writes a string representation of the given permutation to the given output stream. More...
REGINA_API std::ostream & | regina::operator<< (std::ostream &out, const NRational &rat)
| Writes the given rational to the given output stream. More...
REGINA_API long | regina::reducedMod (long k, long modBase)
| Reduces k modulo modBase to give the smallest possible absolute value. More...
REGINA_API long | regina::gcd (long a, long b)
| Calculates the greatest common divisor of two signed integers. More...
REGINA_API long | regina::gcdWithCoeffs (long a, long b, long &u, long &v)
| Calculates the greatest common divisor of two given integers and finds the smallest coefficients with which these integers combine to give their gcd. More...
REGINA_API long | regina::lcm (long a, long b)
| Calculates the lowest common multiple of two signed integers. More...
REGINA_API unsigned long | regina::modularInverse (unsigned long n, unsigned long k)
| Calculates the multiplicative inverse of one integer modulo another. More...
REGINA_API void | regina::factorise (unsigned long n, std::list< unsigned long > &factors)
| Calculates the prime factorisation of the given integer. More...
REGINA_API void | regina::primesUpTo (const NLargeInteger &roof, std::list< NLargeInteger > &primes)
| Determines all primes up to and including the given upper bound. More...
template<class T >
std::ostream & | regina::operator<< (std::ostream &out, const NVector< T > &vector)
| Writes the given vector to the given output stream. More...
REGINA_API NPerm5 | regina::perm4to5 (const NPerm4 &p)
| Converts the given 4-element permutation to a 5-element permutation. More...
REGINA_API NPerm4 | regina::perm5to4 (const NPerm5 &p)
| Expresses the given 5-element permutation as a 4-element permutation. More...
REGINA_API NPerm4 | regina::perm3to4 (const NPerm3 &p)
| Converts the given 3-element permutation to a 4-element permutation. More...
REGINA_API NPerm3 | regina::perm4to3 (const NPerm4 &p)
| Expresses the given 4-element permutation as a 3-element permutation. More...
REGINA_API NPerm5 | regina::perm3to5 (const NPerm3 &p)
| Converts the given 3-element permutation to a 5-element permutation. More...
REGINA_API NPerm3 | regina::perm5to3 (const NPerm5 &p)
| Expresses the given 5-element permutation as a 3-element permutation. More...
| regina::NMatrixInt::NMatrixInt (unsigned long rows, unsigned long cols)
| Creates a new matrix of the given size. More...
| regina::NMatrixInt::NMatrixInt (const NMatrixInt &cloneMe)
| Creates a new matrix that is a clone of the given matrix. More...
virtual void | regina::NMatrixInt::writeTextShort (std::ostream &out) const
| Writes this object in short text format to the given output stream. More...
virtual void | regina::NMatrixInt::writeTextLong (std::ostream &out) const
| Writes this object in long text format to the given output stream. More...

## Variables

REGINA_API const double | regina::epsilon
| A very small positive real designed to accommodate for rounding error. More...
REGINA_API const NPerm4 * | regina::allPermsS4
| An array of size 24 containing all possible permutations of four elements. More...
REGINA_API const unsigned * | regina::allPermsS4Inv
| An array of size 24 containing the inverses of the permutations in the array allPermsS4. More...
REGINA_API const NPerm4 * | regina::orderedPermsS4
| An array of size 24 containing all possible permutations of four elements in lexicographical order. More...
REGINA_API const NPerm4 * | regina::allPermsS3
| An array of size 6 containing all possible permutations of three elements. More...
REGINA_API const unsigned * | regina::allPermsS3Inv
| An array of size 6 containing the inverses of the permutations in the array allPermsS3. More...
REGINA_API const NPerm4 * | regina::orderedPermsS3
| An array of size 6 containing all possible permutations of three elements in lexicographical order. More...
REGINA_API const NPerm4 * | regina::allPermsS2
| An array of size 2 containing all possible permutations of two elements. More...
REGINA_API const unsigned * | regina::allPermsS2Inv
| An array of size 2 containing the inverses of the permutations in the array allPermsS2. More...
static T | regina::NMatrixRing< T >::zero
| Zero in the underlying ring. More...
static T | regina::NMatrixRing< T >::one
| One (the multiplicative identity) in the underlying ring. More...
static T | regina::NVector< T >::zero
| Zero in the underlying number system. More...
static T | regina::NVector< T >::one
| One in the underlying number system. More...
static T | regina::NVector< T >::minusOne
| Negative one in the underlying number system. More...

## Detailed Description

Underlying mathematical gruntwork.

## Typedef Documentation

typedef NIntegerBase<false> regina::NInteger

NInteger is a typedef for NIntegerBase<false>, which offers arbitrary precision integers without support for infinity.

Python:
  This typedef is available in Python.

typedef NIntegerBase<true> regina::NLargeInteger

NLargeInteger is a typedef for NIntegerBase<true>, which offers arbitrary precision integers with support for infinity.

Python:
  This typedef is available in Python.

## Enumeration Type Documentation

anonymous enum

Enumerator

nPerms

The total number of permutations on three elements.

This is the size of the array Sn.

Python:
  Not present.

nPerms_1

The total number of permutations on two elements.

This is the size of the array Sn_1.

Python:
  Not present.

anonymous enum

Enumerator

code012

The internal code for the permutation (0,1,2).

Python:
  Not present.

code021

The internal code for the permutation (0,2,1).

Python:
  Not present.

code120

The internal code for the permutation (1,2,0).

Python:
  Not present.

code102

The internal code for the permutation (1,0,2).

Python:
  Not present.

code201

The internal code for the permutation (2,0,1).

Python:
  Not present.

code210

The internal code for the permutation (2,1,0).

Python:
  Not present.

anonymous enum

Enumerator

nPerms

The total number of permutations on four elements.

This is the size of the array Sn.

Python:
  Not present.

nPerms_1

The total number of permutations on three elements.

This is the size of the array Sn_1.

Python:
  Not present.

anonymous enum

Enumerator

nPerms

The total number of permutations on five elements.

This is the size of the array Sn.

Python:
  Not present.

nPerms_1

The total number of permutations on four elements.

This is the size of the array Sn_1.

Python:
  Not present.

## Function Documentation

REGINA_API void regina::columnEchelonForm | ( | NMatrixInt & | M,
|  | NMatrixInt & | R,
|  | NMatrixInt & | Ri,
|  | const std::vector< unsigned > & | rowList
| ) |  |

Transforms a given matrix into column echelon form with respect to a collection of rows.

Given the matrix M and the list rowList of rows from M, this algorithm puts M in column echelon form with respect to the rows in rowList. The only purpose of rowList is to clarify and/or weaken precisely what is meant by "column echelon form"; all rows of M are affected by the resulting column operations that take place.

This routine also returns the corresponding change of coordinate matrices R and Ri:

- If R and Ri are passed as identity matrices, the returned matrices will be such that `original_M * R = final_M` and `final_M * Ri = original_M` (and of course `final_M` is in column echelon form with respect to the given row list).
- If R and Ri are already non-trivial coordinate transformations, they are modified appropriately by the algorithm.

Our convention is that a matrix is in column echelon form if:

1. each column is either zero or there is a first non-zero entry which is positive (but see the note regarding rowList below);
2. moving from the leftmost column to the rightmost column, the rows containing the first non-zero entries for these columns have strictly increasing indices in rowList;
3. given a first non-zero column entry, in that row all the elements to the left are smaller and non-negative (all elements to the right are already zero by the previous condition);
4. all the zero columns are on the right hand side of the matrix.

By a "zero column" here we simply mean "zero for every row in \a rowList". Likewise, by "first non-zero entry" we mean "first row in \a rowList with a non-zero entry".

In a pinch, you can also use this routine to compute the inverse of an invertible square matrix.

Precondition
  Both R and Ri are square matrices with side length M.columns(), and these matrices are inverses of each other.

Python:
  The argument rowList should be supplied as a python list.

Parameters

  M | the matrix to reduce.
  R | used to return the row-reduction matrix, as described above.
  Ri | used to return the inverse of R.
  rowList | the rows to pay attention to. This list must contain distinct integers, all between 0 and M.rows()-1 inclusive. The integers may appear in any order (though changing the order will change the resulting column echelon form).

Author
  Ryan Budney

REGINA_API std::string regina::edgeDescription | ( | int | edge | ) |

Returns a string representation of the permutation mapping (0,1) to the vertices of the given tetrahedron edge in their canonical order, as described in edgeOrdering().

Only the images of 0 and 1 will be put in the string.

Deprecated:
  This routine is no longer recommended, and will be removed in some future version of Regina. Please use `NEdge::ordering[edge].trunc2()` (which gives identical results).

Parameters

  edge | an edge number in a tetrahedron. This should be between 0 and 5 inclusive. The constant arrays NEdge::edgeNumber and NEdge::edgeVertex describe which vertex numbers are joined by which edge numbers.

Returns
  a string representing the canonical ordering of vertices in the given edge.

std::string regina::edgeDescription | ( | const NPerm4 & | edgePerm | ) |

inline

Returns a string representation of the given permutation with only the images of 0 and 1 included.

Deprecated:
  This routine is no longer recommended, and will be removed in some future version of Regina. Please use NPerm4::trunc2() instead (which gives identical results).

Parameters

  edgePerm | the permutation to represent.

Returns
  a restricted string representation of the given permutation.

REGINA_API NPerm4 regina::edgeOrdering | ( | int | edge | ) |

Returns a permutation mapping (0,1) to the vertices of the given tetrahedron edge in their canonical order.

The images of (0,1) will be the vertex numbers of the vertices that make up the given edge of a generic tetrahedron.

The images of 2 and 3 in the returned permutation will be chosen so that the permutation will be even.

Deprecated:
  This routine is no longer recommended, and will be removed in some future version of Regina. Please use the lookup table NEdge::ordering instead (which gives identical results).

Parameters

  edge | an edge number in a tetrahedron. This should be between 0 and 5 inclusive. The constant arrays NEdge::edgeNumber and NEdge::edgeVertex describe which vertex numbers are joined by which edge numbers.

Returns
  the permutation representing the canonical ordering of vertices in the given edge.

REGINA_API std::string regina::faceDescription | ( | int | face | ) |

Returns a string representation of the permutation mapping (0,1,2) to the vertices of the given tetrahedron face in their canonical order, as described in faceOrdering().

Only the images of 0, 1 and 2 will be put in the string.

Deprecated:
  This routine is no longer recommended, and will be removed in some future version of Regina. Please use `NTriangle::ordering[face].trunc3()` (which gives identical results).

Parameters

  face | a face number in a tetrahedron. This should be between 0 and 3 inclusive. Note that face i is opposite vertex i.

Returns
  a string representing the canonical ordering of vertices in the given face.

std::string regina::faceDescription | ( | const NPerm4 & | facePerm | ) |

inline

Returns a string representation of the given permutation with only the images of 0, 1 and 2 included.

Deprecated:
  This routine is no longer recommended, and will be removed in some future version of Regina. Please use NPerm4::trunc3() instead (which gives identical results).

Parameters

  facePerm | the permutation to represent.

Returns
  a restricted string representation of the given permutation.

REGINA_API NPerm4 regina::faceOrdering | ( | int | face | ) |

Returns a permutation mapping (0,1,2) to the vertices of the given tetrahedron face in their canonical order.

The images of (0,1,2) will be the vertex numbers of the vertices that make up the given face of a generic tetrahedron.

Deprecated:
  This routine is no longer recommended, and will be removed in some future version of Regina. Please use the lookup table NTriangle::ordering instead (which gives identical results).

Parameters

  face | a face number in a tetrahedron. This should be between 0 and 3 inclusive. Note that face i is opposite vertex i.

Returns
  the permutation representing the canonical ordering of vertices in the given face.

REGINA_API void regina::factorise | ( | unsigned long | n,
|  | std::list< unsigned long > & | factors
| ) |  |

Calculates the prime factorisation of the given integer.

All the prime factors will be inserted into the given list. The algorithm used is very neanderthal and should only be used with reasonably sized integers. Don't use it to do RSA!

If a prime factor is repeated, it will be inserted multiple times into the list. The primes in the list are not guaranteed to appear in any specific order, nor are multiple occurrences of the same prime guaranteed to appear together.

Note that once finished the list will contain the prime factors as well as whatever happened to be in the list before this function was called.

Precondition
  The given integer is at least 1.

Deprecated:
  This routine is old and slow; please consider using the much faster routines from the NPrimes class instead.

Python:
  Argument factors is not present; instead this routine returns a python list containing the prime factors.

Parameters

  n | the integer to factorise.
  factors | the list into which prime factors will be inserted.

REGINA_API long regina::gcd | ( | long | a,
|  | long | b
| ) |  |

Calculates the greatest common divisor of two signed integers.

This routine is not recursive.

Although the arguments may be negative, the result is guaranteed to be non-negative. As a special case, gcd(0,0) is considered to be zero.

Parameters

  a | one of the two integers to work with.
  b | the other integer with which to work.

Returns
  the greatest common divisor of a and b.

REGINA_API long regina::gcdWithCoeffs | ( | long | a,
|  | long | b,
|  | long & | u,
|  | long & | v
| ) |  |

Calculates the greatest common divisor of two given integers and finds the smallest coefficients with which these integers combine to give their gcd.

This routine is not recursive.

Note that the given integers need not be non-negative. However, the gcd returned is guaranteed to be non-negative. As a special case, gcd(0,0) is considered to be zero.

If d is the gcd of a and b, the values placed in u and v will be those for which `u*a + v*b = d`, `-abs(a)/d < v*sign(b) <= 0` and `1 <= u*sign(a) <= abs(b)/d`.

In the special case where one of the given integers is zero, the corresponding coefficient will also be zero and the other coefficient will be 1 or -1 so that `u*a + v*b = d` still holds. If both given integers are zero, both of the coefficients will be set to zero.

Parameters

  a | one of the integers to work with.
  b | the other integer with which to work.
  u | a variable into which the final coefficient of a will be placed.
  v | a variable into which the final coefficient of b will be placed.

Returns
  the greatest common divisor of a and b.

template<class R >

bool regina::isNegative | ( | R | x | ) |

inline

Determines whether the given real number is strictly negative.

Any number within regina::epsilon of zero is considered to be zero.

Precondition
  R must be of a floating point real type.

Python:
  Not present.

Parameters

  x | the number to examine.

Returns
  `true` if and only if the given number is strictly negative.

template<class R >

bool regina::isNonNegative | ( | R | x | ) |

inline

Determines whether the given real number is non-negative.

Any number within regina::epsilon of zero is considered to be zero.

Precondition
  R must be of a floating point real type.

Python:
  Not present.

Parameters

  x | the number to examine.

Returns
  `true` if and only if the given number is non-negative.

template<class R >

bool regina::isNonPositive | ( | R | x | ) |

inline

Determines whether the given real number is non-positive.

Any number within regina::epsilon of zero is considered to be zero.

Precondition
  R must be of a floating point real type.

Python:
  Not present.

Parameters

  x | the number to examine.

Returns
  `true` if and only if the given number is non-positive.

template<class R >

bool regina::isNonZero | ( | R | x | ) |

inline

Determines whether the given real number is non-zero.

Any number within regina::epsilon of zero is considered to be zero.

Precondition
  R must be of a floating point real type.

Python:
  Not present.

Parameters

  x | the number to examine.

Returns
  `true` if and only if the given number is approximately non-zero.

template<class R >

bool regina::isPositive | ( | R | x | ) |

inline

Determines whether the given real number is strictly positive.

Any number within regina::epsilon of zero is considered to be zero.

Precondition
  R must be of a floating point real type.

Python:
  Not present.

Parameters

  x | the number to examine.

Returns
  `true` if and only if the given number is strictly positive.

template<class R >

bool regina::isZero | ( | R | x | ) |

inline

Determines whether the given real number is zero.

Any number within regina::epsilon of zero is considered to be zero.

Precondition
  R must be of a floating point real type.

Python:
  Not present.

Parameters

  x | the number to examine.

Returns
  `true` if and only if the given number is approximately zero.

REGINA_API long regina::lcm | ( | long | a,
|  | long | b
| ) |  |

Calculates the lowest common multiple of two signed integers.

Although the arguments may be negative, the result is guaranteed to be non-negative.

If either of the arguments is zero, the return value will also be zero.

Regarding possible overflow: This routine does not create any temporary integers that are larger than the final LCM.

Parameters

  a | one of the two integers to work with.
  b | the other integer with which to work.

Returns
  the lowest common multiple of a and b.

REGINA_API void regina::metricalSmithNormalForm | ( | NMatrixInt & | matrix,
|  | NMatrixInt * | rowSpaceBasis = `0`,
|  | NMatrixInt * | rowSpaceBasisInv = `0`,
|  | NMatrixInt * | colSpaceBasis = `0`,
|  | NMatrixInt * | colSpaceBasisInv = `0`
| ) |  |

An alternative Smith normal form algorithm that also returns change of basis matrices.

This routine may be preferable for extremely large matrices. This is a variant of Hafner-McCurley and Havas-Holt-Rees's description of pivoting methods.

The only input argument is matrix. The four remaining arguments (the change of basis matrices), if passed, will be refilled, though they must be constructed with the correct dimensions as seen in the preconditions below. All five arguments are used to return information as follows.

Let M be the initial value of matrix, and let S be the Smith normal form of M. After this routine exits:

- The argument matrix will contain the Smith normal form S;
- `colSpaceBasis * M * rowSpaceBasis = S`;
- `colSpaceBasisInv * S * rowSpaceBasisInv = M`;
- `colSpaceBasis * colSpaceBasisInv` and `rowSpaceBasis * rowSpaceBasisInv` are both identity matrices.

Thus, one obtains the Smith normal form the original matrix by multiplying on the left by ColSpaceBasis and on the right by RowSpaceBasis.

Precondition
  The matrices rowSpaceBasis and rowSpaceBasisInv, if passed, must be square with side length matrix.columns().
  The matrices colSpaceBasis and colSpaceBasisInv, if passed, must be square, with side length matrix.rows().

Parameters

  matrix | the original matrix to put into Smith Normal Form (this need not be square). When the algorithm terminates, this matrix is in its Smith Normal Form.
  rowSpaceBasis | used to return a change of basis matrix (see above for details). This is optional; you may pass a null pointer instead.
  rowSpaceBasisInv | used to return the inverse of rowSpaceBasis. This is optional; you may pass a null pointer instead.
  colSpaceBasis | used to return a change of basis matrix (see above for details). This is optional; you may pass a null pointer instead.
  colSpaceBasisInv | used to return the inverse of colSpaceBasis. This is optional; you may pass a null pointer instead.

Author
  Ryan Budney

REGINA_API unsigned long regina::modularInverse | ( | unsigned long | n,
|  | unsigned long | k
| ) |  |

Calculates the multiplicative inverse of one integer modulo another.

The inverse returned will be between 0 and n-1 inclusive.

Precondition
  n and k are both strictly positive;
  n and k have no common factors.

Parameters

  n | the modular base in which to work.
  k | the number whose multiplicative inverse should be found.

Returns
  the inverse v for which `k * v == 1 (mod n)`.

regina::NMatrixInt::NMatrixInt | ( | unsigned long | rows,
|  | unsigned long | cols
| ) |  |

inline

Creates a new matrix of the given size.

All entries will be initialised to zero.

Precondition
  The given number of rows and columns are both strictly positive.

Parameters

  rows | the number of rows in the new matrix.
  cols | the number of columns in the new matrix.

regina::NMatrixInt::NMatrixInt | ( | const NMatrixInt & | cloneMe | ) |

inline

Creates a new matrix that is a clone of the given matrix.

Parameters

  cloneMe | the matrix to clone.

template<bool supportInfinity>

REGINA_API NIntegerBase<supportInfinity> regina::operator* | ( | long | lhs,
|  | const NIntegerBase< supportInfinity > & | rhs
| ) |  |

inline

Multiplies the given native integer with the given large integer.

If the large integer is infinite, the result will also be infinity.

Python:
  Not available.

Parameters

  lhs | the native integer to multiply.
  rhs | the large integer to multiply.

Returns
  the product lhs times rhs.

template<bool supportInfinity>

REGINA_API NIntegerBase<supportInfinity> regina::operator+ | ( | long | lhs,
|  | const NIntegerBase< supportInfinity > & | rhs
| ) |  |

inline

Adds the given native integer to the given large integer.

If the large integer is infinite, the result will also be infinity.

Python:
  Not available.

Parameters

  lhs | the native integer to add.
  rhs | the large integer to add.

Returns
  the sum lhs plus rhs.

std::ostream & regina::operator<< | ( | std::ostream & | out,
|  | const NMatrix2 & | mat
| ) |  |

inline

Writes the given matrix to the given output stream.

The matrix will be written entirely on a single line, with the first row followed by the second row.

Parameters

  out | the output stream to which to write.
  mat | the matrix to write.

Returns
  a reference to out.

template<class T >

std::ostream& regina::operator<< | ( | std::ostream & | out,
|  | const NVector< T > & | vector
| ) |  |

Writes the given vector to the given output stream.

The vector will be written on a single line with elements separated by a single space. No newline will be written.

Python:
  Not present.

Parameters

  out | the output stream to which to write.
  vector | the vector to write.

Returns
  a reference to out.

REGINA_API std::ostream& regina::operator<< | ( | std::ostream & | out,
|  | const NRational & | rat
| ) |  |

Writes the given rational to the given output stream.

Infinity will be written as `Inf`. Undefined will be written as `Undef`. A rational with denominator one will be written as a single integer. All other rationals will be written in the form `r/s`.

Parameters

  out | the output stream to which to write.
  rat | the rational to write.

Returns
  a reference to out.

REGINA_API std::ostream& regina::operator<< | ( | std::ostream & | out,
|  | const NPerm3 & | p
| ) |  |

inline

Writes a string representation of the given permutation to the given output stream.

The format will be the same as is used by NPerm3::str().

Parameters

  out | the output stream to which to write.
  p | the permutation to write.

Returns
  a reference to out.

REGINA_API std::ostream& regina::operator<< | ( | std::ostream & | out,
|  | const NPerm5 & | p
| ) |  |

inline

Writes a string representation of the given permutation to the given output stream.

The format will be the same as is used by NPerm5::str().

Parameters

  out | the output stream to which to write.
  p | the permutation to write.

Returns
  a reference to out.

REGINA_API std::ostream& regina::operator<< | ( | std::ostream & | out,
|  | const NPerm4 & | p
| ) |  |

inline

Writes a string representation of the given permutation to the given output stream.

The format will be the same as is used by NPerm4::str().

Parameters

  out | the output stream to which to write.
  p | the permutation to write.

Returns
  a reference to out.

template<bool supportInfinity>

REGINA_API std::ostream& regina::operator<< | ( | std::ostream & | out,
|  | const NIntegerBase< supportInfinity > & | i
| ) |  |

Writes the given integer to the given output stream.

Parameters

  out | the output stream to which to write.
  i | the integer to write.

Returns
  a reference to out.

NPerm4 regina::perm3to4 | ( | const NPerm3 & | p | ) |

inline

Converts the given 3-element permutation to a 4-element permutation.

The resulting 4-element permutation will map 3 to 3, and will map 0, 1 and 2 to their respective images under p.

Parameters

  p | the given 3-element permutation.

Returns
  the permutation p expressed as a permutation of four elements, not three.

NPerm5 regina::perm3to5 | ( | const NPerm3 & | p | ) |

inline

Converts the given 3-element permutation to a 5-element permutation.

The resulting 5-element permutation will map 3 to 3 and 4 to 4, and will map 0, 1 and 2 to their respective images under p.

Parameters

  p | the given 3-element permutation.

Returns
  the permutation p expressed as a permutation of five elements, not three.

NPerm3 regina::perm4to3 | ( | const NPerm4 & | p | ) |

inline

Expresses the given 4-element permutation as a 3-element permutation.

The resulting 3-element permutation will map 0, 1 and 2 to their respective images under p. It is assumed that the image of 3 is 3 under p; otherwise this conversion cannot be performed.

Precondition
  The given permutation maps 3 to 3.

Parameters

  p | the given 4-element permutation.

Returns
  the permutation p expressed as a permutation of three elements, not four.

NPerm5 regina::perm4to5 | ( | const NPerm4 & | p | ) |

inline

Converts the given 4-element permutation to a 5-element permutation.

The resulting 5-element permutation will map 4 to 4, and will map 0, 1, 2 and 3 to their respective images under p.

Parameters

  p | the given 4-element permutation.

Returns
  the permutation p expressed as a permutation of five elements, not four.

NPerm3 regina::perm5to3 | ( | const NPerm5 & | p | ) |

inline

Expresses the given 5-element permutation as a 3-element permutation.

The resulting 3-element permutation will map 0, 1 and 2 to their respective images under p. It is assumed that `maps` 3,4 to 3,4 (but it may do so in either order); otherwise this conversion cannot be performed.

Precondition
  The given permutation maps 3,4 to 3,4 in some order.

Parameters

  p | the given 5-element permutation.

Returns
  the permutation p expressed as a permutation of three elements, not five.

NPerm4 regina::perm5to4 | ( | const NPerm5 & | p | ) |

inline

Expresses the given 5-element permutation as a 4-element permutation.

The resulting 4-element permutation will map 0, 1, 2 and 3 to their respective images under p. It is assumed that the image of 4 is 4 under p; otherwise this conversion cannot be performed.

Precondition
  The given permutation maps 4 to 4.

Parameters

  p | the given 5-element permutation.

Returns
  the permutation p expressed as a permutation of four elements, not five.

REGINA_API std::auto_ptr<NMatrixInt> regina::preImageOfLattice | ( | const NMatrixInt & | hom,
|  | const std::vector< NLargeInteger > & | sublattice
| ) |  |

Given a homomorphism from Z^n to Z^k and a sublattice of Z^k, compute the preimage of this sublattice under this homomorphism.

The homomorphism from Z^n to Z^k is described by the given k by n matrix hom. The sublattice is of the form `(p1 Z) * (p2 Z) * ... * (pk Z)`, where the non-negative integers p1, ..., pk are passed in the given list sublattice.

An equivalent problem is to consider hom to be a homomorphism from Z^n to Z_p1 + ... + Z_pk; this routine then finds the kernel of this homomorphism.

The preimage of the sublattice (equivalently, the kernel described above) is some rank n lattice in Z^n. This algorithm finds and returns a basis for the lattice.

Python:
  The argument sublattice should be supplied as a python list.

Parameters

  hom | the matrix representing the homomorphism from Z^n to Z^k; this must be a k by n matrix.
  sublattice | a list of length k describing the sublattice of Z^k; the elements of this list must be the non-negative integers p1, ..., pk as described above.

Returns
  a new matrix whose columns are a basis for the preimage lattice. This matrix will have precisely n rows.

Author
  Ryan Budney

REGINA_API void regina::primesUpTo | ( | const NLargeInteger & | roof,
|  | std::list< NLargeInteger > & | primes
| ) |  |

Determines all primes up to and including the given upper bound.

All the primes found will be inserted into the given list in increasing order.

The algorithm currently used is fairly neanderthal.

Precondition
  The given list is empty.

Deprecated:
  This routine is old and slow; please consider using the much faster routines from the NPrimes class instead.

Python:
  Argument primes is not present; instead this routine returns a python list containing the primes up to and including roof.

Parameters

  roof | the upper bound up to which primes will be found.
  primes | the list into which the primes will be inserted.

REGINA_API long regina::reducedMod | ( | long | k,
|  | long | modBase
| ) |  |

Reduces k modulo modBase to give the smallest possible absolute value.

For instance, `reducedMod(4,10) = 4` but `reducedMod(6,10) = -4`. In the case of a tie, the positive solution is taken.

Precondition
  modBase is strictly positive.

Parameters

  k | the number to reduce modulo modBase.
  modBase | the modular base in which to work.

REGINA_API unsigned regina::rowBasis | ( | NMatrixInt & | matrix | ) |

Find a basis for the row space of the given matrix.

This routine will rearrange the rows of the given matrix so that the first rank rows form a basis for the row space (where rank is the rank of the matrix). The rank itself will be returned. No other changes will be made to the matrix aside from swapping rows.

Although this routine takes an integer matrix (and only uses integer operations), we consider the row space to be over the rationals. That is, although we never divide, we act as though we could if we wanted to.

Parameters

  matrix | the matrix to examine and rearrange.

Returns
  the rank of the given matrix.

REGINA_API unsigned regina::rowBasisAndOrthComp | ( | NMatrixInt & | input,
|  | NMatrixInt & | complement
| ) |  |

Finds a basis for the row space of the given matrix, as well as an "incremental" basis for its orthogonal complement.

This routine takes an (r by c) matrix input, as well as a square (c by c) matrix complement, and does the following:

- The rows of input are rearranged so that the first rank rows form a basis for the row space (where rank is the rank of the matrix). No other changes are made to this matrix aside from swapping rows.
- The matrix complement is re-filled (any previous contents are thrown away) so that, for any i between 0 and rank-1 inclusive, the final (c - i) rows of complement form a basis for the orthogonal complement of the first i rows of the rearranged input.
- The rank of the matrix input is returned from this routine.

This routine can help with larger procedures that need to build up a row space and simultaneously cut down the complement one dimension at a time.

Although this routine takes integer matrices (and only uses integer operations), we consider all bases to be over the rationals. That is, although we never divide, we act as though we could if we wanted to.

Precondition
  The matrix complement is a square matrix, whose size is equal to the number of columns in input.

Parameters

  input | the input matrix whose row space we will describe; this matrix will be changed (though only by swapping rows).
  complement | the square matrix that will be re-filled with the "incremental" basis for the orthogonal complement of input.

Returns
  the rank of the given matrix input.

REGINA_API bool regina::simpler | ( | const NMatrix2 & | m1,
|  | const NMatrix2 & | m2
| ) |  |

Determines whether the first given matrix is more aesthetically pleasing than the second.

The way in which this judgement is made is purely aesthetic on the part of the author, and is subject to change in future versions of Regina.

Parameters

  m1 | the first matrix to examine.
  m2 | the second matrix to examine.

Returns
  `true` if m1 is deemed to be more pleasing than m2, or `false` if either the matrices are equal or m2 is more pleasing than m1.

REGINA_API bool regina::simpler | ( | const NMatrix2 & | pair1first,
|  | const NMatrix2 & | pair1second,
|  | const NMatrix2 & | pair2first,
|  | const NMatrix2 & | pair2second
| ) |  |

Determines whether the first given pair of matrices is more aesthetically pleasing than the second pair.

The way in which this judgement is made is purely aesthetic on the part of the author, and is subject to change in future versions of Regina.

Note that pairs are ordered, so the pair (M, N) may be more (or perhaps less) pleasing than the pair (N, M).

Parameters

  pair1first | the first matrix of the first pair to examine.
  pair1second | the second matrix of the first pair to examine.
  pair2first | the first matrix of the second pair to examine.
  pair2second | the second matrix of the second pair to examine.

Returns
  `true` if the first pair is deemed to be more pleasing than the second pair, or `false` if either the ordered pairs are equal or the second pair is more pleasing than the first.

REGINA_API void regina::smithNormalForm | ( | NMatrixInt & | matrix | ) |

Transforms the given integer matrix into Smith normal form.

Note that the given matrix need not be square and need not be of full rank.

Reading down the diagonal, the final Smith normal form will have a series of non-negative, non-decreasing invariant factors followed by zeroes. "Invariant factor" refers to the convention that the ith term divides the (i+1)th term, and so they are unique.

The algorithm used is due to Hafner and McCurley (1991). It does not use modular arithmetic to control the intermediate coefficient explosion.

Parameters

  matrix | the matrix to transform.

REGINA_API void regina::smithNormalForm | ( | NMatrixInt & | matrix,
|  | NMatrixInt & | rowSpaceBasis,
|  | NMatrixInt & | rowSpaceBasisInv,
|  | NMatrixInt & | colSpaceBasis,
|  | NMatrixInt & | colSpaceBasisInv
| ) |  |

A Smith normal form algorithm that also returns change of basis matrices.

This is a modification of the one-argument smithNormalForm(NMatrixInt&). As well as converting the given matrix matrix into Smith normal form, it also returns the appropriate change-of-basis matrices corresponding to all the row and column operations that were performed.

The only input argument is matrix. The four remaining arguments (the change of basis matrices) will be refilled, though they must be constructed with the correct dimensions as seen in the preconditions below. All five arguments are used to return information as follows.

Let M be the initial value of matrix, and let S be the Smith normal form of M. After this routine exits:

- The argument matrix will contain the Smith normal form S;
- `colSpaceBasis * M * rowSpaceBasis = S`;
- `colSpaceBasisInv * S * rowSpaceBasisInv = M`;
- `colSpaceBasis * colSpaceBasisInv` and `rowSpaceBasis * rowSpaceBasisInv` are both identity matrices.

Thus, one obtains the Smith normal form the original matrix by multiplying on the left by ColSpaceBasis and on the right by RowSpaceBasis.

Precondition
  The matrices rowSpaceBasis and rowSpaceBasisInv that are passed are square, with side length matrix.columns().
  The matrices colSpaceBasis and colSpaceBasisInv that are passed are square, with side length matrix.rows().

Parameters

  matrix | the original matrix to put into Smith Normal Form (this need not be square). When the algorithm terminates, this matrix is in its Smith Normal Form.
  rowSpaceBasis | used to return a change of basis matrix (see above for details).
  rowSpaceBasisInv | used to return the inverse of rowSpaceBasis.
  colSpaceBasis | used to return a change of basis matrix (see above for details).
  colSpaceBasisInv | used to return the inverse of colSpaceBasis.

Author
  Ryan Budney

REGINA_API std::auto_ptr<NMatrixInt> regina::torsionAutInverse | ( | const NMatrixInt & | input,
|  | const std::vector< NLargeInteger > & | invF
| ) |  |

Given an automorphism of an abelian group, this procedure computes the inverse automorphism.

The abelian group is of the form `Z_p1 + Z_p2 + ... + Z_pn`. The input is an n-by-n matrix A which represents a lift of the automorphism to just some n-by-n matrix. Specifically, you have a little commutative diagram with `Z^n –A–> Z^n` covering the automorphism of `Z_p1 + Z_p2 + ... + Z_pn`, where the maps down are the direct sum of the standard quotients `Z –> Z_pi`. So if you want this procedure to give you meaningful output, A must be a lift of a genuine automorphism of `Z_p1 + ... + Z_pn`.

Precondition
  The list p1, p2, ..., pn is a list of invariant factors, which means that p1|p2, ..., p{n-1}|pn.

Python:
  The argument invF should be supplied as a python list.

Parameters

  input | the n-by-n matrix A, which must be a lift of a genuine automorphism as described above.
  invF | the list p1, p2, ..., pn.

Returns
  the inverse automorphism, also described as an n-by-n matrix as per the discussion above.

Author
  Ryan Budney

void regina::NMatrixInt::writeTextLong | ( | std::ostream & | out | ) | const

inline virtual

Writes this object in long text format to the given output stream.

The output should provide the user with all the information they could want. The output should be human-readable, should not contain extremely long lines (so users can read the output in a terminal), and should end with a final newline.

The default implementation of this routine merely calls writeTextShort() and adds a newline.

Python:
  The parameter out does not exist; standard output will be used.

Parameters

  out | the output stream to which to write.

Reimplemented from regina::ShareableObject.

void regina::NMatrixInt::writeTextShort | ( | std::ostream & | out | ) | const

inline virtual

Writes this object in short text format to the given output stream.

The output should be human-readable, should fit on a single line, and should not end with a newline.

Python:
  The parameter out does not exist; standard output will be used.

Parameters

  out | the output stream to which to write.

Implements regina::ShareableObject.

## Variable Documentation

REGINA_API const NPerm4* regina::allPermsS2

An array of size 2 containing all possible permutations of two elements.

In each permutation, 2 maps to 2 and 3 maps to 3.

The permutations with even indices in the array are the even permutations, and those with odd indices in the array are the odd permutations.

Note that the permutations are also in lexicographical order.

Deprecated:
  This array has been moved into the NPerm4 class, and can now be accessed as the static array NPerm4::S2. The deprecated name regina::allPermsS2 now just points to NPerm4::S2, and will be removed in some future version of Regina.

REGINA_API const unsigned* regina::allPermsS2Inv

An array of size 2 containing the inverses of the permutations in the array allPermsS2.

Specifically, the inverse of permutation `allPermsS2[i]` is the permutation `allPermsS2[ allPermsS2Inv[i] ]`.

Deprecated:
  This array is unnecessary, since all elements of S2 are their own inverses. This array will be removed in some future version of Regina.

REGINA_API const NPerm4* regina::allPermsS3

An array of size 6 containing all possible permutations of three elements.

In each permutation, 3 maps to 3.

The permutations with even indices in the array are the even permutations, and those with odd indices in the array are the odd permutations.

Note that the permutations are not necessarily in lexicographical order.

Deprecated:
  This array has been moved into the NPerm4 class, and can now be accessed as the static array NPerm4::S3. The deprecated name regina::allPermsS4 now just points to NPerm4::S3, and will be removed in some future version of Regina.

REGINA_API const unsigned* regina::allPermsS3Inv

An array of size 6 containing the inverses of the permutations in the array allPermsS3.

Specifically, the inverse of permutation `allPermsS3[i]` is the permutation `allPermsS3[ allPermsS3Inv[i] ]`.

Deprecated:
  This array has been moved into the NPerm3 class, and can now be accessed as the static array NPerm3::invS3. The deprecated name regina::allPermsS3Inv now just points to NPerm3::invS3, and will be removed in some future version of Regina.

REGINA_API const NPerm4* regina::allPermsS4

An array of size 24 containing all possible permutations of four elements.

The permutations with even indices in the array are the even permutations, and those with odd indices in the array are the odd permutations.

Note that the permutations are not necessarily in lexicographical order.

Deprecated:
  This array has been moved into the NPerm4 class, and can now be accessed as the static array NPerm4::S4. The deprecated name regina::allPermsS4 now just points to NPerm4::S4, and will be removed in some future version of Regina.

REGINA_API const unsigned* regina::allPermsS4Inv

An array of size 24 containing the inverses of the permutations in the array allPermsS4.

Specifically, the inverse of permutation `allPermsS4[i]` is the permutation `allPermsS4[ allPermsS4Inv[i] ]`.

Deprecated:
  This array has been moved into the NPerm4 class, and can now be accessed as the static array NPerm4::invS4. The deprecated name regina::allPermsS4Inv now just points to NPerm4::invS4, and will be removed in some future version of Regina.

REGINA_API const double regina::epsilon

A very small positive real designed to accommodate for rounding error.

Any two numbers within epsilon of each other are considered to be equal by the generic zero-testing and sign-testing routines defined in this file (isZero(), isPositive(), isNonNegative() and so on).

template<class T>

T regina::NVector< T >::minusOne

static

Negative one in the underlying number system.

This would be `const` if it weren't for the fact that some compilers don't like this. It should never be modified!

template<class T>

T regina::NVector< T >::one

static

One in the underlying number system.

This would be `const` if it weren't for the fact that some compilers don't like this. It should never be modified!

template<class T>

T regina::NMatrixRing< T >::one

static

One (the multiplicative identity) in the underlying ring.

This would be `const` if it weren't for the fact that some compilers don't like this. It should never be modified!

REGINA_API const NPerm4* regina::orderedPermsS3

An array of size 6 containing all possible permutations of three elements in lexicographical order.

In each permutation, 3 maps to 3.

Deprecated:
  This array has been moved into the NPerm4 class, and can now be accessed as the static array NPerm4::orderedS3. The deprecated name regina::orderedPermsS3 now just points to NPerm4::orderedS3, and will be removed in some future version of Regina.

REGINA_API const NPerm4* regina::orderedPermsS4

An array of size 24 containing all possible permutations of four elements in lexicographical order.

Deprecated:
  This array has been moved into the NPerm4 class, and can now be accessed as the static array NPerm4::orderedS4. The deprecated name regina::orderedPermsS4 now just points to NPerm4::orderedS4, and will be removed in some future version of Regina.

template<class T>

T regina::NVector< T >::zero

static

Zero in the underlying number system.

This would be `const` if it weren't for the fact that some compilers don't like this. It should never be modified!

template<class T>

T regina::NMatrixRing< T >::zero

static

Zero in the underlying ring.

This would be `const` if it weren't for the fact that some compilers don't like this. It should never be modified!

Copyright © 1999-2014, 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@debian.org).