Matrices over the natural numbers quotiented by (t = t + p)¶

Defined in matrix.hpp.

This page describes the functionality for \(n \times n\) matrices over the finite quotient of the usual semiring of natural number by the congruence \(t = t + p\) for arbitrary \(n\), \(t\), and \(p\). The value \(t\) is referred to as the threshold and \(p\) is called the period. The matrices of this type are referred to by the acroynm ntp matrices, for “natural threshold period”. The NTPSemiring has elements \(\{0, 1, ..., t, t + 1, ..., t + p - 1\}\) where \(t\), and \(p\) are the threshold and period, respectively; addition and multiplication in the NTPSemiring is defined below.

There are three types of such matrices where:

the dimension is known at compile-time;
the dimension is to be defined a run time but the arithmetic operations are known at compile-time (i.e. the values of \(t\) and \(p\) are known at compile time)
both the dimension and the arithmetic operations (i.e. \(t\) and \(p\)) are to be defined a run time.

All three of these types can be accessed via the alias template NTPMat<T, P, R, C, Scalar>: if T and P have value 0, then the threshold and period can be set at run time, and if R or C is 0, then the dimension can be set at run time. The default values of T, P, and R are 0, and the default value of C is R.

The alias NTPMat<T, P, R, C, Scalar> is either StaticMatrix or DynamicMatrix, please refer to the documentation of these class templates for more details. The only substantial difference in the interface of StaticMatrix and DynamicMatrix is that the former can be default constructed and the latter should be constructed using the dimensions.

Example

NTPMat<11, 2, 3> m;  // default construct an uninitialized 3 x 3 static matrix with threshold 11, period 2
NTPMat<11, 2> m(4, 4);  // construct an uninitialized 4 x 4 dynamic matrix with threshold 11, period 2
NTPSemiring sr(11, 2);  // construct an ntp semiring with threshold 11, period 2
NTPMat<>  m(sr, 5, 5);  // construct an uninitialized 5 x 5 dynamic matrix with threshold 11, period 2

template<size_t T, size_t P, typename Scalar> struct NTPPlus¶

This is a stateless struct with a single call operator of signature: Scalar operator()(Scalar const x, Scalar const y) const noexcept that returns \(x \oplus y\) which is defined by

\[\begin{split}x\oplus y = \begin{cases} x + y & \text{if } x + y \leq T \\ T + ((x + y) - T \pmod{P}) & \text{if } x + y > T \end{cases}\end{split}\]

representing addition in the quotient of the semiring natural numbers by the congruence \((T = T + P)\).

template<size_t T, size_t P, typename Scalar> struct NTPProd¶

This is a stateless struct with a single call operator of signature: Scalar operator()(Scalar const x, Scalar const y) const noexcept that returns \(x \otimes y\) which is defined by

\[\begin{split}x\otimes y = \begin{cases} xy & \text{if } xy \leq T \\ T + ((xy - T) \pmod{P}) & \text{if } xy > T \end{cases}\end{split}\]

representing multiplication in the quotient of the semiring natural numbers by the congruence \((T = T + P)\).

template<typename Scalar = int> class NTPSemiring final¶

This class represents the ntp semiring consists of the integers \(\{0, 1, ..., t, t + 1, ..., t + p - 1\}\) for some \(t\) and \(p\) (called the threshold and period). Instances of this class can be used to define the value of the threshold \(t\) and period \(p\) at run time.

Template Parameters: Scalar – the type of the elements of the semiring.

NTPSemiring() = delete¶: Deleted default constructor.

NTPSemiring(NTPSemiring const&) = default¶: Default copy constructor.

NTPSemiring(NTPSemiring&&) = default¶: Default move constructor.

NTPSemiring &operator=(NTPSemiring const&) = default¶: Default copy assignment operator.

NTPSemiring &operator=(NTPSemiring&&) = default¶: Default move assignment operator.

explicit NTPSemiring(Scalar const t, Scalar const p)¶

Construct from threshold and period.

Parameters

t – the threshold (\(t \geq 0\)).
p – the period (\(p > 0\)).

Throws

LibsemigroupsException if t is less than zero.

Throws

LibsemigroupsException if p is less than or equal to zero.

Complexity

Constant.

Scalar zero() const noexcept¶

Returns \(0\); representing the additive identity of the quotient of the semiring of natural numbers.

Parameters: (None)
Returns: A value of type Scalar.
Exceptions: This function is noexcept and is guaranteed never to throw.
Complexity: Constant.

Scalar one() const noexcept¶

