Re: Matrix exponentiation

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

On Tue, Nov 19, 2019 at 05:41:40PM +0000, Predrag Terzic wrote:
> Let me make myself clear.
> If M=[1,1;1,0] and n=5 which algorithm is used to calculate M^n and
> what is its computational complexity?

It uses sliding-window binary powering, so the complexity is close to
log_2(n)+1 matrix multiplications.

If d is the dimension of your matrix, the method using charpoly
will have a cost of about d+1 matrix multiplications, and 
about log_2(n)+1 polynomial multiplications (which are much cheaper).

Cheers,
Bill