LUApply - Maple Help

LinearAlgebra[Modular]

 LUApply
 apply PLU Decomposition to a mod m Matrix or Vector

 Calling Sequence LUApply(m, A, pvec, B)

Parameters

 m - modulus A - mod m Matrix (from LUDecomposition) pvec - permutation vector (from LUDecomposition) B - mod m Matrix or Vector representing right-hand side of problem

Description

 • The LUApply function applies the permutation pvec and the forward and backward substitutions encoded in A directly to the right-hand side mod m Matrix or Vector B, where pvec and A are the output of the LUDecomposition function.
 B must have the same number of rows as columns in A.
 • The function works directly on B, returning the solution in B on successful completion. If the function fails, B can be altered.
 • LUApply is simply the application of Permute, ForwardSubstitute, and then BackwardSubstitute.
 • This command is part of the LinearAlgebra[Modular] package, so it can be used in the form LUApply(..) only after executing the command with(LinearAlgebra[Modular]).  However, it can always be used in the form LinearAlgebra[Modular][LUApply](..).

Examples

Compute LU decomposition of a random 5 x 5 Matrix, and use LUApply to obtain a solution.

 > $\mathrm{with}\left(\mathrm{LinearAlgebra}\left[\mathrm{Modular}\right]\right):$
 > $p≔97$
 ${p}{≔}{97}$ (1)
 > $A≔\mathrm{Mod}\left(p,\mathrm{Matrix}\left(5,5,\left(i,j\right)↦\mathrm{rand}\left(\right)\right),\mathrm{integer}\left[\right]\right):$
 > $A$
 $\left[\begin{array}{ccccc}{77}& {96}& {10}& {86}& {58}\\ {36}& {80}& {22}& {44}& {39}\\ {60}& {39}& {43}& {12}& {55}\\ {2}& {24}& {71}& {45}& {29}\\ {21}& {48}& {7}& {33}& {57}\end{array}\right]$ (2)
 > $\mathrm{A2}≔\mathrm{Copy}\left(p,A\right):$
 > $\mathrm{pv}≔\mathrm{Vector}\left(4\right):$
 > $\mathrm{LUDecomposition}\left(p,\mathrm{A2},\mathrm{pv},0\right):$
 > $\mathrm{A2},\mathrm{pv}$
 $\left[\begin{array}{ccccc}{77}& {96}& {10}& {86}& {58}\\ {37}& {20}& {40}& {63}& {27}\\ {94}& {60}& {1}& {79}& {64}\\ {29}& {56}& {63}& {7}& {78}\\ {62}& {54}& {40}& {10}& {5}\end{array}\right]{,}\left[\begin{array}{c}{1}\\ {2}\\ {3}\\ {4}\end{array}\right]$ (3)
 > $B≔\mathrm{Mod}\left(p,\mathrm{Matrix}\left(5,2,\left(i,j\right)↦\mathrm{rand}\left(\right)\right),\mathrm{integer}\left[\right]\right)$
 ${B}{≔}\left[\begin{array}{cc}{65}& {16}\\ {93}& {96}\\ {71}& {44}\\ {70}& {58}\\ {25}& {29}\end{array}\right]$ (4)
 > $X≔\mathrm{Copy}\left(p,B\right):$
 > $\mathrm{LUApply}\left(p,\mathrm{A2},\mathrm{pv},X\right):$
 > $X$
 $\left[\begin{array}{cc}{11}& {37}\\ {12}& {20}\\ {57}& {11}\\ {83}& {68}\\ {1}& {11}\end{array}\right]$ (5)

Check the solution.

 > $\mathrm{Multiply}\left(p,A,X\right)-B$
 $\left[\begin{array}{cc}{0}& {0}\\ {0}& {0}\\ {0}& {0}\\ {0}& {0}\\ {0}& {0}\end{array}\right]$ (6)

Use float[8] with a nontrivial permutation.

 > $p≔13:$
 > $A≔\mathrm{Mod}\left(13,\left[\left[0,0,12\right],\left[12,0,3\right],\left[1,1,1\right]\right],\mathrm{float}\left[8\right]\right)$
 ${A}{≔}\left[\begin{array}{ccc}{0.}& {0.}& {12.}\\ {12.}& {0.}& {3.}\\ {1.}& {1.}& {1.}\end{array}\right]$ (7)
 > $\mathrm{A2}≔\mathrm{Copy}\left(p,A\right):$
 > $\mathrm{pv}≔\mathrm{Vector}\left(2\right):$
 > $\mathrm{LUDecomposition}\left(p,\mathrm{A2},\mathrm{pv},0\right):$
 > $\mathrm{A2},\mathrm{pv}$
 $\left[\begin{array}{ccc}{12.}& {0.}& {3.}\\ {12.}& {1.}& {4.}\\ {0.}& {0.}& {12.}\end{array}\right]{,}\left[\begin{array}{c}{2}\\ {3}\end{array}\right]$ (8)

Now apply to a random vector and check it.

 > $B≔\mathrm{Mod}\left(p,\mathrm{Vector}\left(3,i↦\mathrm{rand}\left(\right)\right),\mathrm{float}\left[8\right]\right)$
 ${B}{≔}\left[\begin{array}{c}{5.}\\ {3.}\\ {5.}\end{array}\right]$ (9)
 > $X≔\mathrm{Copy}\left(p,B\right):$
 > $\mathrm{LUApply}\left(p,\mathrm{A2},\mathrm{pv},X\right):$
 > $X$
 $\left[\begin{array}{c}{8.}\\ {2.}\\ {8.}\end{array}\right]$ (10)
 > $\mathrm{Multiply}\left(p,A,X\right)-B$
 $\left[\begin{array}{c}{0.}\\ {0.}\\ {0.}\end{array}\right]$ (11)