[SciPy-User] What is the complexity of scipy.sparse.linalg.eigsh

[David Cournapeau]

On Tue, Sep 13, 2011 at 10:48 PM, rechardchen <rechardchen at gmail.com> wrote:
> Hi, all
>       Recently I am using scipy.sparse.linalg.eigsh to compute K smallest
> eigenvalues(and their eigenvectors), but I have no idea how fast the
> function  runs. I know it uses ARPACK's implicitly restarted Lanczos Method,
> but I found no such information on ARPACK's official site.

It depends on your input (sparsity of the matrix). Assuming a square,
dense matrix of nrows, the cost is O(n^2 * k), keeping in mind the
constant can be pretty high. It is also data dependent, as the method
is iterative (there are no algebraic solutions to eigenvalues problems
in general).

cheers,

David