Note that your A1
is a SparseArray
, while your NL1
is a full list of lists, since you've formed it using IdentityMatrix
and DiagonalMatrix
which return full lists of lists. This could have a huge impact on memory footprint as well as speed and accuracy of your computations, particularly if you're working with very large, sparse graphs. I would take this into account when forming the Laplacian matrix.
As I understand it, the Laplacian matrix of a graph is its adacency matrix minus its vertex degree matrix. We could implement this as a sparse matrix like so
g = GraphData[{"Kneser", {14, 6}}];
vertexDegrees = VertexDegree[g];
diagonalRules = Table[{i, i} -> -vertexDegrees[[i]],
{i, 1, Length[vertexDegrees]}];
adjacencyRules = ArrayRules[AdjacencyMatrix[g]];
laplacian = SparseArray[Join[diagonalRules, adjacencyRules]];
Dimensions[laplacian]
(* Out: {3003, 3003} *)
It's a large matrix; let's look at just a piece of it.
MatrixForm[Normal[laplacian[[1282 ;; 1296, 1282 ;; 1296]]] /.
0 -> Style[0, LightGray]]

I guess your version of the command to compute the 10 smallest eigenvalues would be
Eigenvalues[N[laplacian], -10] // AbsoluteTiming
(* Out: {2.454553, {-22.1063, -22., -22., -21.8781, -13.0058,
-13., -13., -13., -12.9948, 4.5206*10^-15}} *)
You might try something like so:
Eigenvalues[N[laplacian], 10, Method -> {"Arnoldi",
"Shift" -> 0, "BasisSize" -> 50}] // AbsoluteTiming
(* Out: {1.691656, {-13., -13., -13., -13., -13., -13., -13.,
-13., -12.6622, -6.90978*10^-16}} *)
You can use the Eigensystem
command to check for accuracy.
{vals, vecs} = Eigensystem[N[laplacian], 10, Method -> {"Arnoldi",
"Shift" -> 0, "BasisSize" -> 50}];
Norm[laplacian.vecs[[1]] - vals[[1]]*vecs[[1]]]
(* Out: 2.30196*10^-9 *)
{vals, vecs} = Eigensystem[N[laplacian], -10];
Norm[laplacian.vecs[[1]] - vals[[1]]*vecs[[1]]]
(* 0.284252 *)
It appears that the Arnoldi specified version is faster and more accurate.
I don't know a lot of the details behind the computations, particularly the second syntax with the -10. Perhaps @DanielLichtblau or @ruebenko could comment on that.
G
, otherwise we can't help easily. $\endgroup$N
will work wonders. $\endgroup$