Produit à matrice booléenne rapide et clairsemé avec prétraitement possible

12

Quels sont les algorithmes les plus efficaces pour multiplier deux matrices booléennes très clairsemées (disons, N = 200 et il n'y a que 100 à 200 éléments non nuls)?

En fait, j'ai l'avantage que lorsque je multiplie A par B, les B sont prédéfinis et que je peux faire un prétraitement arbitrairement complexe sur eux. Je sais aussi que les résultats des produits sont toujours aussi rares que les matrices originales.

L'algorithme "plutôt naïf" (scan A par lignes; pour chaque 1 bit de la ligne A, OU le résultat avec la ligne correspondante de B) s'avère très efficace et ne nécessite que quelques milliers d'instructions CPU pour calculer un seul produit , il ne sera donc pas facile de le dépasser, et il n'est dépassable que par un facteur constant (car il y a des centaines de bits dans le résultat). Mais je ne perds pas espoir et je demande de l'aide à la communauté :)

jkff
la source
1
Je doute que nous puissions battre de façon significative une constante de 10 instructions machine par mot de sortie. Est-il possible qu'une forme implicite de sortie soit acceptable?
Warren Schudy
Oui tant qu'il peut être multiplié par Bs plus loin.
jkff
Quelles sont les opérations d'addition et de multiplication (pour les bits) sur lesquelles la multiplication matricielle est définie? Votre algorithme naïf suggère que la réponse est "ou" et "et" respectivement, mais c'est une multiplication matricielle assez étrange car ceux-ci ne définissent pas un champ. Voulez-vous dire "xor" au lieu de "ou"?
Warren Schudy
Non, je veux dire "ou" et "et". Je n'ai pas besoin des opérations pour définir un champ, c'est en fait un problème semblable à l'accessibilité du graphe (je calcule la composition de plusieurs fonctions un-à-plusieurs).
jkff

Réponses:

11

J'étais réticent à répondre à cette question, car le seul résultat théorique que je connaisse dans ce sens a mon nom sur le papier ...

Théoriquement, il est possible de prétraiter une matrice booléenne dense afin que les multiplications matricielles-vecteurs éparses avec (sur la semi-continuité de OR et AND) puissent être effectuées plus rapidement que le temps d'exécution naïf. Probablement une quantité importante de piratage serait nécessaire pour l'implémenter dans la pratique, mais je pense que cela se passerait bien dans la pratique pour un assez grand et la bonne implémentation.A A nn×nAAn

(Remarque: cet algorithme n'est vraiment utile que dans le cas où une matrice est dense et l'autre est clairsemée. Ce cas apparaît souvent, par exemple, lors du calcul de la fermeture transitive d'un graphe clairsemé, la matrice de fermeture transitive finira par devenir dense par rapport à la matrice d'adjacence d'origine.)

Le papier est

Guy E. Blelloch, Virginia Vassilevska, Ryan Williams: Une nouvelle approche combinatoire pour les problèmes de graphes clairsemés. ICALP (1) 2008: 108-120

et le résultat pertinent de l'article est que pour chaque , il existe un algorithme de temps qui, étant donné 0-1 matrice , les opérations suivantes sont prise en charge:O ( n 2 + ε ) n × n Aε>0O(n2+ε)n×nA

- Pour tout vecteur avec seulement zéros, peut être calculé en temps , où , sont des paramètres libres satisfaisant . (Un bon réglage est et , de sorte que le temps d'exécution est d'environ pour toute constante souhaitée .t A v O ( n ( t / k + n /) / log n ) kvtAvO(n(t/k+n/)/logn)k(k)nε=logcnk=ε(logn)/loglognnt/logn+n2/logcnc

- Les mises à jour des lignes et des colonnes vers peuvent être calculées en temps .AO(n1+ε)

Nous avons utilisé cette structure de données pour donner des algorithmes théoriques plus rapides pour APSP dans des graphiques clairsemés non pondérés.

Ryan Williams
la source
3
Je viens de remarquer que vous supposez également que la sortie de la multiplication matricielle est également clairsemée. Dans ce cas, il existe des algorithmes encore plus rapides; effectuez une recherche sur le Web pour "multiplication de matrice sensible à la sortie".
Ryan Williams
Ryan Williams - J'ai une question rapide: connaissez-vous ou avez-vous exploré une méthode généralisant les matrices clairsemées (plutôt que simplement booléennes)? {1,0,1}
Alexandre Cassagne
5

Je pense que ce que vous appelez est une matrice "hypersparse" (nnz <n). J'ai écrit un article il y a quelques années sur la façon de les multiplier. Il s'agit essentiellement d'une fusion de produits externes avec une fusion multidirectionnelle intelligente pour éliminer la réalisation de triplets intermédiaires.

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

Aydin Buluc
la source