6
$\begingroup$

Is it normal for Mathematica to take over 30mins to try to compute the first eigenvector of a 100x100 matrix? The matrix is reasonably sparse - about 90% of the cells are 0s and each column sums to either 1 or 0.

The command I'm using is

m = ToExpression@Import@"http://pastebin.com/raw.php?i=yM4pUYQV";
N[Eigenvectors[m, Quartics -> True][[1]]]

My machine is an i5 3ghz and the process still isn't terminated yet. It's a quad core machine, but only one of the cores is being maxed out for over 30mins.

$\endgroup$
  • $\begingroup$ Sure. Here it is pastebin.com/qfPQv9LQ $\endgroup$ – Kar Oct 30 '14 at 10:27
  • 4
    $\begingroup$ And btw, you don't generate only the first, you generate them all and take the first. $\endgroup$ – Öskå Oct 30 '14 at 10:32
  • $\begingroup$ It seems it is taking forever with that matrix, but if I do the same N[Eigenvectors[mat, Quartics -> True][[1]]] where mat = RandomReal[{1, 1000}, {100, 100}], it takes no time at all. Something to do with the matrix m itself, I think. $\endgroup$ – Sultan of Swing Oct 30 '14 at 10:32
  • $\begingroup$ I've tried other matrices that have the same properties, i.e. 1) each column sums to either 1 or 0 and 2) reasonably sparse. For instance, pastebin.com/LczndfTL Same as the one I first posted, it's taking forever. $\endgroup$ – Kar Oct 30 '14 at 10:36
  • $\begingroup$ If you are goiung to numericize, why not just do Eigenvalues[N[matrix]]? It will be much faster, in the sense that an instant is faster than a half hour. $\endgroup$ – Daniel Lichtblau Oct 30 '14 at 16:32
14
$\begingroup$

Avoiding exact calculation by using approximated numerical value before calculation speeds things up. I'm also calculating only the first Eigenvectors as pointed pot by @Öskå. Now it takes only 15 milliseconds time

AbsoluteTiming[Chop@Eigenvectors[N[m], 1, Quartics -> True]]

{0.015600, {{-0.0725514, -0.106358, -0.0986766, -0.110735 [...] }}}

$\endgroup$
3
$\begingroup$

By using a sparse solver you can gain another factor of ten in speed over @rhermans' method:

Eigenvectors[m // SparseArray // N, 1, Method -> "Arnoldi"] // AbsoluteTiming

(*    {0.001119, {{-0.0725514, -0.106358, -0.0986766, -0.110735, [...]}}}   *)
$\endgroup$
  • $\begingroup$ Would that be the lowest eigenmode as organized by magnitude of Eigenvalues then? The speed up is awesome but it’s never been clear to me which eigenvalue or eigenvector that it is when we choose like this. What ordering ends up getting used? $\endgroup$ – CA Trevillian Dec 1 at 21:08
  • 2
    $\begingroup$ @CATrevillian Numerical eigenvalue routines sort the eigenvalues by Abs by default. At least the Method "Arnoldi" allows for the suboption ` "Criteria" ` which affects the sorting. See the docu of Eigenvalue under "Options", "Method","Arnoldi". $\endgroup$ – Henrik Schumacher Dec 1 at 22:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.