Bill Allombert on Tue, 19 Nov 2019 19:04:39 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Matrix exponentiation

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).