Producto de matriz booleana rápida y dispersa con posible preprocesamiento

¿Cuáles son los algoritmos más eficientes en la práctica para multiplicar dos matrices booleanas muy dispersas (digamos, N = 200 y solo hay unos 100-200 elementos distintos de cero)?

En realidad, tengo la ventaja de que cuando multiplico A por B, las B están predefinidas y puedo hacer un preprocesamiento complejo arbitrario en ellas. También sé que los resultados de los productos son siempre tan escasos como las matrices originales.

El algoritmo "bastante ingenuo" (escaneo A por filas; por cada 1 bit de la fila A, O el resultado con la fila correspondiente de B) resulta muy eficiente y requiere solo un par de miles de instrucciones de la CPU para calcular un solo producto , por lo que no será fácil superarlo, y solo es superable por un factor constante (porque hay cientos de un bit en el resultado). Pero no estoy perdiendo la esperanza y pidiendo ayuda a la comunidad :)

ds.algorithms matrix-product sparse-matrix boolean-matrix implementation jkff
fuente

Dudo que podamos superar significativamente una constante de 10 instrucciones de máquina por palabra de salida. ¿Es posible que alguna forma implícita del resultado sea aceptable?

Warren Schudy

Sí, siempre que pueda multiplicarse por Bs más.

jkff

¿Cuáles son las operaciones de suma y multiplicación (para bits) en las que se define la multiplicación matricial? Su ingenuo algoritmo sugiere que la respuesta es "o" y "y" respectivamente, pero esa es una multiplicación de matriz bastante extraña ya que esas no definen un campo. ¿Te refieres a "xor" en lugar de "o"?

Warren Schudy

No, quiero decir "o" y "y". No necesito las operaciones para definir un campo, en realidad es un problema similar a la posibilidad de alcanzar gráficos (estoy calculando la composición de varias funciones de uno a muchos).

jkff

Respuestas:

Era reacio a responder esto, porque el único resultado teórico que conozco en este sentido tiene mi nombre en el papel ...

$n \times n$ $A$ $A$ $n$

(Nota: este algoritmo solo es realmente útil para el caso en que una matriz es densa y la otra es escasa. Sin embargo, este caso aparece mucho, por ejemplo, al calcular el cierre transitivo de un gráfico disperso, la matriz de cierre transitivo eventualmente se volverá densa en comparación con la matriz de adyacencia original).

El papel es

Guy E. Blelloch, Virginia Vassilevska, Ryan Williams: un nuevo enfoque combinatorio para problemas de gráficos dispersos. ICALP (1) 2008: 108-120

$\varepsilon > 0$ $O(n^{2+\varepsilon})$ $n \times n$ $A$

$v$ $t$ $A v$ $O(n(t/k + n/\ell)/\log n)$ $\ell$ $k$ ${\ell \choose k} \leq n^{\varepsilon}$ $\ell=\log^c n$ $k=\varepsilon(\log n)/\log \log n$ $nt/\log n + n^2/\log^c n$ $c$

- Las actualizaciones de fila y columna a se pueden calcular en tiempo . $A$ $O(n^{1+\varepsilon})$

Utilizamos esta estructura de datos para proporcionar algoritmos teóricos más rápidos para APSP en gráficos dispersos no pesados.

Ryan Williams
fuente

Acabo de notar que también asumes que la salida de la multiplicación de la matriz también es escasa. En ese caso, hay algoritmos aún más rápidos; haga una búsqueda en la web para "multiplicación de matriz sensible a la salida".

Ryan Williams

Ryan Williams - Tengo una pregunta rápida: ¿conoce o ha explorado algún método que generalice a matrices escasamente valoradas en (en lugar de simplemente booleano)?

{- 1, 0, 1}

$\{-1, 0, 1\}$

Alexandre Cassagne

Creo que lo que llamas es una matriz "hipersparse" (nnz <n). Hace unos años escribí un artículo sobre cómo multiplicarlos. Esencialmente, es una combinación de producto externo con una inteligente combinación de múltiples vías para eliminar la realización de triples intermedios.

Buluc y Gilbert, IPDPS 2008: http://gauss.cs.ucsb.edu/publication/hypersparse-ipdps08.pdf

Aydin Buluc
fuente