# MatrixPower performance

In Mathematica 9, (I think) MatrixPower[matrix(m.m), n].vector has complexity $O(m^{2+\epsilon}\times\log(n))$ (Mathematica automatically find the algorithm that optimize the time), while MatrixPower[matrix(m.m), n, vector] has complexity $O(m^2\times n)$. It (the second form) always remain that complexity, sometimes it is good and sometimes bad.

For example:

mat = Table[RandomReal[1./500], {1000}, {1000}];
vec = Table[RandomReal[1./500], {1000}];

MatrixPower[mat, 1000]; // AbsoluteTiming

(* {6.831456, Null} *)

MatrixPower[mat, 1000, vec]; // AbsoluteTiming

(* {2.889963, Null}*)

MatrixPower[mat, 5000]; // AbsoluteTiming
(* {8.150533, Null} *)

MatrixPower[mat, 5000, vec]; // AbsoluteTiming

(* {15.022040, Null}*)


In the first case, it is good, and the second case, it is bad. This seems to be a mistake of the developers.

1. How can I determine the power that optimize the time?
2. Is that fixed in next versions?
• In 10.4 looping over 100 iterations gives me 0.2967,0.1128,0.3945,0.6259 respectively., so persists. – Feyre Aug 17 '16 at 16:26
• @Feyre - I take it you divided you're measured times by 100 (or you have a supercomputer) – mikado Aug 17 '16 at 18:05
• @mikado Yes, those are the respective means. – Feyre Aug 17 '16 at 18:07
• This question is possibly related to a question I had on MatrixExp, mathematica.stackexchange.com/questions/121625/… – user64620 Aug 17 '16 at 23:01