3
$\begingroup$

I have a large sparse matrix, $L$, which represents the laplacian of a weighted graph: $L = \text{diag}(\sum_{j=1}^{N} w_{ij})-W$, where $W$ is the weighted adjacency matrix with $w_{ij}$ giving the non-negative weight of the edge connecting vertices $i$ and $j$, with $w_{ii} = 0$ (i.e. no self-loops). $L$ is symmetric. I would like to know the "unique" or "distinct" eigenvalues of $L$. I compute its eigenvalues and I get something like:

$$832.8374\\ 831.8227\\ 829.1944\\ 829.0325\\ 827.0706\\ 825.2424\\ 821.0557\\ 819.1499\\ 818.5737\\ 816.9287\\ \dots$$

I suspect that while numerically different, several of these really correspond to the same root of the characteristic polynomial, e.g. $\lambda_i' = 829.1944$ and $\lambda_i'' = 829.0325$ are probably the same root, $\lambda_i$, but due to numerical artifacts they appear different.

When computing eigenvalues numerically, how can I determine which eigenvalues are actually distinct roots of the characteristic polynomial (i.e. I want to know the unique eigenvalues and their geometric multiplicity)?

I am computing these using Matlab's eigs function, which uses the Arnoldi algorithm.

$\endgroup$
  • 1
    $\begingroup$ This problem is basically intractable, unless you can say something completely analytical (using some sort of structure of the matrix). $\endgroup$ – Ian Jan 15 '16 at 22:43
  • $\begingroup$ @Ian: See the edits, L is a graph laplacian and is symmetric and real valued. Does that help? $\endgroup$ – okj Jan 17 '16 at 2:27
  • $\begingroup$ @okj Not really. Arbitrarily small perturbations of a matrix with a double eigenvalue will have single eigenvalues, which makes this kind of problem extremely numerically unsntable. The fact that your matrix has integer entries might help, though. $\endgroup$ – Ian Jan 17 '16 at 3:02
0
$\begingroup$

Assuming that the Arnoldi iteration appears to have converged, then given two eigenvalues, it is possible to determine if they are different. However, it is impossible to determine whether they are the same.

Given the entries of the matrix and the initial vector and the number of iterations in your eigensolver, it is possible to determine the maximum amount of error that has accrued from floating point operations as a function of the machine precision. Unfortunately, this floating error analysis might be quite tricky depending on exactly how you're implementing your iterative solver (it would be far easier, for example, to analyze power iteration).

At the end of the day, you'll have an upper bound on the relative error possible, in which case if any two eigenvalues have a ratio that exceeds that value, then they can be concluded to be different. If the two eigenvalues have a ratio below this threshold, then no conclusion can be made, as it is impossible to decide if the eigenvalues are the same, or just closer than the finite precision of the computer can resolve.

$\endgroup$

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.