LinearAlgebra[Modular] - Maple Programming Help

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

LinearAlgebra[Modular]

 add multiple of a mod m Matrix or Vector to another

 Calling Sequence AddMultiple(m, mult, A, B, order, 'sparse') AddMultiple(m, mult, A, B, C, 'sparse')

Parameters

 m - modulus A - Matrix or Vector, including subspec B - Matrix or Vector, including subspec order - ordering of output object sparse - (optional) controls behavior of operation mult - (optional) multiplier, default is 1 C - output Matrix or Vector, including subspec

Description

 • The AddMultiple function performs the operation $B\mathrm{mult}+A$ placing the output in a new object, or in C, depending on calling sequence. All of A, B, and C must be mod m Matrices or Vectors, and mult must be a scalar.
 The first calling sequence returns a new mod m Matrix or Vector for the result with the specified ordering, order, or the ordering of the input objects A and B.
 Note: If A and B have different ordering, order must be specified.
 The second calling sequence places the output of the computation into C, returning NULL.
 Note: The parameter C can be the same Matrix or Vector as A or B as long as the operation is performed with direct overlap.  For example, if A and C are the same Matrix, the operation involving the entry ${A}_{i,j}$ must have the result going to ${C}_{i,j}$.
 • The multiplier, mult, is an optional parameter.  However, if it is not specified, it is assumed to be 1. The multiplier must be in the range $0..m-1$.  This function can be used to perform Matrix or Vector subtraction by the selection of $\mathrm{mult}=m-1$. This is coded efficiently, that is, without multiplication.
 • If specified, the optional keyword 'sparse', is only applicable if the multiplier is not $1$ or $m-1$ and the datatype is a hardware datatype.  It indicates that the algorithm checks for zero entries before performing multiplications. This typically provides an efficiency gain if matrices have 10% or more entries in B equal to zero. This is not implemented for the integer datatype, as it typically provides very little gain.
 Note: In cases for which sparse does not apply but has been specified, the option is ignored.
 • The AddMultiple function allows the use of sub-Matrix and sub-Vector specifications for both input and output Matrices or Vectors. For example, the function can be used to add a row of a Matrix to a row Vector, placing the result in the column of another Matrix.
 • Note: If the used portion of A or B, and C overlap, but not directly, the behavior of AddMultiple is undefined.
 • This command is part of the LinearAlgebra[Modular] package, so it can be used in the form AddMultiple(..) only after executing the command with(LinearAlgebra[Modular]).  However, it can always be used in the form LinearAlgebra[Modular][AddMultiple](..).

Examples

 > $\mathrm{with}\left(\mathrm{LinearAlgebra}[\mathrm{Modular}]\right):$
 > $A≔\mathrm{Mod}\left(13,\mathrm{Matrix}\left(4,4,\left(i,j\right)→\mathrm{rand}\left(\right)\right),\mathrm{integer}[]\right)$
 ${A}{≔}\left[\begin{array}{rrrr}{10}& {0}& {8}& {12}\\ {2}& {6}& {0}& {11}\\ {9}& {2}& {11}& {7}\\ {4}& {11}& {12}& {11}\end{array}\right]$ (1)
 > $B≔\mathrm{Mod}\left(13,\mathrm{Matrix}\left(4,4,\left(i,j\right)→\mathbf{if}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}i=j\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{then}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}1\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{else}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}0\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{end if}\right),\mathrm{integer}[]\right)$
 ${B}{≔}\left[\begin{array}{rrrr}{1}& {0}& {0}& {0}\\ {0}& {1}& {0}& {0}\\ {0}& {0}& {1}& {0}\\ {0}& {0}& {0}& {1}\end{array}\right]$ (2)

Default multiplier and new output Matrix (A+B).

 > $\mathrm{AddMultiple}\left(13,A,B\right)$
 $\left[\begin{array}{rrrr}{11}& {0}& {8}& {12}\\ {2}& {7}& {0}& {11}\\ {9}& {2}& {12}& {7}\\ {4}& {11}& {12}& {12}\end{array}\right]$ (3)

Chosen multiplier of 2 (A+2*B).

 > $\mathrm{AddMultiple}\left(13,2,A,B\right)$
 $\left[\begin{array}{rrrr}{12}& {0}& {8}& {12}\\ {2}& {8}& {0}& {11}\\ {9}& {2}& {0}& {7}\\ {4}& {11}& {12}& {0}\end{array}\right]$ (4)

Replace A with the result.

 > $\mathrm{AddMultiple}\left(13,2,A,B,A\right):$
 > $A$
 $\left[\begin{array}{rrrr}{12}& {0}& {8}& {12}\\ {2}& {8}& {0}& {11}\\ {9}& {2}& {0}& {7}\\ {4}& {11}& {12}& {0}\end{array}\right]$ (5)

Add row 3 of A to row 2 of A, with output in column 1 of B.

 > $\mathrm{AddMultiple}\left(13,A,3,'\mathrm{transpose}',A,2,'\mathrm{transpose}',B,1..-1,1\right):$
 > $A,B$
 $\left[\begin{array}{rrrr}{12}& {0}& {8}& {12}\\ {2}& {8}& {0}& {11}\\ {9}& {2}& {0}& {7}\\ {4}& {11}& {12}& {0}\end{array}\right]{,}\left[\begin{array}{rrrr}{11}& {0}& {0}& {0}\\ {10}& {1}& {0}& {0}\\ {0}& {0}& {1}& {0}\\ {5}& {0}& {0}& {1}\end{array}\right]$ (6)

Construct a larger Matrix and identity Matrix, using larger modulus.

 > $N≔100:$
 > $p≔65535:$
 > $A≔\mathrm{Mod}\left(p,\mathrm{Matrix}\left(N,N,\left(i,j\right)→\mathrm{rand}\left(\right)\right),\mathrm{float}[8]\right)$
 ${A}{≔}\left[\begin{array}{c}{\mathrm{100 x 100}}{\mathrm{Matrix}}\\ {\mathrm{Data Type:}}{\mathrm{float}}{[}{8}{]}\\ {\mathrm{Storage:}}{\mathrm{rectangular}}\\ {\mathrm{Order:}}{\mathrm{C_order}}\end{array}\right]$ (7)
 > $B≔\mathrm{Mod}\left(p,\mathrm{Matrix}\left(N,N,\left(i,j\right)→\mathbf{if}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}i=j\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{then}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}1\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{else}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}0\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{end if}\right),\mathrm{float}[8]\right)$
 ${B}{≔}\left[\begin{array}{c}{\mathrm{100 x 100}}{\mathrm{Matrix}}\\ {\mathrm{Data Type:}}{\mathrm{float}}{[}{8}{]}\\ {\mathrm{Storage:}}{\mathrm{rectangular}}\\ {\mathrm{Order:}}{\mathrm{C_order}}\end{array}\right]$ (8)

Time addition of 327*B to A 2000 times.

 > $t≔\mathrm{time}\left(\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}i\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{to}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}2000\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{AddMultiple}\left(p,327,A,B,A\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{end do}:$$\mathrm{time}\left(\right)-t$
 ${0.150}$ (9)

Time addition of 327*B to A 2000 times using sparse.

 > $t≔\mathrm{time}\left(\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}i\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{to}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}2000\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{AddMultiple}\left(p,327,A,B,A,'\mathrm{sparse}'\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{end do}:$$\mathrm{time}\left(\right)-t$
 ${0.047}$ (10)