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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.