The LinearAlgebra:-Modular subpackage is a highly efficient suite of programmer tools for performing dense linear algebra computations in Z/m, the integers modulo m over the positive range.

As a programmer package, the key focus is on efficient computation mod m, so for all routines that accept modular data in Matrix or Vector form, no checking of the input data (to verify that all data is in the range $0..m-1$) is performed. If data outside the allowed range is present, the called function can produce incorrect answers.

There are three datatypes that can be used by this subpackage. Each one must be chosen explicitly or implicitly for all routines in the subpackage. You cannot mix datatypes for the functions. Two of these datatypes, integer[4]/integer[8] and float[8] are implemented efficiently through use of hardware data and compiled routines. The remaining datatype is integer, which uses native Maple integers.

The integer[4]/integer[8] datatype is dependent on the hardware on which it is running. For 32-bit versions of Maple, the datatype is integer[4], and it allows moduli in the range 2 .. 2^16-1 or $2..65535$.

For 64-bit versions of Maple, the datatype is integer[8], and it allows moduli in the range 2 .. 2^32-1 or $2..4294967295$. When specifying the use of this datatype, $\mathrm{integer}\left[\right]$ can be used to make code more easily portable between 32-bit and 64-bit versions.

Where possible, the float[8] datatype uses Basic Linear Algebra Subprograms (BLAS) to augment the efficiency of the routines.  For more information, see References. The allowed modulus range for this datatype is 2 .. 2^25-1 or $2..33554431$, which provides a larger range than the integer[4] datatype for 32-bit versions of Maple, so it may be better suited for use in algorithms requiring many primes or larger primes.

As mentioned before, the integer datatype is implemented by using native Maple integers. This means there is no limit on the range of allowable moduli, but all functions for this datatype are implemented in native Maple, so compared to the other datatypes, use of this datatype is significantly slower.

Generally, the Mod and Create commands are used to construct mod m Matrices and Vectors of the required types.

Note: It is not required that they be used to construct Matrices and Vectors, as they are of a standard Maple datatype (integer[4]/integer[8], float[8], and integer). Construction of a 10 by 10 Matrix of float[8] data to use with the subpackage can be accomplished with the Matrix constructor, that is, Matrix(10, 10, datatype=float[8], storage=rectangular), though use of the Create command for this purpose is recommended (see information on latency below).

Each command in the Modular subpackage can be accessed by using either the long form or the short form of the command name in the command calling sequence.

The long form, LinearAlgebra:-Modular:-command, is always available. The short form can be used after loading the package.

The low-level commands (basic operations) allow for specification of a Sub-Matrix or Sub-Vector for operation, and as a result, can perform operations on part of a Matrix or Vector, or treat a row of a Matrix as a Vector, or work with the transpose of a Matrix or Vector directly, without making copies. The following is a list of available commands in this category.

The mid-level commands allow for in-place or specified output operations, that is, no object copying, but cannot work on parts of a Matrix or Vector.  The following is a list of available commands in this category.

The high-level commands do not generally support in-place operation, and are typically implemented in native Maple, though they call on the mid and low-level functions quite extensively. The following is a list of available commands in this category.

In addition, integer algorithms have been implemented based on the modular algorithms mentioned above, and modular homomorphism techniques, and these include:

All low and mid-level commands for the hardware datatypes have been designed to be as efficient as possible, and to have very low latency, so that many operations on small objects can be performed efficiently. For example, construction of a $\mathrm{10x10}{\mathrm{float}}_8$ matrix using the Create command requires less than 1/10 the time as the same operation performed using the Matrix constructor (sampled over 10000 iterations).

Warning: the core algorithms in the package are designed to be most efficient with $\mathrm{C\_order}$ matrices (when the data is large), so if efficiency is a major consideration, applications should restrict to use of $\mathrm{C\_order}$.

$\mathrm{with}\left(\mathrm{LinearAlgebra}:-\mathrm{Modular}\right)$

