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

David Cournapeau cournape@gmail....
Tue Sep 13 22:41:00 CDT 2011


On Tue, Sep 13, 2011 at 10:48 PM, rechardchen <rechardchen@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


More information about the SciPy-User mailing list