Re: Matrix exponentiation

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

On Tue, Nov 19, 2019 at 07:04:35PM +0100, Bill Allombert wrote:
> 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).

Actually, 2*sqrt(d)+2 matrix multiplications because the polynomial
evaluation use Brent & Kung algorithm.

Cheers,
Bill