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).
$\begingroup$
$\endgroup$
10
-
$\begingroup$ Do you need all the eigenvalues, or just the first (or last) few? $\endgroup$– J. M.'s missing motivation ♦Commented Jul 25, 2016 at 17:16
-
$\begingroup$ @J.M. I need all of them, alas... $\endgroup$– Igor RivinCommented Jul 25, 2016 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.'s missing motivation ♦Commented Jul 25, 2016 at 17:26
-
$\begingroup$ Did you get the same results in MATLAB and Mathematica? Are sure that your graph is correctly specified? $\endgroup$– mikadoCommented Jul 25, 2016 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 RivinCommented Jul 25, 2016 at 17:31
|
Show 5 more comments
1 Answer
$\begingroup$
$\endgroup$
2
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]
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)?
answered Sep 15, 2016 at 15:55
-
$\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$ Commented Sep 15, 2016 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$ Commented Sep 16, 2016 at 13:09