Underlying mathematical gruntwork. More...
Classes | |
class | regina::NFastRay |
A fast but inflexible class storing a ray rooted at the origin whose coordinates are rational. More... | |
class | regina::NFastVector< T > |
A fast but inflexible vector of elements from a given ring T. More... | |
class | regina::NLargeInteger |
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::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 slow but flexible class storing a ray rooted at the origin whose coordinates are rational. More... | |
class | regina::NVector< T > |
A slow but flexible vector class of elements from a given ring T. More... | |
class | regina::NVectorDense< T > |
A dense vector of objects of type T. More... | |
class | regina::NVectorMatrix_Illegal_Modification |
An exception thrown when a matrix row or column vector is modified. More... | |
class | regina::NVectorMatrix< T > |
A vector that corresponds to a row or column of a matrix. More... | |
class | regina::NVectorMatrixRow< T > |
A vector that corresponds to a row of a matrix. More... | |
class | regina::NVectorMatrixCol< T > |
A vector that corresponds to a column of a matrix. More... | |
class | regina::NVectorUnit_Illegal_Modification |
An exception thrown when a unit vector is modified. More... | |
class | regina::NVectorUnit< T > |
A unit vector of type T. More... | |
Functions | |
template<class R > | |
bool | regina::isZero (R x) |
Determines whether the given real number is zero. | |
template<class R > | |
bool | regina::isNonZero (R x) |
Determines whether the given real number is non-zero. | |
template<class R > | |
bool | regina::isPositive (R x) |
Determines whether the given real number is strictly positive. | |
template<class R > | |
bool | regina::isNegative (R x) |
Determines whether the given real number is strictly negative. | |
template<class R > | |
bool | regina::isNonNegative (R x) |
Determines whether the given real number is non-negative. | |
template<class R > | |
bool | regina::isNonPositive (R x) |
Determines whether the given real number is non-positive. | |
void | regina::smithNormalForm (NMatrixInt &matrix) |
Transforms the given integer matrix into Smith normal form. | |
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. | |
unsigned | regina::rowBasis (NMatrixInt &matrix) |
Find a basis for the row space of the given matrix. | |
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. | |
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. | |
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. | |
template<class T > | |
std::ostream & | regina::operator<< (std::ostream &out, const NFastVector< T > &vector) |
Writes the given vector to the given output stream. | |
std::ostream & | regina::operator<< (std::ostream &out, const NLargeInteger &large) |
Writes the given integer to the given output stream. | |
std::ostream & | regina::operator<< (std::ostream &out, const NMatrix2 &mat) |
Writes the given matrix to the given output stream. | |
bool | regina::simpler (const NMatrix2 &m1, const NMatrix2 &m2) |
Determines whether the first given matrix is more aesthetically pleasing than the second. | |
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. | |
std::ostream & | regina::operator<< (std::ostream &out, const NRational &rat) |
Writes the given rational to the given output stream. | |
NRay * | regina::intersect (const NRay &pos, const NRay &neg, const NVector< NLargeInteger > &hyperplane) |
Returns a newly allocated ray representing the intersection of the hyperplane joining two given rays with the given additional hyperplane. | |
long | regina::reducedMod (long k, long modBase) |
Reduces k modulo modBase to give the smallest possible absolute value. | |
long | regina::gcd (long a, long b) |
Calculates the greatest common divisor of two signed integers. | |
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. | |
long | regina::lcm (long a, long b) |
Calculates the lowest common multiple of two signed integers. | |
unsigned long | regina::modularInverse (unsigned long n, unsigned long k) |
Calculates the multiplicative inverse of one integer modulo another. | |
void | regina::factorise (unsigned long n, std::list< unsigned long > &factors) |
Calculates the prime factorisation of the given integer. | |
void | regina::primesUpTo (const NLargeInteger &roof, std::list< NLargeInteger > &primes) |
Determines all primes up to and including the given upper bound. | |
template<class T > | |
std::ostream & | regina::operator<< (std::ostream &out, const NVector< T > &vector) |
Writes the given vector to the given output stream. | |
regina::NMatrixInt::NMatrixInt (unsigned long rows, unsigned long cols) | |
Creates a new matrix of the given size. | |
regina::NMatrixInt::NMatrixInt (const NMatrixInt &cloneMe) | |
Creates a new matrix that is a clone of the given matrix. | |
virtual void | regina::NMatrixInt::writeTextShort (std::ostream &out) const |
Writes this object in short text format to the given output stream. | |
virtual void | regina::NMatrixInt::writeTextLong (std::ostream &out) const |
Writes this object in long text format to the given output stream. | |
Variables | |
const double | regina::epsilon |
A very small positive real designed to accommodate for rounding error. | |
static T | regina::NFastVector::zero |
Zero in the underlying number system. | |
static T | regina::NFastVector::one |
One in the underlying number system. | |
static T | regina::NFastVector::minusOne |
Negative one in the underlying number system. | |
static T | regina::NMatrixRing::zero |
Zero in the underlying ring. | |
static T | regina::NMatrixRing::one |
One (the multiplicative identity) in the underlying ring. | |
static T | regina::NVector::zero |
Zero in the underlying number system. | |
static T | regina::NVector::one |
One in the underlying number system. | |
static T | regina::NVector::minusOne |
Negative one in the underlying number system. |
Underlying mathematical gruntwork.
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:
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).Our convention is that a matrix is in column echelon form if:
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".
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). |
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.
n | the integer to factorise. |
factors | the list into which prime factors will be inserted. |
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.
a | one of the two integers to work with. |
b | the other integer with which to work. |
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.
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. |
NRay* regina::intersect | ( | const NRay & | pos, |
const NRay & | neg, | ||
const NVector< NLargeInteger > & | hyperplane | ||
) |
Returns a newly allocated ray representing the intersection of the hyperplane joining two given rays with the given additional hyperplane.
The resulting ray will be in its smallest integral form.
The given additional hyperplane must pass through the origin, and is represented by a vector perpendicular to it.
If the arguments pos and neg are on the positive and negative sides of the hyperplane respectively (where positive and negative sides are determined by the sign of the dot product of a ray vector with the hyperplane representation vector), the resulting ray is guaranteed to be a positive multiple of a convex combination of the two original rays.
The resulting ray is guaranteed to be of the same subclass of NRay as argument neg.
pos | one of the two given rays. |
neg | the other of the two given rays. |
hyperplane | a perpendicular to the given additional hyperplane. |
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.
x | the number to examine. |
true
if and only if the given number is strictly negative. 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.
x | the number to examine. |
true
if and only if the given number is non-negative. 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.
x | the number to examine. |
true
if and only if the given number is non-positive. 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.
x | the number to examine. |
true
if and only if the given number is approximately non-zero. 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.
x | the number to examine. |
true
if and only if the given number is strictly positive. 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.
x | the number to examine. |
true
if and only if the given number is approximately zero. 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.
a | one of the two integers to work with. |
b | the other integer with which to work. |
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.
n | the modular base in which to work. |
k | the number whose multiplicative inverse should be found. |
k * v == 1 (mod n)
. regina::NMatrixInt::NMatrixInt | ( | unsigned long | rows, |
unsigned long | cols | ||
) | [inline, inherited] |
Creates a new matrix of the given size.
All entries will be initialised to zero.
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, inherited] |
Creates a new matrix that is a clone of the given matrix.
cloneMe | the matrix to clone. |
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
.
out | the output stream to which to write. |
rat | the rational to write. |
std::ostream& regina::operator<< | ( | std::ostream & | out, |
const NLargeInteger & | large | ||
) |
Writes the given integer to the given output stream.
out | the output stream to which to write. |
large | the integer to write. |
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.
out | the output stream to which to write. |
vector | the vector to write. |
std::ostream& regina::operator<< | ( | std::ostream & | out, |
const NFastVector< 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.
out | the output stream to which to write. |
vector | the vector to write. |
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.
out | the output stream to which to write. |
mat | the matrix to write. |
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.
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. |
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.
roof | the upper bound up to which primes will be found. |
primes | the list into which the primes will be inserted. |
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.
k | the number to reduce modulo modBase. |
modBase | the modular base in which to work. |
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.
matrix | the matrix to examine and rearrange. |
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:
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.
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. |
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.
m1 | the first matrix to examine. |
m2 | the second matrix to examine. |
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. 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).
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. |
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. 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.
The algorithm used is due to Hafner and McCurley (1991). It does not use modular arithmetic to control the intermediate coefficient explosion.
matrix | the matrix to transform. |
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:
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.
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. |
void regina::NMatrixInt::writeTextLong | ( | std::ostream & | out ) | const [inline, virtual, inherited] |
Writes this object in long text format to the given output stream.
The output should provided the user with all the information they could want. The output should end with a newline.
The default implementation of this routine merely calls writeTextShort() and adds a newline.
out | the output stream to which to write. |
Reimplemented from regina::ShareableObject.
void regina::NMatrixInt::writeTextShort | ( | std::ostream & | out ) | const [inline, virtual, inherited] |
Writes this object in short text format to the given output stream.
The output should fit on a single line and no newline should be written.
out | the output stream to which to write. |
Implements regina::ShareableObject.
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).
T regina::NFastVector< T >::minusOne [static, inherited] |
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!
T regina::NVector< T >::minusOne [static, inherited] |
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!
T regina::NVector< T >::one [static, inherited] |
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!
T regina::NMatrixRing< T >::one [static, inherited] |
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!
T regina::NFastVector< T >::one [static, inherited] |
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!
T regina::NFastVector< T >::zero [static, inherited] |
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!
T regina::NMatrixRing< T >::zero [static, inherited] |
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!
T regina::NVector< T >::zero [static, inherited] |
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!