Algoritmo para multiplicación matricial de matriz cuadrática con matriz dispersa

Question

Estoy optimizando el código que depende en gran medida de una biblioteca Matrix personalizada (que no se excluirá del proyecto porque está en todas partes. Esto no es bueno, pero es un hecho. ..) muchos cálculos se hacen con las matrices de 10-20 filas y columnas, muchos cálculos incluyen una forma cuadrática como

C = A*B*A' 

me di cuenta de que a menudo a es escasa y me gustaría hacer uso de este hecho. Así que estoy buscando un algoritmo que pueda manejar este caso. La estabilidad numérica es importante. ¿Hay algo que pueda usar? (No escribí nuestra biblioteca, así que no sé si hay algún inconveniente que deba tener en cuenta)

Como "nuestro" método simple de multiplicación O (n^3) se ejecuta más rápido que Eigen 3 en la plataforma objetivo, como necesito estabilidad numérica y las matrices no son muy grandes, creo que el algoritmo de Strassen y el algoritmo Coppersmith-Winograd no son lo que estoy buscando. En cambio, es simplemente la multiplicación de la forma cuadrática de una manera que me permite verificar fácilmente los ceros en A.

¡Gracias por cualquier sugerencia!

Answer 1

Existe el documento this, que trata de la rápida multiplicación de matrices dispersas. El algoritmo desarrollado divide la matriz dispersa en dos partes: una densa y otra dispersa y aplica un algoritmo de multiplicación rápido en ella. Entonces, para mí, parece que no depende del tamaño de la matriz, como mencionaste con respecto a Strassen, sino del hecho de que es escasa.

Answer 2

Hay formas de implementar una matriz dispersa en formas que se hacen en una matriz más condensada que una matriz densa. Una manera en que lo hago es como sigue:

[0 0 0 0 0] 
[0 1 2 0 9] 
[0 0 0 2 0] 
[0 1 0 0 0] 

se convierte en un conjunto lineal de elementos no nulos

typedef struct { 
    int row; 
    int col; 
    double entry; 
} Element; 

typedef SparseMatrix Element*; 

Así la matriz ahora tiene una complejidad espacio de O (n) en lugar de O (n^2) Para A * B, donde A y B son matrices, solo necesita recorrer cada matriz para encontrar elementos coincidentes (es decir, a-> fila == b-> col & & a-> col == b-> fila), y posiblemente agregue varios juntos (producto interno). Este algoritmo sería de complejidad O (n^2) en lugar de O (n^3). Esto se debe a que puede omitir la operación frívola de tomar un producto interno que daría como resultado cero.

Answer 3

la salida Highly Parallel Sparse Matrix-Matrix Multiplication algorothm