$\left[\mathrm{AddMultiple}\,\mathrm{Adjoint}\,\mathrm{BackwardSubstitute}\,\mathrm{Basis}\,\mathrm{CharacteristicPolynomial}\,\mathrm{ChineseRemainder}\,\mathrm{Copy}\,\mathrm{Create}\,\mathrm{Determinant}\,\mathrm{Fill}\,\mathrm{ForwardSubstitute}\,\mathrm{Identity}\,\mathrm{IntegerCharacteristicPolynomial}\,\mathrm{IntegerDeterminant}\,\mathrm{IntegerLinearSolve}\,\mathrm{Inverse}\,\mathrm{LUApply}\,\mathrm{LUDecomposition}\,\mathrm{LinearSolve}\,\mathrm{MatBasis}\,\mathrm{MatGcd}\,\mathrm{MatrixPower}\,\mathrm{Mod}\,\mathrm{Multiply}\,\mathrm{Permute}\,\mathrm{Random}\,\mathrm{Rank}\,\mathrm{RankProfile}\,\mathrm{RowEchelonTransform}\,\mathrm{RowReduce}\,\mathrm{Swap}\,\mathrm{Transpose}\,\mathrm{ZigZag}\right]$

$\mathrm{Mat}≔\mathrm{Mod}\left(13\,\left[\left[1\,x\,x^2\right]\,\left[x-2\,3\,\frac{x}{x-1}\right]\right]\,x=4\,\mathrm{float}\left[8\right]\right)$

$\mathrm{Mat}≔\left[\begin{array}{ccc}1.& 4.& 3.\\ 2.& 3.& 10.\end{array}\right]$

$\mathrm{RowReduce}\left(13\,\mathrm{Mat}\,2\,3\,3\,'\det '\,0\,0\,0\,0\,\mathrm{true}\right)\:$

$\mathrm{Mat}$

$\left[\begin{array}{ccc}1.& 0.& 1.\\ 0.& 1.& 7.\end{array}\right]$

$\mathrm{Transpose}\left(13\,\mathrm{Mat}\right)$

$\left[\begin{array}{cc}1.& 0.\\ 0.& 1.\\ 1.& 7.\end{array}\right]$

$\mathrm{dtype}≔\mathrm{integer}\left[\frac{\mathrm{kernelopts}\left(\mathrm{wordsize}\right)}{8}\right]\:$

$\mathrm{V1}≔\mathrm{Mod}\left(13\,\left[5\,2\,3\,4\,1\right]\,\mathrm{dtype}\right)$

$\mathrm{V1}≔\left[\begin{array}{c}5\\ 2\\ 3\\ 4\\ 1\end{array}\right]$

$\mathrm{V2}≔\mathrm{Mod}\left(13\,\left[3\,1\,1\,9\,1\right]\,'\mathrm{transpose}'\,\mathrm{dtype}\right)$

$\mathrm{V2}≔\left[\begin{array}{ccccc}3& 1& 1& 9& 1\end{array}\right]$

$\mathrm{Multiply}\left(13\,\mathrm{V1}\,\mathrm{V2}\right)$

$\left[\begin{array}{ccccc}2& 5& 5& 6& 5\\ 6& 2& 2& 5& 2\\ 9& 3& 3& 1& 3\\ 12& 4& 4& 10& 4\\ 3& 1& 1& 9& 1\end{array}\right]$

$\mathrm{Multiply}\left(13\,\mathrm{V2}\,\mathrm{V1}\right)$

$5$

$\mathrm{Multiply}\left(13\,\mathrm{V1}\,'\mathrm{transpose}'\,\mathrm{V1}\right)$

$3$

$\mathrm{Multiply}\left(13\,\mathrm{V1}\,\mathrm{V1}\right)$

Error, (in LinearAlgebra:-Modular:-Multiply) argument 3 has a row dimension where prior arguments require a row object

Dumas, Jean-Guillaume, and Pernet, Clement. "Efficient Finite Field Arithmetic for Linear Algebra." Presentation at University of Waterloo. 2001.