Overview of the Modular Subpackage of LinearAlgebra - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

Overview of the Modular Subpackage of LinearAlgebra

 

Calling Sequence

Description

List of Modular Subpackage Commands

Examples

References

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 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, integer 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.

  

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.

 

 

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 row-reduction on a mod m Matrix (no transpose operation).

Swap

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.

 

 

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

 

 

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:

 

 

IntegerCharacteristicPolynomial

Compute the characteristic polynomial of a square

 

integer matrix.

IntegerDeterminant

Compute the determinant of a square

 

integer matrix.

IntegerLinearSolve

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 10x10float8 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 C_order matrices (when the data is large), so if efficiency is a major consideration, applications should restrict to use of C_order.

Examples

A row reduction example.

withLinearAlgebraModular

AddMultiple,Adjoint,BackwardSubstitute,Basis,CharacteristicPolynomial,ChineseRemainder,Copy,Create,Determinant,Fill,ForwardSubstitute,Identity,IntegerCharacteristicPolynomial,IntegerDeterminant,IntegerLinearSolve,Inverse,LUApply,LUDecomposition,LinearSolve,MatBasis,MatGcd,MatrixPower,Mod,Multiply,Permute,Random,Rank,RankProfile,RowEchelonTransform,RowReduce,Swap,Transpose,ZigZag

(1)

MatMod13,1,x,x2,x2,3,xx1,x=4,float8

Mat1.4.3.2.3.10.

(2)

RowReduce13,Mat,2,3,3,'det',0,0,0,0,true:

Mat

1.0.1.0.1.7.

(3)

Transpose13,Mat

1.0.0.1.1.7.

(4)

A multiplication example.

dtypeintegerkerneloptswordsize8:

V1Mod13,5,2,3,4,1,dtype

V152341

(5)

V2Mod13,3,1,1,9,1,'transpose',dtype

V231191

(6)

Multiply13,V1,V2

255656225293313124410431191

(7)

Multiply13,V2,V1

5

(8)

Multiply13,V1,'transpose',V1

3

(9)

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

Multiply13,V1,V1

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

References

  

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

See Also

LinearAlgebra/Details

module

with