python sparse numpy

Computing N autovalores más pequeños de Sparse Matrix en Python

Question

Me gustaría encontrar los N valores más pequeños de una matriz dispersa en Python. Intenté usar el paquete scipy.sparse.linalg.eigen.arpack , pero es muy lento para calcular los valores propios más pequeños. Leí en alguna parte que hay un modo shift-invert, pero cuando intento usarlo, recibo un mensaje de error que me dice que el modo shift-invert no está soportado. ¿Alguna idea de cómo debo proceder?

Answer 1

Versiones de SciPy

Comparando la documentación de scipy.sparse.linalg.eigs de SciPy v0.9 con la documentación de scipy.sparse.linalg.eigs de SciPy v0.10 , parece que el modo shift-inverter está implementado y funcionando desde v0.10. Específicamente, la explicación del parámetro sigma en la documentación v0.9 indica que no está implementado, pero la documentación v0.10 no indica que sea el caso.

Si no tiene SciPy v0.10, o posterior, la instalación de la última debería permitirle utilizar el modo shift-invert con el eigensolver disperso.

Hallazgos lentos de autovalores de pequeña magnitud

Como se menciona en la pregunta, es posible usar la interfaz ARPACK para encontrar valores propios de pequeña magnitud. Esto se hace pasando which=''SM'' cuando se llama a scipy.sparse.linalg.eigs . Sin embargo, como se afirma en la pregunta, lento. Esto se confirma en la sección Tutorial de SciPy sobre Problemas de valores propios dispersos con ARPACK , donde dice:

Tenga en cuenta que ARPACK generalmente es mejor para encontrar valores propios extremos: es decir, valores propios con grandes magnitudes. En particular, usar which = ''SM'' puede llevar a un tiempo de ejecución lento y / o resultados anómalos. Un mejor enfoque es usar el modo shift-invert .

Experimentos

Veamos un código que intenta usar shift-invert con ambos v0.9 y v0.10 de SciPy. En ambos casos, usaremos el siguiente código.

from scipy.sparse import identity
from scipy.sparse.linalg import eigs

A = identity(10, format=''csc'')
A.setdiag(range(1, 11))
eigs(A, 3, sigma=0) # find three eigenvalues near zero using shift-invert mode

SciPy v0.9

Al ejecutar el código en SciPy v0.9, se genera una excepción.

NotImplementedError: shifted eigenproblem not supported yet

SciPy v0.10

Ejecutar el código en SciPy 0.10 produce los resultados esperados.

(array([ 1.+0.j,  2.+0.j,  3.+0.j]),
 array([[ -1.00000000e+00+0.j,   5.96300068e-17+0.j,   9.95488924e-17+0.j],
       [  3.55591776e-17+0.j,   1.00000000e+00+0.j,  -4.88997616e-16+0.j],
       [ -3.79110898e-17+0.j,   1.16635626e-16+0.j,   1.00000000e+00+0.j],
       [ -1.08397454e-17+0.j,   1.23544164e-17+0.j,   1.78854096e-15+0.j],
       [  1.68486368e-17+0.j,  -9.37965967e-18+0.j,   2.05571432e-16+0.j],
       [ -2.97859557e-19+0.j,  -3.43100887e-18+0.j,   3.35947574e-17+0.j],
       [  1.89565432e-17+0.j,  -3.61479402e-17+0.j,  -1.33021453e-17+0.j],
       [ -1.40925577e-18+0.j,   3.16953070e-18+0.j,   7.91193025e-17+0.j],
       [  6.76947854e-19+0.j,  -3.75674631e-19+0.j,   3.61821551e-17+0.j],
       [ -3.07505146e-17+0.j,  -6.52050102e-17+0.j,  -8.57423599e-16+0.j]]))