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 $\mathrm{mult}B+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}\left[\mathrm{Modular}\right]\right):$
 > $A≔\mathrm{Mod}\left(13,\mathrm{Matrix}\left(4,4,\left(i,j\right)↦\mathrm{rand}\left(\right)\right),\mathrm{integer}\left[\right]\right)$
 ${A}{≔}\left[\begin{array}{cccc}{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.3em}{0.0ex}}i=j\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{then}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}1\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{else}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}0\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{if}\right),\mathrm{integer}\left[\right]\right)$
 ${B}{≔}\left[\begin{array}{cccc}{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}{cccc}{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}{cccc}{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}{cccc}{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}{cccc}{12}& {0}& {8}& {12}\\ {2}& {8}& {0}& {11}\\ {9}& {2}& {0}& {7}\\ {4}& {11}& {12}& {0}\end{array}\right]{,}\left[\begin{array}{cccc}{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}\left[8\right]\right)$
 ${A}{≔}\begin{array}{c}\left[\begin{array}{ccccccccccc}{11389.}& {46583.}& {35619.}& {55627.}& {8333.}& {58193.}& {17153.}& {8373.}& {52522.}& {23726.}& {\dots }\\ {44895.}& {6541.}& {32238.}& {16633.}& {10648.}& {63397.}& {19275.}& {64312.}& {56077.}& {58182.}& {\dots }\\ {64903.}& {64302.}& {19646.}& {18892.}& {49105.}& {15561.}& {6011.}& {6642.}& {14428.}& {948.}& {\dots }\\ {19988.}& {58098.}& {58338.}& {27655.}& {38255.}& {63581.}& {39333.}& {24939.}& {47194.}& {35517.}& {\dots }\\ {64615.}& {24982.}& {19867.}& {29792.}& {45897.}& {32976.}& {55062.}& {29390.}& {36394.}& {2517.}& {\dots }\\ {46329.}& {32483.}& {63057.}& {1464.}& {4135.}& {39144.}& {64901.}& {51178.}& {5572.}& {41509.}& {\dots }\\ {38220.}& {34732.}& {29262.}& {10252.}& {1409.}& {61105.}& {31465.}& {28004.}& {63254.}& {13677.}& {\dots }\\ {27312.}& {54051.}& {12354.}& {45067.}& {5724.}& {8267.}& {60093.}& {13710.}& {29697.}& {48342.}& {\dots }\\ {14619.}& {19190.}& {42094.}& {28726.}& {44834.}& {44709.}& {17258.}& {11606.}& {24997.}& {54504.}& {\dots }\\ {65230.}& {7515.}& {23936.}& {51591.}& {65276.}& {41391.}& {2571.}& {8536.}& {52753.}& {18709.}& {\dots }\\ {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {}\end{array}\right]\\ \hfill {\text{100 × 100 Matrix}}\end{array}$ (7)
 > $B≔\mathrm{Mod}\left(p,\mathrm{Matrix}\left(N,N,\left(i,j\right)↦\mathbf{if}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}i=j\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{then}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}1\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{else}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}0\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{if}\right),\mathrm{float}\left[8\right]\right)$
 ${B}{≔}\begin{array}{c}\left[\begin{array}{ccccccccccc}{1.}& {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {\dots }\\ {0.}& {1.}& {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {\dots }\\ {0.}& {0.}& {1.}& {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {\dots }\\ {0.}& {0.}& {0.}& {1.}& {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {\dots }\\ {0.}& {0.}& {0.}& {0.}& {1.}& {0.}& {0.}& {0.}& {0.}& {0.}& {\dots }\\ {0.}& {0.}& {0.}& {0.}& {0.}& {1.}& {0.}& {0.}& {0.}& {0.}& {\dots }\\ {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {1.}& {0.}& {0.}& {0.}& {\dots }\\ {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {1.}& {0.}& {0.}& {\dots }\\ {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {1.}& {0.}& {\dots }\\ {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {0.}& {1.}& {\dots }\\ {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {⋮}& {}\end{array}\right]\\ \hfill {\text{100 × 100 Matrix}}\end{array}$ (8)

Time addition of 327*B to A 2000 times.

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

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

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