Speedup calculation of the largest eigenvalue and eigenvector of a 400×400 matrix? [duplicate]

Question

Actually, the matrix is an adjacency matrix of a network. The code is:

A1 = GridGraph[{20, 20}, PlotLabel -> "20*20 nodes", VertexLabels -> "Name"]
A = AdjacencyMatrix[A1];

I want to calculate the eigenvalue of A and its eigenvector. I have tried the normal function such as Eigenvalues and Eigenvectors. But it need much time and may not get a result (my laptop have not complete the calculation yet.)

The code is:

λ = N[Eigenvalues[Normal[A], 1]][[1]];
uA = N[Eigenvectors[Normal[A], 1]][[1]];

I want to know whether there is a method or parameter to reduce the time.

Answer 1

The issue here is that AdjacencyMatrix returns a non-real valued matrix

g = GridGraph[{20, 20}];
amg = AdjacencyMatrix[A1];

meaning the elements are all integers:

In[]:= Map[Head,Normal@amg,{2}]//Flatten//Union
Out[]= {Integer}

and the kernel is trying to find an answer in terms of integers, rational numbers, and roots. Numericizing before computation leads to the timings in fractions of a second for your example:

In[]:= eig = Eigensystem[N[amg]];//AbsoluteTiming
Out[]= {0.05914,Null}

Eigenvalues are ordered by the absolute value of the eigenvalues, so the first one is the max. You get it and its corresponding eigenvector as:

eig[[All, 1]]

Answer 2

If you just want the largest eigenvalue, the Arnoldi method is much faster than calculating all eigenvalues (and associated eigenvectors) and picking the largest:

Eigensystem[A // N, 1,
            Method -> {"Arnoldi", "Criteria" -> "RealPart"}] // AbsoluteTiming

(*    {0.007187, {{3.95532}, {{-0.00211558, -0.0041839, ..., -0.00211558}}}}    *)