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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Sure. Here it is pastebin.com/qfPQv9LQ $\endgroup$
    – Kar
    Commented Oct 30, 2014 at 10:27
  • 4
    $\begingroup$ And btw, you don't generate only the first, you generate them all and take the first. $\endgroup$
    – Öskå
    Commented Oct 30, 2014 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
    Commented Oct 30, 2014 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
    Commented Oct 30, 2014 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
    Commented Oct 30, 2014 at 16:32

2 Answers 2

Reset to default
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 [...] }}}

Improve this answer
$\endgroup$
4
$\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, [...]}}}   *)
Improve this answer
$\endgroup$
2
  • $\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
    Commented Dec 1, 2019 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
    Commented Dec 1, 2019 at 22:02

Your Answer

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

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