LinearAlgebra[Modular] - Maple Programming Help

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

LinearAlgebra[Modular]

 ForwardSubstitute
 apply in-place forward substitution from a lower triangular mod m Matrix to a mod m Matrix or Vector

 Calling Sequence ForwardSubstitute(m, A, B, diagflag)

Parameters

 m - modulus A - mod m lower triangular Matrix B - mod m Matrix or Vector to which to apply forward substitution diagflag - boolean; indicate whether to assume diagonal entries are 1

Description

 • The ForwardSubstitute function applies the forward substitution described by the lower triangular part of the square mod m Matrix A to the mod m Matrix or Vector B.
 Note: It is assumed that A is in lower triangular form, or that only the lower triangular part is relevant and the upper triangular part of A is completely ignored.
 The mod m Matrix or Vector B must have the same number of rows as there are columns of A.
 • Application of forward substitution requires that m is prime, but in some cases it can be computed if m is composite. If it cannot be computed for m composite, an error message is returned.
 • The diagflag parameter is a boolean that indicates if the diagonal of the lower triangular Matrix is considered to be the identity (true), or used in the forward substitution (false). This option is most useful when applying forward substitution from a compact LU decomposition (see LUDecomposition), where the diagonal of the lower triangular factor is the identity, and is not explicitly stored.
 • The ForwardSubstitute function is used as one of the steps in the LUApply function.
 • This command is part of the LinearAlgebra[Modular] package, so it can be used in the form ForwardSubstitute(..) only after executing the command with(LinearAlgebra[Modular]).  However, it can always be used in the form LinearAlgebra[Modular][ForwardSubstitute](..).

Examples

Construct and solve a lower triangular system.

 > $\mathrm{with}\left(\mathrm{LinearAlgebra}[\mathrm{Modular}]\right):$
 > $p≔97$
 ${p}{:=}{97}$ (1)
 > $A≔\mathrm{Mod}\left(p,\mathrm{Matrix}\left(4,4,\left(i,j\right)→\mathbf{if}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}j\le i\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{then}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{rand}\left(\right)\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≔\mathrm{Mod}\left(p,\mathrm{Matrix}\left(4,2,\left(i,j\right)→\mathrm{rand}\left(\right)\right),\mathrm{integer}[]\right):$
 > $A,B$
 $\left[\begin{array}{rrrr}{77}& {0}& {0}& {0}\\ {96}& {10}& {0}& {0}\\ {86}& {58}& {36}& {0}\\ {80}& {22}& {44}& {39}\end{array}\right]{,}\left[\begin{array}{rr}{60}& {39}\\ {43}& {12}\\ {55}& {2}\\ {24}& {71}\end{array}\right]$ (2)
 > $X≔\mathrm{Copy}\left(p,B\right):$
 > $\mathrm{ForwardSubstitute}\left(p,A,X,\mathrm{false}\right):$
 > $X$
 $\left[\begin{array}{rr}{94}& {32}\\ {4}& {82}\\ {75}& {34}\\ {94}& {58}\end{array}\right]$ (3)
 > $\mathrm{Multiply}\left(p,A,X\right)-B$
 $\left[\begin{array}{rr}{0}& {0}\\ {0}& {0}\\ {0}& {0}\\ {0}& {0}\end{array}\right]$ (4)

Lower triangular system with assumed diagonal of 1.

 > $p≔97$
 ${p}{:=}{97}$ (5)
 > $A≔\mathrm{Mod}\left(p,\mathrm{Matrix}\left(4,4,\left(i,j\right)→\mathbf{if}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}j
 > $B≔\mathrm{Mod}\left(p,\mathrm{Vector}[\mathrm{column}]\left(4,i→\mathrm{rand}\left(\right)\right),\mathrm{float}[8]\right):$
 > $A,B$
 $\left[\begin{array}{cccc}{0.}& {0.}& {0.}& {0.}\\ {45.}& {0.}& {0.}& {0.}\\ {29.}& {21.}& {0.}& {0.}\\ {48.}& {7.}& {33.}& {0.}\end{array}\right]{,}\left[\begin{array}{c}{57.}\\ {65.}\\ {16.}\\ {93.}\end{array}\right]$ (6)
 > $X≔\mathrm{Copy}\left(p,B\right):$
 > $\mathrm{ForwardSubstitute}\left(p,A,X,\mathrm{true}\right):$
 > $X$
 $\left[\begin{array}{c}{57.}\\ {22.}\\ {35.}\\ {25.}\end{array}\right]$ (7)
 > $\mathrm{AddMultiple}\left(p,\mathrm{Multiply}\left(p,A,X\right),X\right)-B$
 $\left[\begin{array}{c}{0.}\\ {0.}\\ {0.}\\ {0.}\end{array}\right]$ (8)