Re: Matrix exponentiation

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Tue, Nov 19, 2019 at 05:00:17PM +0000, Predrag Terzic wrote:
> Which algorithm is used for matrix exponentiation  in PARI/GP 2.11.1
> and what is its computational complexity? Is it repeated squaring
> algorithm (binary exponentiation) or something else?

Ah sorry, maybe you means A^n ? Then of course it is available in
PARI/GP and yes it uses the binary exponentiation method (double-and-add)

However if you are interested by n larger than the dimension of your
matrix, there is a faster method:

1) compute a annulator polynomial P for your matrix, for example
P = charpoly(M) 
  or 
P = minpoly(M).
Any polynomial is OK as long as P(M) = 0.

2) Compute 
Q = lift(Mod(x,P)^n)

3) M^n is then given by
subst(Q, x, M)

An example:
M=[1,2;3,4];
P=charpoly(M);
Q=lift(Mod(x,P)^1000);
subst(Q,x,M)==M^1000

Cheers,
Bill