compute in-place PLU Decomposition of a mod m Matrix - Maple Help

Online Help

All Products    Maple    MapleSim


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

LinearAlgebra[Modular][LUDecomposition] - compute in-place PLU Decomposition of a mod m Matrix

Calling Sequence

LUDecomposition(m, A, pvec, det)

Parameters

m

-

modulus

A

-

mod m Matrix

pvec

-

permutation vector

det

-

name for determinant or 0

Description

• 

The LUDecomposition function computes an in-place PLU decomposition of a square mod m Matrix A placing the permutation information in pvec. Optionally, the determinant can also be computed.

• 

Computation of an LU decomposition requires that m is a prime, but in some cases it can be computed when m is composite. If it cannot be computed for m composite, an error message returns.

• 

The pvec parameter must be a Vector of type integer[4]/integer[8], integer, or anything, having at least n1 entries, where the Matrix A is nxn.

• 

If the determinant of the Matrix being decomposed is required, specify det as a name. Otherwise, specify as the value 0. On output, the name specified for det is assigned the value of the determinant.

  

Note: If the determinant is not required, set det to zero to avoid unnecessary calculations.

• 

Since the computation is performed in-place, the LU decomposition is stored in compact form. On successful completion, the upper triangular Matrix is stored in the upper triangular part of A, and the lower triangular Matrix is stored in the lower triangular part of A, replacing diagonal entries with 1.

• 

The permutation is also stored in a compact form in pvec. This vector can be interpreted as an ordered list of instructions on how to apply a permutation, where the first entry describes the row exchange required for the first row, the second describes the row exchange required for the second row, etcetera.

  

For example, for a 4x4 Matrix the permutation vector must have 3 elements. If these are [1, 4, 4], this corresponds to the following exchanges in the given order: 1<=>1, 2<=>4, 3<=>4.

  

Unlike a permutation Matrix, this format does not result in a unique representation for a permutation. For example, for a 4x4 Matrix, the identity permutation is given by [1,2,3], [3,2,1], [2,1,3], etcetera. Use of this format makes application of the permutation (or its inverse) to a Matrix or Vector quite simple. If the permutation Matrix is required, it can be obtained through application of the Permute function on an identity Matrix.

• 

After obtaining the LU decomposition and permutation vector, it can be applied to the right-hand side of the original system (a mod m Matrix or Vector) to obtain the solution using the LUApply function, or explicitly by using Permute, ForwardSubstitute, and then BackwardSubstitute.

• 

This command is part of the LinearAlgebra[Modular] package, so it can be used in the form LUDecomposition(..) only after executing the command with(LinearAlgebra[Modular]).  However, it can always be used in the form LinearAlgebra[Modular][LUDecomposition](..).

Examples

Compute LU decomposition of a random 5 x 5 Matrix.

withLinearAlgebra&lsqb;Modular&rsqb;&colon;

p:=97

p:=97

(1)

A:=Modp&comma;Matrix5&comma;5&comma;i&comma;j&rarr;rand&comma;integer&lsqb;&rsqb;&colon;

A

779610865836802244396039431255224714529214873357

(2)

A2:=Copyp&comma;A&colon;

pv:=Vector4&colon;

LUDecompositionp&comma;A2&comma;pv&comma;&apos;det&apos;&colon;

A2&comma;pv&comma;det

77961086583720406327946017964295663778625440105&comma;1234&comma;65

(3)

Check the determinant.

modpLinearAlgebra:-DeterminantMatrix5&comma;5&comma;i&comma;j&rarr;Ai&comma;j&comma;p

65

(4)

Construct a 'B' in A X = B, and compute X.

B:=Modp&comma;Matrix5&comma;2&comma;i&comma;j&rarr;rand&comma;integer&lsqb;&rsqb;

B:=65169396714470582529

(5)

X:=Copyp&comma;B&colon;

LUApplyp&comma;A2&comma;pv&comma;X&colon;

X

1137122057118368111

(6)

Check it.

Multiplyp&comma;A&comma;X&comma;B

65169396714470582529&comma;65169396714470582529

(7)

Using float[8] with a nontrivial permutation

p:=13&colon;

A:=Mod13&comma;0&comma;0&comma;12&comma;12&comma;0&comma;3&comma;1&comma;1&comma;1&comma;float8

A:=0.0.12.12.0.3.1.1.1.

(8)

A2:=Copyp&comma;A&colon;

pv:=Vector2&colon;

LUDecompositionp&comma;A2&comma;pv&comma;0&colon;

A2&comma;pv

12.0.3.12.1.4.0.0.12.&comma;23

(9)

Now apply it to a random Vector and check.

B:=Modp&comma;Vector3&comma;i&rarr;rand&comma;float8

B:=5.3.5.

(10)

X:=Copyp&comma;B&colon;

Apply it manually.

Permutep&comma;pv&comma;X&comma;true&comma;false&colon;

ForwardSubstitutep&comma;A2&comma;X&comma;true&colon;

BackwardSubstitutep&comma;A2&comma;X&colon;

X

8.2.8.

(11)

Multiplyp&comma;A&comma;X&comma;B

5.3.5.&comma;5.3.5.

(12)

See Also

LinearAlgebra/Details, LinearAlgebra[Modular], LinearAlgebra[Modular][BackwardSubstitute], LinearAlgebra[Modular][Copy], LinearAlgebra[Modular][ForwardSubstitute], LinearAlgebra[Modular][LUApply], LinearAlgebra[Modular][Mod], LinearAlgebra[Modular][Multiply], LinearAlgebra[Modular][Permute]


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam