¿Cuál es la mejor manera de determinar el número de no ceros en la multiplicación de matrices dispersas?

Me preguntaba si existe un método rápido y eficiente para encontrar el número de no ceros de antemano por multiplicación de matrices escasa asumiendo ambas matrices están en formato CSC o RSE.

Sé que hay uno en el paquete smmp, pero necesito algo que ya esté implementado en C o C ++.

Cualquier ayuda será apreciada. Gracias por adelantado.

Puede simular el producto matriz-matriz formando el producto de los dos patrones de dispersión, es decir, considera el patrón de dispersión (que se almacena en matrices separadas en formato CSR) como una matriz que contiene un cero o uno en cada entrada La ejecución de este producto simulado sólo requiere para formar el yopera en estos ceros y unos y, por lo tanto, es mucho más rápido que el producto matriz-matriz real; de hecho, todo lo que tiene que hacer es recorrer las filas y columnas de las dos matrices y verificar que haya al menos una entrada en un fila y la columna con la que multiplica con ambas matrices que no son cero. Esta es una operación barata, mucho más barata en cualquier caso que tener que hacer la multiplicación de coma flotante en el producto real que no solo requiere que hagas aritmética de coma flotante (costosa) sino que también leas los números de coma flotante reales de la memoria ( aún más caro, pero no es necesario que al multiplicar el patrón de escasez debido a que los que no son cero los valores de la matriz se almacenan por separado en RSE).

De hecho, me escribió el código original en Matlab para A * B, A y B escasa. Pre-asignación de espacio para el resultado fue de hecho la parte interesante. Observamos lo que apunta a cabo Godric - que conocer el número de nonzeros en AB es tan costoso como el cálculo de AB.

Hicimos la implementación inicial de la escasa Matlab alrededor de 1990, antes del artículo de Edith Cohen que brindaba la primera forma práctica y rápida de estimar con precisión el tamaño de AB. Armamos un estimador de tamaño inferior, y si nos quedamos sin espacio en la mitad del cálculo, duplicamos la asignación y copiamos el resultado parcialmente calculado.

No sé qué hay en Matlab ahora.

Otra posibilidad sería la de calcular la columna uno AB a la vez. Cada columna puede almacenarse temporalmente en un acumulador de escasa (ver el artículo Matlab escaso para una explicación de estos), y el espacio asignado para mantener el tamaño exactamente conocida de la columna de resultados. El resultado sería en forma de columna dispersa comprimido dispersado - cada columna de CSC pero no contigüidad intercolumnas - utilizando 2 vectores de númeroColumnas longitud (Inicio col, col longitud), en lugar de uno, como meta-datos. Su forma un dispositivo de almacenamiento que puede ser digno de una mirada; tiene otra fortaleza: puede hacer crecer una columna sin reasignar toda la matriz.

Este artículo describe un algoritmo para aproximar el tamaño de una resultante de la matriz producto de dos matrices dispersas.

El problema con la búsqueda de un número exacto de los no-cero entradas en una multiplicación matriz dispersa es que cada elemento de la resultante depende de la interacción de dos vectores, ambos de los cuales son susceptibles de contener al menos un par de elementos no nulos. Por lo tanto, para calcular el número, debe evaluar las operaciones lógicas en un par de vectores para cada elemento resultante. El problema con esto es que requiere una cantidad de operaciones similares a la cantidad de operaciones necesarias para calcular el producto matriz en sí. En mis comentarios he mencionado la posibilidad de explotar ciertas estructuras en las que no son cero los elementos de las matrices originales, sin embargo esos mismos exploits podrían ser utilizados para reducir el trabajo realizado en la multiplicación de la matriz también.

Es probable sería mejor utilizar el papel por encima de a la sobre-estimar los requisitos de memoria, hacer la multiplicación y luego truncar la memoria asignada, o mover la matriz resultante a una matriz de más de tamaño apropiado. Además, los productos de matriz dispersa no son una ocurrencia rara, y casi garantizaría que este problema se haya resuelto antes. Un poco de investigación en algunas bibliotecas de matriz abierta y de código abierto debería llevarlo a los algoritmos que usan para preasignar memoria.

Para que la RSE o CSC, está garantizado que su gama de elementos de la matriz ya no tiene ceros? En ese caso, es fácil de averiguar cuántos elementos no nulos existen, usando algo similar a:

int nnz = sizeof(My_Array)/sizeof(long int);

Sin embargo, si este no es el caso (parece un poco demasiado fácil) lo que podría intentar es una reducción . Si su matriz de elementos de matriz es muy grande, esta puede ser la forma más eficiente de calcular la cantidad de elementos distintos de cero. Muchos / C ++ bibliotecas paralelo C, tales como empuje (una biblioteca CUDA) o OpenCL (que no se necesita una GPU de uso) tienen soporte para reducciones condicionales - para cada elemento, añadir el resultado de Condition(Element). Si se establece la condición de que Element != 0a continuación vamos a añadir el número de elementos no nulos. También es posible que desee eliminar los elementos de valor cero de su matriz de elementos, matriz de índices de fila / columna y ajustar sus punteros de columna / fila.

La forma más sencilla de implementos RSE es tratar

std::vector< std::map<int, complex<float>> > 

para representar a su matriz. En ese caso, realmente no se preocupará por el número de elementos distintos de cero, se accede a todos a través de

std::map< int, complex<float> >::iterator

en cada fila. Mejor ..