Cruz publicado en StackOverflow.
Tengo algunas muy grandes matrices dispersas creado mediante spMatrix función de la matriz de paquete.
El uso de la solución() funciona para mi Ax=b problema, pero se necesita un tiempo muy largo. Varios días.
Me di cuenta de que http://cran.r-project.org/web/packages/RScaLAPACK/RScaLAPACK.pdf parece tener una función que puede paralelizar la función de resolver, sin embargo, puede tomar varias semanas para obtener nuevos paquetes instalado en este servidor en particular.
El servidor ya tiene la nieve de los paquetes instalados.
Así
- Es allí una manera de usar la nieve para paralelizar esta operación?
- Si no, hay otras maneras para acelerar este tipo de operación?
- Hay otros paquetes como RScaLAPACK? Mi búsqueda en RScaLAPACK parecía sugerir que la gente tenía un montón de problemas con él.
Gracias.
Detalles adicionales
- Las matrices son alrededor de 370.000 x 370,000. Lo estoy usando para resolver alfa centralidad, http://en.wikipedia.org/wiki/Alpha_centrality.
- Yo era originalmente mediante el alfa de la centralidad de la función en el igraph paquete, pero de que se estrellara R.
- Esto es en una sola máquina con 12 núcleos y 96 gigas de memoria (creo)
- Es un gráfico dirigido a lo largo de las líneas del documento de citación relaciones.
- El cálculo de la condición de número y densidad llevará un tiempo. Publicaremos como viene disponible.
Respuestas
¿Demasiados anuncios?
Dan
Puntos
51
¿Has probado la descomposición QR? Ver Teorema 3 aquí para la solución de $Ax=b$.
Encontrar la inversa de una matriz (incluso una pequeña) es un proceso lento. Métodos tales como la descomposición QR o Cholesky se utilizan en la práctica cuando es necesario 'invertir' (al menos en mi experiencia en estadística programación).
Usted puede descomponer esta operación en un conjunto de operaciones más pequeñas que son fáciles de poner en paralelo.
Supongamos que se desea resolver $\mathbf{m}\mathbf{v}=\mathbf{u}$ $N$ $N$ matriz $\mathbf{m}$ $N$- vector $\mathbf{u}$. Escrito $N=n+m$ (intentando $n\approx m$), descomponer $\mathbf{m}$ en cuatro bloques $\mathbf{a}_{n \times n}$, $\mathbf{b}_{n \times m}$, $\mathbf{c}_{m\times n}$, y $\mathbf{d}_{m \times m}$, y también se descomponen $\mathbf{u}$ en su primer $n$ componentes $\mathbf{e}_n$ y su última $m$ componentes $\mathbf{f}_m$, mientras que del mismo modo que expresan $\mathbf{v}$ como la concatenación de la $n$-vector $\mathbf{x}$ e las $m$-vector $\mathbf{y}$. El sistema original se aprecia fácilmente a ser equivalente a la secuencia
$$\eqalign{ \mathbf{a} \mathbf{z} &= \mathbf{e} \\ \mathbf{a} \mathbf{w} &= \mathbf{b} \\ \left(\mathbf{d}-\mathbf{c}\mathbf{w}\right)\mathbf{y}& = \mathbf{f} - \mathbf{c}\mathbf{z} \\ \mathbf{a}\mathbf{x} &= \mathbf{e} - \mathbf{b}\mathbf{y} }$$
Los dos primeros forman $m+1$ sistemas de $n$ ecuaciones (tener una matriz común); y el tercero es un sistema único de $m$ ecuaciones (dependiendo de las soluciones a los dos primeros); y el último es un sistema único de $n$ ecuaciones (dependiendo de la solución a la tercera). Eligiendo $m \approx n \approx N/2$, se han reducido los tamaños de las matrices involucradas y que han creado una oportunidad para que se ejecute la primera $m+1$ sistemas en paralelo. Si esto no es suficiente, la técnica puede ser aplicada de forma recursiva.
Este enfoque funciona no importa lo que el algoritmo para la solución de un sistema lineal se puede favorecer.
