6
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ In 10.4 looping over 100 iterations gives me 0.2967,0.1128,0.3945,0.6259 respectively., so persists. $\endgroup$ – Feyre Aug 17 '16 at 16:26
  • $\begingroup$ @Feyre - I take it you divided you're measured times by 100 (or you have a supercomputer) $\endgroup$ – mikado Aug 17 '16 at 18:05
  • $\begingroup$ @mikado Yes, those are the respective means. $\endgroup$ – Feyre Aug 17 '16 at 18:07
  • 1
    $\begingroup$ This question is possibly related to a question I had on MatrixExp, mathematica.stackexchange.com/questions/121625/… $\endgroup$ – user64620 Aug 17 '16 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.