¿Cuál es la forma más rápida de calcular el valor propio más grande de una matriz general?

EDITAR: Estoy probando si algún valor propio tiene una magnitud de uno o más.

Necesito encontrar el valor propio absoluto más grande de una gran matriz dispersa, no simétrica.

He estado usando la eigen()función de R , que usa el algoritmo QR de EISPACK o LAPACK para encontrar todos los valores propios y luego uso abs()para obtener los valores absolutos. Sin embargo, necesito hacerlo más rápido.

También he intentado usar la interfaz ARPACK en el igraphpaquete R. Sin embargo, dio un error para una de mis matrices.

La implementación final debe ser accesible desde R.

Probablemente habrá múltiples valores propios de la misma magnitud.

¿Tienes alguna sugerencia?

EDITAR: Precisión solo necesita ser 1e-11. Una matriz "típica" ha sido hasta ahora . He podido hacer una factorización QR en él. Sin embargo, también es posible tener unos mucho más grandes. Actualmente estoy empezando a leer sobre el algoritmo Arnoldi. Entiendo que está relacionado con Lanczsos.$386\times 386$

EDIT2: si tengo varias matrices que estoy "probando" y sé que hay una gran submatriz que no varía. ¿Es posible ignorarlo / descartarlo?

Depende mucho del tamaño de su matriz, en el caso a gran escala también de si es escasa y de la precisión que desea lograr.

Si su matriz es demasiado grande para permitir una factorización única y necesita una alta precisión, el algoritmo de Lanczsos es probablemente la forma más rápida. En el caso no simétrico, se necesita el algoritmo Arnoldi, que es numéricamente inestable, por lo que una implementación debe abordar esto (es algo incómodo de curar).

Si este no es el caso en su problema, brinde información más específica en su pregunta. Luego agregue un comentario a esta respuesta, y lo actualizaré.

Editar: [Esto era para la versión anterior de la pregunta, buscando el valor propio más grande.] Como su matriz es pequeña y aparentemente densa, haría la iteración de Arnoldi en B = (IA) ^ {- 1}, usando una inicial la factorización triangular permutada de IA tiene una multiplicación barata por B. (O calcule un inverso explícito, pero esto cuesta 3 veces más que la factorización). Desea probar si B tiene un valor propio negativo. Al trabajar con B en lugar de A, los valores propios negativos están mucho mejor separados, por lo que si hay uno, debe converger rápidamente.

Pero tengo curiosidad acerca de dónde viene su problema. Las matrices no simétricas generalmente tienen valores propios complejos, por lo que "" más grande "" ni siquiera está bien definido. Por lo tanto, debe saber más sobre su problema, lo que podría ayudarlo a sugerir cómo resolverlo aún más rápido y / o de manera más confiable.

Edit2: Es difícil obtener con Arnoldi un subconjunto particular de interés. Para obtener los valores propios absolutamente más grandes de manera confiable, debe hacer una iteración del subespacio utilizando la matriz original, con un tamaño del subespacio que coincida o supere el número de valores propios que se espera que sea de 1 o mayor en magnitud. En matrices pequeñas, esto será más lento que el algoritmo QR, pero en matrices grandes será mucho más rápido.

La iteración de potencia (o método de potencia), por ejemplo, lo que describe Dan, siempre debe converger, aunque a la velocidad .$\left|\lambda_{n-1}/\lambda_{n}\right|$

Si está cerca de λ n , será lento, pero puede usar la extrapolación para evitarlo . Puede parecer complicado, pero en el documento se da una implementación en pseudocódigo.$\lambda_{n-1}$$\lambda_n$

Ha habido una buena investigación sobre esto recientemente. Los nuevos enfoques utilizan "algoritmos aleatorios" que solo requieren unas pocas lecturas de su matriz para obtener una buena precisión en los valores propios más grandes. Esto contrasta con las iteraciones de potencia que requieren varias multiplicaciones de matriz-vector para alcanzar una alta precisión.

Puede leer más sobre la nueva investigación aquí:

http://math.berkeley.edu/~strain/273.F10/martinsson.tygert.rokhlin.randomized.decomposition.pdf

http://arxiv.org/abs/0909.4061

Este código lo hará por usted:

http://cims.nyu.edu/~tygert/software.html

https://bitbucket.org/rcompton/pca_hgdp/raw/be45a1d9a7077b60219f7017af0130c7f43d7b52/pca.m

http://code.google.com/p/redsvd/

https://cwiki.apache.org/MAHOUT/stochastic-singular-value-decomposition.html

Si su idioma de elección no está allí, puede rodar su propia SVD aleatoria con bastante facilidad; solo requiere una multiplicación de vector de matriz seguida de una llamada a un SVD estándar.

Aquí encontrará una introducción algorítmica al algoritmo Jacobi-Davidson, que calcula el valor propio máximo.

En este artículo se exploran los aspectos matemáticos. JD permite matrices generales (reales o complejas) y puede usarse para calcular rangos de valores propios.

Aquí puede encontrar varias implementaciones de biblioteca JDQR y JDQZ (incluida una interfaz C, a la que debería poder vincular desde R).

En tu publicación original, dices:

"También intenté usar la interfaz ARPACK en el paquete igraph R. Sin embargo, me dio un error en una de mis matrices".

Me interesaría saber más sobre el error. Si puede hacer que esta matriz esté disponible públicamente en algún lugar, me interesaría probar ARPACK en ella.

Según lo que he leído anteriormente, esperaría que ARPACK hiciera un muy buen trabajo extrayendo los valores propios más grandes (o algunos de los más grandes) de una matriz dispersa. Para ser más específico, esperaría que los métodos de Arnoldi funcionen bien para este caso y, por supuesto, en eso se basa ARPACK.

La convergencia lenta del método de potencia cuando hay valores propios estrechamente espaciados en la región de interés se mencionó anteriormente. Arnoldi mejora esto al iterar con varios vectores en lugar del método de potencia.

No es el mas rapido forma rápida, pero una forma razonablemente rápida es simplemente golpear un vector (inicialmente aleatorio) con la matriz repetidamente y luego normalizar cada pocos pasos. Eventualmente convergerá al vector propio más grande, y la ganancia en la norma para un solo paso es el valor propio asociado.

Esto funciona mejor cuando el valor propio más grande es sustancialmente más grande que cualquier otro valor propio. Si otro valor propio es cercano en magnitud al mayor, esto tardará un tiempo en converger, y puede ser difícil determinar si ha convergido.

El paquete R RARPACK funciona para mí. Y parece ser muy rápido, ya que es solo una interfaz para ARPACK, el paquete estándar para álgebra lineal dispersa (lo que significa calcular algunos valores propios y vectores propios).