 Overview of the Modular Subpackage of LinearAlgebra - Maple Programming Help

Home : Support : Online Help : Mathematics : Linear Algebra : LinearAlgebra Package : Modular Subpackage : LinearAlgebra/Modular

Overview of the Modular Subpackage of LinearAlgebra

 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..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/integer and float are implemented efficiently through use of hardware data and compiled routines. The remaining datatype is integer, which uses native Maple integers.
 The integer/integer datatype is dependent on the hardware on which it is running. For 32-bit versions of Maple, the datatype is integer, and it allows moduli in the range 2 .. 2^16-1 or $2..65535$.
 For 64-bit versions of Maple, the datatype is integer, 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 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 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/integer, float, and integer). Construction of a 10 by 10 Matrix of float data to use with the subpackage can be accomplished with the Matrix constructor, that is, Matrix(10, 10, datatype=float, 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 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.

 Add a multiple of a mod m Matrix or Vector to another. Copy a mod m Matrix or Vector. Create a new mod m Matrix or Vector. Fill a mod m Matrix or Vector with a specified value. Evaluate the input mod m, and possibly a set of evaluations; outputs a mod m Matrix or Vector. Multiply mod m Matrices or Vectors. Perform row-reduction on a mod m Matrix (no transpose operation). Exchange data between two mod m Matrices or Vectors.

 • 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.

 Apply backward substitution with a square upper triangular mod m Matrix to a mod m Matrix or Vector. Apply forward substitution with a square lower triangular mod m Matrix to a mod m Matrix or Vector. Apply the result of $\mathrm{LUDecomposition}$ to a mod m Matrix or Vector. Perform LU decomposition on a mod m Matrix. Compute a basis (and optionally the nullspace) of the Vectors present in the rows of the input Matrix. Compute the GCD of the polynomials with coefficients present in the rows of the input Matrix. Apply a permutation to a mod m Matrix or Vector. Compute a row echelon transform of a mod m Matrix. Compute the ZigZag form of a square mod m Matrix.

 • 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.

 Compute the Adjoint of a mod m Matrix. Compute a basis (and optionally the nullspace) of a list or set of mod m Vectors, or Vectors present in a mod m Matrix. Compute the characteristic polynomial of a matrix mod m. 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. Compute the determinant of a square mod m Matrix. Construct a mod m identity Matrix. Compute the Inverse of a mod m Matrix. Obtain the solution of a mod m Matrix. Compute a power of a square mod m Matrix. Compute the Rank of a mod m Matrix. Compute the Rank Profile of a mod m Matrix. 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:

 Compute the characteristic polynomial of a square integer matrix. Compute the determinant of a square integer matrix. Compute the rational solution of an integer linear matrix problem.

 • 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}$.

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}≔\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]$ (2)
 > $\mathrm{RowReduce}\left(13,\mathrm{Mat},2,3,3,'\mathrm{det}',0,0,0,0,\mathrm{true}\right):$
 > $\mathrm{Mat}$
 $\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}≔\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]$ (5)
 > $\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]$ (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)$
 ${5}$ (8)
 > $\mathrm{Multiply}\left(13,\mathrm{V1},'\mathrm{transpose}',\mathrm{V1}\right)$
 ${3}$ (9)

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, Jean-Guillaume, and Pernet, Clement. "Efficient Finite Field Arithmetic for Linear Algebra." Presentation at University of Waterloo. 2001.