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

David Cournapeau cournape@gmail....
Wed Sep 14 13:10:03 CDT 2011


On Wed, Sep 14, 2011 at 8:19 AM, rechardchen <rechardchen@gmail.com> wrote:
> thanks. what if I use csr_matrix?
> can the literal k in your text be close to n?

The sparse format does not matter: what matters is the cost of the
basic operation A*x for your matrix A and one dense x vector. For
dense A, A*x is O(N^2). For sparse matrix, it could be less. So the
general formula for looking for k eigen values is generally O(k *
cost(A*x)).

cheers,

David


More information about the SciPy-User mailing list