
Calling Sequence


LinearAlgebra[Modular][command](arguments)
command(arguments)


Description


•

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..m1$) 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 32bit versions of Maple, the datatype is integer[4], and it allows moduli in the range 2 .. 2^161 or $2..65535$.


For 64bit versions of Maple, the datatype is integer[8], and it allows moduli in the range 2 .. 2^321 or $2..4294967295$. When specifying the use of this datatype, $\mathrm{integer}\left[\right]$ can be used to make code more easily portable between 32bit and 64bit 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^251 or $2..33554431$, which provides a larger range than the integer[4] datatype for 32bit 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.


As the underlying implementation of the Modular subpackage is a module, it is also possible to use the form LinearAlgebra[Modular]:command or LinearAlgebra:Modular:command to access a command from the package, the latter of which is recommended for use in programming. For more information, see Module Members.



List of Modular Subpackage Commands


•

The lowlevel commands (basic operations) allow for specification of a SubMatrix or SubVector 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.



AddMultiple

Add a multiple of a mod m Matrix or Vector to another.

Copy

Copy a mod m Matrix or Vector.

Create

Create a new mod m Matrix or Vector.

Fill

Fill a mod m Matrix or Vector with a specified value.

Mod

Evaluate the input mod m, and possibly a set of


evaluations; outputs a mod m Matrix or Vector.

Multiply

Multiply mod m Matrices or Vectors.

RowReduce

Perform rowreduction on a mod m Matrix (no transpose operation).

Swap

Exchange data between two mod m Matrices or Vectors.





•

The midlevel commands allow for inplace 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.



BackwardSubstitute

Apply backward substitution with a square upper


triangular mod m Matrix to a mod m Matrix or Vector.

ForwardSubstitute

Apply forward substitution with a square lower


triangular mod m Matrix to a mod m Matrix or Vector.

LUApply

Apply the result of $\mathrm{LUDecomposition}$ to a


mod m Matrix or Vector.

LUDecomposition

Perform LU decomposition on a mod m Matrix.

MatBasis

Compute a basis (and optionally the nullspace) of


the Vectors present in the rows of the input Matrix.

MatGcd

Compute the GCD of the polynomials with coefficients


present in the rows of the input Matrix.

Permute

Apply a permutation to a mod m Matrix or Vector.

RowEchelonTransform

Compute a row echelon transform of a mod m Matrix.

ZigZag

Compute the ZigZag form of a square mod m Matrix.





•

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



Adjoint

Compute the Adjoint of a mod m Matrix.

Basis

Compute a basis (and optionally the nullspace)


of a list or set of mod m Vectors, or Vectors present


in a mod m Matrix.

CharacteristicPolynomial

Compute the characteristic polynomial of a matrix


mod m.

ChineseRemainder

Apply the Chinese remainder algorithm to a list of


mod m Matrices or Vectors, or update an existing


Chinese remainder Matrix or Vector with new images.

Determinant

Compute the determinant of a square mod m Matrix.

Identity

Construct a mod m identity Matrix.

Inverse

Compute the Inverse of a mod m Matrix.

LinearSolve

Obtain the solution of a mod m Matrix.

MatrixPower

Compute a power of a square mod m Matrix.

Rank

Compute the Rank of a mod m Matrix.

RankProfile

Compute the Rank Profile of a mod m Matrix.

Transpose

Compute the transpose of a mod m Matrix.





•

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

•

All low and midlevel 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}$.



Examples


A row reduction example.
>

$\mathrm{with}\left(\mathrm{LinearAlgebra}\left[\mathrm{Modular}\right]\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]$
 (1) 
>

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

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

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

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

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

$\left[\begin{array}{cc}{1.}& {0.}\\ {0.}& {1.}\\ {1.}& {7.}\end{array}\right]$
 (4) 
A multiplication example.
>

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

>

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

${\mathrm{V1}}{\u2254}\left[\begin{array}{c}{5}\\ {2}\\ {3}\\ {4}\\ {1}\end{array}\right]$
 (5) 
>

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

${\mathrm{V2}}{\u2254}\left[\begin{array}{ccccc}{3}& {1}& {1}& {9}& {1}\end{array}\right]$
 (6) 
>

$\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]$
 (7) 
>

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

>

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

This is a problem. Notice that the orientation of the vectors do not match.
>

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



References



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



