<p>This is probably resolved. As pointed out in <a href="https://arxiv.org/pdf/1504.06768.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1504.06768.pdf</a>, you don't actually need to invert the shifted sparse matrix and then repeatedly apply it in some Lanczos-type method -- you just need to repeatedly solve an inverse problem (M-sigma*identity)*v(n+1)=v(n) to generate a sequence of vectors {v(n)}. This inverse problem can be done quickly for a sparse matrix after LU decomposition.</p>
counterintuitive speed difference between LM and shift-invert modes in scipy.sparse.linalg.eigsh?
<p>I'm trying to find the smallest (as in most negative, not lowest magnitude) several eigenvalues of a list of sparse Hermitian matrices in Python using scipy.sparse.linalg.eigsh. The matrices are ~1000x1000, and the list length is ~500-2000. In addition, I know upper and lower bounds on the eigenvalues of all the matrices -- call them <em>eig_UB</em> and <em>eig_LB</em>, respectively.</p>

<p>I've tried two methods:</p>

<ol>
<li>Using shift-invert mode with sigma=<em>eig_LB</em>.</li>
<li>Subtracting <em>eig_UB</em> from the diagonal of each matrix (thus shifting the smallest eigenvalues to be the largest magnitude eigenvalues), diagonalizing the resulting matrices with default eigsh settings (no shift-invert mode and using which='LM'), and then adding <em>eig_UB</em> to the resulting eigenvalues.</li>
</ol>

<p>Both methods work and their results agree, but method 1 is around 2-2.5x faster. This seems counterintuitive, since (at least as I understand the eigsh documentation) shift-invert mode subtracts sigma from the diagonal, inverts the matrix, and then finds eigenvalues, whereas default mode directly finds the largest magnitude eigenvalues. Does anyone know what could explain the difference in performance?</p>

<p>One other piece of information: I've checked, and the matrices that result from shift-inverting (that is, (M-sigma*identity)^(-1) if M is the original matrix) are no longer sparse, which seems like it should make finding their eigenvalues take even longer.</p>