Python eigenvectors: differences among numpy.linalg, scipy.linalg and scipy.sparse.linalg

Question

Scipy and Numpy have between them three different functions for finding eigenvectors for a given square matrix, these are:

1. numpy.linalg.eig(a)
2. scipy.linalg.eig(a), and
3. scipy.sparse.linalg.eig(A, k)

Focusing specifically on the situation that all the optional arguments I've left off the last two are left at their defaults and that a/A is real-valued, I am curious about the differences among these three which are ambiguous from the documentation - especially:

• Why does (3) have a note that it can't find all eigenvectors?
• Why must the other two compute all solutions - why don't they take a k argument?
• (1) has a note saying that the eigenvalues are returned in no particular order; (3) has an optional argument to control the order. Does (2) make any guarantees about this?
• Does (3) assume that A is sparse? (mathematically speaking, rather than being represented as a scipy sparse matrix) Can it be inefficient, or even give wrong results, if this assumption doesn't hold?
• Are there other factors I should consider when choosing among these?

Answer 1

The special behaviour of the third one has to do with the Lanczos algorithm, which works very well with sparse matrices. The documentation of scipy.sparse.linalg.eig says it uses a wrapper for ARPACK, which in turn uses "the Implicitly Restarted Arnoldi Method (IRAM) or, in the case of symmetric matrices, the corresponding variant of the Lanczos algorithm." (1).

Now, the Lanczos algorithm has the property that it works better for large eigenvalues (in fact, it uses the maximum eigenvalue):

In practice, this simple algorithm does not work very well for computing very many of the eigenvectors because any round-off error will tend to introduce slight components of the more significant eigenvectors back into the computation, degrading the accuracy of the computation. (2)

So, whereas the Lanczos algorithm is only an approximation, I guess the other two methods use algos to find the exact eigenvalues -- and seemingly all of them, which probably depends on the algorithms used, too.