Returns \(1\); representing the additive identity of the quotient of the semiring of natural numbers.

Parameters: (None)
Returns: A value of type Scalar.
Exceptions: This function is noexcept and is guaranteed never to throw.
Complexity: Constant.

Scalar plus(Scalar const x, Scalar const y) const noexcept¶

Returns \(x \oplus y\) which is defined by

\[\begin{split}x\oplus y = \begin{cases} x + y & \text{if } x + y \leq \texttt{threshold()} \\ \texttt{threshold()} + ((x + y - \texttt{threshold()}) \pmod{\texttt{period()}}) & \text{if } x + y > \texttt{threshold()} \end{cases}\end{split}\]

representing the addition in the quotient of the semiring of natural numbers.

Parameters

x – scalar (\(0\leq x < \texttt{threshold()} + \texttt{period()}\))
y – scalar (\(0\leq y < \texttt{threshold()} + \texttt{period()}\))

Returns

A value of type Scalar.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

Scalar prod(Scalar const x, Scalar const y) const noexcept¶

Returns \(x \otimes y\) which is defined by

\[\begin{split}x\otimes y = \begin{cases} xy & \text{if } xy \leq \texttt{threshold()} \\ \texttt{threshold()} + ((xy - \texttt{threshold()})\pmod{\texttt{period()}}) & \text{if } xy > \texttt{threshold()} \end{cases}\end{split}\]

where \(t\) is the threshold; representing multiplication in the quotient of the semiring of natural numbers.

Parameters

x – scalar (\(0\leq x < \texttt{threshold()} + \texttt{period()}\))
y – scalar (\(0\leq y < \texttt{threshold()} + \texttt{period}()\))

Returns

A value of type Scalar.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

Scalar threshold() const noexcept¶

Returns the threshold value used to construct this.

Parameters: (None)
Returns: A value of type Scalar.
Exceptions: This function is noexcept and is guaranteed never to throw.
Complexity: Constant.

Scalar period() const noexcept¶

Returns the period value used to construct this.

Parameters: (None)
Returns: A value of type Scalar.
Exceptions: This function is noexcept and is guaranteed never to throw.
Complexity: Constant.

template<typename Scalar> using DynamicNTPMatWithSemiring = DynamicMatrix<NTPSemiring<Scalar>, Scalar>¶

Alias for ntp matrices with dimensions, threshold, and period defined at runtime.

Template Parameters: Scalar – The type of the entries in the matrix.

template<size_t T, size_t P, typename Scalar> using DynamicNTPMatWithoutSemiring = DynamicMatrix<NTPPlus<T, P, Scalar>, NTPProd<T, P, Scalar>, IntegerZero<Scalar>, IntegerOne<Scalar>, Scalar>¶

Alias for the type of dynamic ntp matrices where the dimension is defined at run time, but the threshold and period are defined at compile-time.

Template Parameters

T – the threshold.
P – the period.
Scalar – the type of the entries in the matrix.

template<size_t T, size_t P, size_t R, size_t C, typename Scalar> using StaticNTPMat = StaticMatrix<NTPPlus<T, P, Scalar>, NTPProd<T, P, Scalar>, IntegerZero<Scalar>, IntegerOne<Scalar>, R, C, Scalar>¶

Alias for static ntp matrices where the threshold, period, and dimensions are defined at compile-time.

Template Parameters

T – the threshold.
P – the period.
R – the number of rows.
C – the number of columns.
Scalar – The type of the entries in the matrix (default: int).

template<size_t T = 0, size_t P = 0, size_t R = 0, size_t C = R, typename Scalar = size_t> using NTPMat = std::conditional_t<R == 0 || C == 0, std::conditional_t<T == 0 && P == 0, DynamicNTPMatWithSemiring<Scalar>, DynamicNTPMatWithoutSemiring<T, P, Scalar>>, StaticNTPMat<T, P, R, C, Scalar>>¶

Template Parameters

T – the threshold. If both T and P are 0, this indicates that the value will be set at run time (default: 0).
P – the period. If both T and P are 0, this indicates that the value will be set at run time (default: 0).
R – the number of rows. A value of 0 indicates that the value will be set at run time (default: 0).
C – the number of columns. A value of 0 indicates that the value will be set at run time (default: R).
Scalar – The type of the entries in the matrix (default: size_t).

template<typename U> static constexpr bool IsNTPMat¶: This variable has value true if the template parameter U is the same as NTPMat<T, P, R, C, Scalar> for some values of T, P, R, C, and Scalar; and false if it is not.