¿Cuál es la forma más rápida de representar y multiplicar matrices booleanas dispersas?

Question

Por lo tanto, estoy usando matrices booleanas cuya dimensión suele ser un par de docenas a un par de cientos, por lo general son bastante dispersas (solo unos 2-4 no ceros en la mayoría de las filas y columnas) y mi tiempo de ejecución está fuertemente dominado por sus multiplicación.

¿Qué estructura de datos se adapta mejor para acelerar la multiplicación en estas circunstancias?

Actualmente estoy almacenando cada matriz en un conjunto de bits contiguos (matriz de longitudes de 64 bits) por filas, y multiplicándolas con básicamente el algoritmo estándar, solo aceleré para la dispersión con la operación rápida de localizar el siguiente conjunto bit en una palabra, y con vectorización por operaciones de máscara de bits.

¿Debo quizás usar alguna representación dispersa?

Answer 1

Creo que tiene sentido utilizar una representación dispersa. Incluso con algo tan simple como un conjunto de índices que no son cero, creo que obtendrás un mejor rendimiento.

Por ejemplo, para una matriz de 100 × 100 con 300 elementos distintos de cero, usando representación en 2D, la multiplicación requiere 100 × 100 × 100 = 1,000,000 de "operaciones". El uso de un conjunto de índices requiere solo 300 × 300 = 90,000 operaciones. (Por supuesto, esas operaciones no son directamente comparables.)

Answer 2

Una lista de las 1's de xey. Por ejemplo:

[0,2,0,12,0,60,1,2,1,39 ... etc]

Lo que significa que hay un 1 a 0,2 a 1 a 0 , 12, etc.

Lo bueno es que realmente no necesita un nuevo tipo de datos, y es bastante simple de analizar.

Para multiplicar, buscaría todos los índices coincidentes/parcialmente coincidentes.

Answer 3

Es posible que desee considerar el uso de una representación quadtree. El quadtree puede codificar una matriz dispersa bastante bien, y se presta a una implementación de multiplicación recursiva bastante fácil (y eficiente en caché). Haga que el caso base sea una matriz de 8x8 para que pueda implementar la multiplicación como una operación (¿optimizada para el ensamblaje?) De 64 bits por 64 bits.