LinearAlgebra[Modular] - Maple Help

Online Help

All Products    Maple    MapleSim


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

LinearAlgebra[Modular]

  

CharacteristicPolynomial

  

Compute the characteristic polynomial of a square matrix mod p

 

Calling Sequence

Parameters

Description

Examples

Calling Sequence

CharacteristicPolynomial(m, A, lambda)

Parameters

m

-

modulus

A

-

square matrix

lambda

-

variable name to use for characteristic polynomial

Description

• 

The CharacteristicPolynomial function computes the characteristic polynomial of a matrix mod m. Note that the matrix A need not have entries in the positive range 0..m1, as the routine needs to make a copy of the matrix for the computation, and does so using Mod. Upon successful completion, the characteristic polynomial of A mod m in lambda is returned.

• 

A number of different algorithms and implementations are in use, each with significantly different efficiency, so it is important to describe these here.

  

If m is a prime number with fewer than 100 digits (the digit limitation is present only to guarantee that the primality check is not too expensive) then the Hessenberg algorithm is used. This is a reduction-like routine, in which the matrix is 'reduced' to Hessenberg form, and the characteristic polynomial is computed from this form.

  

Furthermore, if the prime is sufficiently small so that the Modular package can work with a hardware datatype (either integer[] or float[8]), then an efficient external routine is used for the computation, making it quite fast.

  

In the event that the modulus m is not prime, or greater than 100 digits in length, the Berkowitz algorithm is used. Unlike the Hessenberg implementation, the Berkowitz implementation uses no external code, so it is noticeably slower for comparable problems, as demonstrated in the examples.

• 

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

Examples

withLinearAlgebra[Modular]:

AMatrix30,30,i,j→rand

A:= 30 x 30 MatrixData Type: anythingStorage: rectangularOrder: Fortran_order

(1)

t0time:

p0LinearAlgebra:-CharacteristicPolynomialA,x:

t0timet0

t0:=0.030

(2)

Compute the characteristic polynomial using external Hessenberg and Berkowitz, and compare the timings.

First Hessenberg with prime modulus

m1ithprime4600

m1:=44201

(3)

tHtime:

p1CharacteristicPolynomialm1,A,x

p1:=x30+2002x29+26760x28+39582x27+40328x26+17238x25+38348x24+11836x23+15733x22+29600x21+29719x20+9058x19+29063x18+33642x17+28407x16+27842x15+14164x14+18577x13+28084x12+2630x11+19981x10+32617x9+29073x8+7564x7+6983x6+4578x5+22718x4+10812x3+41753x2+36640x+43117

(4)

tHtimetH

tH:=0.003

(5)

modpExpandp0p1,m1

0

(6)

Next Berkowitz with composite modulus

m2m11

m2:=44200

(7)

tBtime:

p2CharacteristicPolynomialm2,A,x

p2:=x30+37365x29+4931x28+43039x27+35328x26+26584x25+23190x24+27442x23+41208x22+38734x21+19681x20+7132x19+14062x18+31571x17+43180x16+6873x15+2753x14+18263x13+9875x12+13378x11+29095x10+20935x9+2151x8+1739x7+6988x6+26015x5+15981x4+38044x3+4421x2+12865x+30584

(8)

tBtimetB

tB:=0.090

(9)

modpExpandp0p2,m2

0

(10)

Factor of time faster for Hessenberg

tBtH

30.00000000

(11)

See Also

LinearAlgebra/Details

LinearAlgebra[Modular]

LinearAlgebra[Modular][IntegerCharacteristicPolynomial]

LinearAlgebra[Modular][Mod]

 


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