scipy.sparse.linalg.eigs is faster with k=8 than with k=1
Hi: I am using scipy.sparse.linalg.eigs with a 336x336 sparse matrix with 1144 nonzero entries. I only need the eigenvector corresponding to the larger eigenvalue, so I was running the function with k=1. However, I found that it is about 10 times faster to call the function with k=8. I am testing this with the following code (available here: https://gist.github.com/2775892): ############################################################# import timeit setup = """ import numpy as np import scipy.sparse import scipy.io from scipy.sparse.linalg import eigs P = scipy.io.mmread('P.mtx') """ n = 10 for k in range(1,20): code = 'eigs(P, k=%d)' % k t = timeit.timeit(stmt=code, setup=setup, number=n) / n print 'k: %2d, time: %5.1f ms' % (k, 1000*t) ############################################################# The output is k: 1, time: 301.7 ms k: 2, time: 242.6 ms k: 3, time: 352.0 ms k: 4, time: 168.8 ms k: 5, time: 148.1 ms k: 6, time: 93.2 ms k: 7, time: 70.0 ms k: 8, time: 29.3 ms k: 9, time: 45.2 ms k: 10, time: 63.0 ms k: 11, time: 209.1 ms k: 12, time: 170.8 ms k: 13, time: 120.2 ms k: 14, time: 104.6 ms k: 15, time: 115.0 ms k: 16, time: 97.0 ms k: 17, time: 94.0 ms k: 18, time: 94.4 ms k: 19, time: 74.3 ms Is this behavior typical for eigs? In other words, should I always use k set to values around 6 or 8, or is it matrix dependent? I am also curious about this. I would expect that computing 1 eigenvector should never be slower than computing more eigenvectors. Any about why is this happening? Alejandro.
Alejandro Weinstein <alejandro.weinstein <at> gmail.com> writes: [clip]
I am using scipy.sparse.linalg.eigs with a 336x336 sparse matrix with 1144 nonzero entries. I only need the eigenvector corresponding to the larger eigenvalue, so I was running the function with k=1. However, I found that it is about 10 times faster to call the function with k=8. [clip] Is this behavior typical for eigs? In other words, should I always use k set to values around 6 or 8, or is it matrix dependent?
I am also curious about this. I would expect that computing 1 eigenvector should never be slower than computing more eigenvectors. Any about why is this happening?
The sparse eigenvalue solver, ARPACK, is a Krylov method, and the size of the Krylov subspace depends on `k` (you can also adjust it by specifying the `ncv` parameter). I don't see any straightforward ways to predict how the exact performance depends on the Krylov subspace size --- bigger is better, but on the other hand, involves more work. The performance will in any case depend on the structure of the matrix. More on ARPACK: ftp://ftp.caam.rice.edu/pub/people/sorensen/ARPACK/ug.ps.gz
On Wed, May 23, 2012 at 11:15 AM, Pauli Virtanen <pav@iki.fi> wrote:
The sparse eigenvalue solver, ARPACK, is a Krylov method, and the size of the Krylov subspace depends on `k` (you can also adjust it by specifying the `ncv` parameter). I don't see any straightforward ways to predict how the exact performance depends on the Krylov subspace size --- bigger is better, but on the other hand, involves more work. The performance will in any case depend on the structure of the matrix.
I see. Thanks for the answer. Just for the record, if I set sigma=1, which means that eigs finds eigenvalues near sigma using shift-invert mode, then the time increases with k. These are the times (everything is the same as in the original program, except that I use code = 'eigs(P, k=%d, sigma=1)' % k Using sigma equal to 1.000000 k: 1, time: 3.1 ms k: 2, time: 6.9 ms k: 3, time: 5.4 ms k: 4, time: 7.9 ms k: 5, time: 16.8 ms k: 6, time: 24.4 ms k: 7, time: 17.1 ms k: 8, time: 20.4 ms k: 9, time: 21.2 ms k: 10, time: 20.7 ms k: 11, time: 23.5 ms k: 12, time: 24.2 ms k: 13, time: 32.0 ms k: 14, time: 32.9 ms k: 15, time: 23.3 ms k: 16, time: 36.4 ms k: 17, time: 49.4 ms k: 18, time: 39.3 ms k: 19, time: 42.2 ms Alejandro.
participants (2)
-
Alejandro Weinstein -
Pauli Virtanen