Calculando el inverso de una matriz muy grande

Estoy tratando de calcular el inverso de una matriz muy grande (11300x21500) en C++. Hasta ahora he probado las librerías Eigen y Armadillo, pero ambas fallaron en la etapa de inicialización, diciendo que no hay suficiente memoria. ¿Puede haber alguna forma de superar esta situación?Calculando el inverso de una matriz muy grande

Gracias de antemano

P.S
I deben corregir el tamaño de la matriz a 21500x21500. Como sugirió UmNyobe, esta no es una matriz cuadrada. En realidad, es la matriz de observación, X, y estoy tratando de calcular (X^TX) ^-1

tengo una memoria de 8 GB (en un sistema de 64 bits), pero no creo que estoy haciendo uso de todo este espacio de memoria. El administrador de tareas muestra que el uso de memoria en el momento del error es de 1 GB. Tal vez haya un comando de sistema operativo en Windows 7 que cierra una aplicación cuando su uso de memoria excede 1GB.

Por cierto, mi propósito original es ejecutar una regresión sobre esta matriz de observación.

Una cosa más: la mayoría de las columnas en cada fila de la matriz de observación X son cero. ¿Puede haber una forma de aprovechar esto para limitar el uso de la memoria en la operación de inversión?

Fuente

2012-05-09 Osman Darin

¿por qué sus dimensiones no son iguales? – UmNyobe

Esa matriz contiene aproximadamente 1GB o 2GB de datos dependiendo de si tiene entradas de matriz de 4 u 8 bytes. ¿Estás en una máquina de 32 bits? –

Steve Iba a publicar sobre la memoria, debe escribirla con más detalle como lo mencionó primero. – UmNyobe

No se puede invertir una matriz no cuadrada.

http://en.wikipedia.org/wiki/Invertible_matrix

Fuente

2012-05-09 22:33:57 MrWuf

Incluso si fuera cuadrado, la memoria todavía va a importar en el hardware de 32 bits –

He corregido la especificación, es una matriz cuadrada de 21000x21000 dimensiones. –

Creo que quiere una pseudoinversión Moore-Penrose, que puede tomar en una matriz no cuadrada. –

Suponiendo que la matriz es cuadrado, lo que es probable que estás buscando es un algoritmo de inversión de la matriz en el lugar.

Deberías echar un vistazo a this.

Fuente

2012-05-09 22:35:31

Asumiendo una matriz (11300 x 11300) de número entero (32 bits), que tienen

4*(11300^2)/(1024^3) = 0.4757 GB

Si está utilizando doble precisión a continuación, duplicar este número.

Si la biblioteca utiliza el algoritmo Strassen, que requiere memoria adicional de la misma magnitud, duplica el número anterior.

Invertir una matriz de doble base de este tamaño con Strassen o gaussian le costará 1,9 GB.

Fuente

2012-05-09 22:51:45 UmNyobe

... ¿entonces? Me parece bien. –

Por lo tanto, debe proporcionar detalles de la máquina en la que está trabajando. No podrá invertir un 21500x21500 en una máquina de 32 bits, por ejemplo ... – UmNyobe

Gracias por la entrada. Como especificación de mi máquina, tengo 8 gb de memoria (en un sistema de 64 bits). Pero por lo que puedo hacer un seguimiento del uso de la memoria con el administrador de tareas, Windows cierra la aplicación cuando la memoria utilizada es de 1 gb. Al menos, esa es la cantidad que muestran los administradores de tareas. Y eso realmente sucede antes de tomar el inverso. La aplicación proporciona el error en la etapa de inicialización de la matriz –

Me gustaría proponer otra solución, que solo funciona si no está interesado en la inversa de la matriz en sí, sino en el producto de la inversa con un vector. Por ejemplo, suponga que desea encontrar el producto de sus tiempos inversos en un vector v, es decir, w := (X^T X)^{-1} v. En este caso, en realidad se está buscando una solución al problema

Find w such that (X^T X) w = v

Usando algoritmos iterativos, es posible encontrar w dado X y v en la ecuación anterior sin invertirX. Una posibilidad que me viene a la mente es usar el Method of Conjugate Gradients.Este algoritmo se puede implementar en aproximadamente 10 líneas y solo requiere poder calcular el producto (X^T X) y con un vector dado y. En nuestro caso, esto se puede hacer incluso en dos pasos, es decir, calcular z := X y y en un segundo paso X^T z, lo que ahorrará espacio ya que no necesita almacenar el producto X^T X.

Fuente

2012-07-31 13:39:43 Mehrwolf

Aunque está compilando su programa en una máquina de 64 bits, también debe asegurarse de estar utilizando las bibliotecas correctas de 64 bits. De lo contrario, el programa puede compilarse en 32 bits y aún obtendrá los mismos problemas de memoria.

En cuanto al cálculo de la inversa, la función inversa de OpenCV puede ayudar. Asegúrese de usar el inverso de DECOMP_SVD, ya que considero que es más efectivo con matrices casi singulares.

Fuente

2013-07-21 09:40:15

Calculando el inverso de una matriz muy grande

Respuesta

Cuestiones relacionadas