resueltos - valores y vectores propios de una matriz 3x3 julioprofe
¿Qué tan caro es calcular los valores propios de una matriz? (7)
¿Cuánto tiempo puede llevarme a la práctica si tengo una matriz de 1000x1000?
MATLAB (basado en LAPACK) calcula en una máquina de doble núcleo de 1.83 GHz todos los valores propios de un 1000x1000 al azar en aproximadamente 5 segundos. Cuando la matriz es simétrica , el cálculo se puede hacer de manera significativamente más rápida y solo requiere alrededor de 1 segundo.
¿Qué tan caro es calcular los valores propios de una matriz?
¿Cuál es la complejidad de los mejores algoritmos?
¿Cuánto tiempo puede llevarme a la práctica si tengo una matriz de 1000 x 1000? Supongo que ayuda si la matriz es escasa.
¿Hay algún caso en el que el cálculo del valor propio no termine?
En R , puedo calcular los valores propios como en el siguiente ejemplo de juguete:
m<-matrix( c(13,2, 5,4), ncol=2, nrow=2 )
eigen(m, only.values=1)
$values
[1] 14 3
¿Alguien sabe qué algoritmo usa?
¿Hay algún otro paquete (de código abierto) que calcule el valor propio?
Supongo que ayuda si la matriz es escasa.
Sí, hay algoritmos que funcionan bien en matrices dispersas.
Ver por ejemplo: http://www.cise.ufl.edu/research/sparse/
Con matrices grandes, generalmente no quieres todos los valores propios. Solo desea que los primeros pocos hagan (diga) una reducción de dimensión.
El algoritmo canónico es el algoritmo iterativo Arnoldi-Lanczos implementado en ARPACK:
www.caam.rice.edu/software/ARPACK/
Hay una interfaz de matlab en eigs:
eigs(A,k) and eigs(A,B,k) return the k largest magnitude eigenvalues.
Y ahora también hay una interfaz R:
La mayoría de los algoritmos para los cálculos de valor propio se escalan a grande-Oh (n ^ 3), donde n es la dimensión fila / col de la matriz (simétrica y cuadrada).
Para conocer la complejidad del tiempo del mejor algoritmo hasta la fecha, debería consultar los últimos trabajos de investigación en Informática Científica / Métodos Numéricos.
Pero incluso si asumes el peor caso, aún necesitarías al menos 1000 ^ 3 operaciones para una matriz de 1000x1000.
R usa la implementación de la rutina LAPACK (DSYEVR, DGEEV, ZHEEV y ZGEEV) de forma predeterminada. Sin embargo, podría especificar EISPACK = TRUE como parámetro para usar las rutinas RS, RG, CH y CG de EISPACK.
Los paquetes de fuente abierta más populares y buenos para el cálculo de valores propios son LAPACK y EISPACK.
Me gustaría echar un vistazo a los algoritmos de Eigenvalue , que se vinculan a una serie de métodos diferentes. Todos ellos tendrán diferentes características, y con suerte uno será adecuado para sus propósitos.
Utiliza el QR QR. Ver Wilkinson, JH (1965) El problema de valores propios algebraicos. Clarendon Press, Oxford. No explota la dispersión.
Apache Mahout es un marco de código abierto basado en map-reduce (es decir, funciona para matrices realmente grandes). Tenga en cuenta que para muchas cosas de la matriz, la pregunta no es "¿cuál es el gran momento de ejecución", sino más bien "¿qué tan paralelizable es?" Mahout says que usan Lanczos, que esencialmente se puede ejecutar en paralelo en tantos procesadores como quieras darle.