5
$\begingroup$

When I try to compute the eigenvalues of the adjacency matrix of a very large graph I get, what can be charitably described as, garbage. In particular, since the graph is four-regular, the eigenvalues should be in $[-4, 4]$ but they are visibly not. I used Matlab (via MATLink), and got the same problems, so this is clearly an issue that transcends mathematica. The question is: what is the best way to deal with it. (the obvious solution -setting precision to 100 - makes Mathematica run out of memory, and would probably take forever if it did not).

$\endgroup$
  • $\begingroup$ Do you need all the eigenvalues, or just the first (or last) few? $\endgroup$ – J. M. will be back soon Jul 25 '16 at 17:16
  • $\begingroup$ @J.M. I need all of them, alas... $\endgroup$ – Igor Rivin Jul 25 '16 at 17:20
  • $\begingroup$ I'm kind of wondering what sort of computer would it take to get an accurate eigensystem of a $27450\times27450$ matrix, if so... in any event, did you at least try to compare the results of taking the first few and last few eigenvalues with increasing precision? $\endgroup$ – J. M. will be back soon Jul 25 '16 at 17:26
  • $\begingroup$ Did you get the same results in MATLAB and Mathematica? Are sure that your graph is correctly specified? $\endgroup$ – mikado Jul 25 '16 at 17:29
  • 1
    $\begingroup$ @george2079 I am not sure I understand the question. If you don't N[] the matrix, the computation takes (literally) forever. $\endgroup$ – Igor Rivin Jul 25 '16 at 17:31
5
$\begingroup$

Igor,

I tried this and got a result with all eigenvalues in the range [-4,4]:

graph = Import["https://www.dropbox.com/s/m3ytliwfcgsdgul/c500.m?dl=1"];
adjacency = AdjacencyMatrix[graph];
eigenvalues = Eigenvalues[N[adjacency]];

Check the length:

Length[eigenvalues] (* gives: 27,450 *)

Check the minimum and maximum values:

MinMax[eigenvalues] (* gives: {-3.46169, 3.99988} *)

Plot the eigenvalues:

ListPlot[eigenvalues]

enter image description here

I placed the computed eigenvalues in this cloud object:

https://www.wolframcloud.com/objects/user-7053ce31-817f-4643-aec1-eda27051bba6/for-igor-rivin

Is this what you're after? If not, can you clarify your question perhaps (with code)?

$\endgroup$
  • $\begingroup$ What sort of computer did you use? My original bug was manifested on an OS X mathematica, but on Windows things seem to work fine - which seems to mean it is a virtual memory problem of some sort. $\endgroup$ – Igor Rivin Sep 15 '16 at 17:54
  • $\begingroup$ (Commenting from memory, I may have to correct details later) I used my Windows 10 desktop machine, with an i7 processor and 32GB of memory. During the computation the task manager was showing about 16GB of memory use (for all processes). I can check into Mac, it is possible that the numerics library performs differently on the platform in this case. $\endgroup$ – Arnoud Buzing Sep 16 '16 at 13:09

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.