La complexité de calcul de la multiplication matricielle

14

Je recherche des informations sur la complexité de calcul de la multiplication matricielle des matrices rectangulaires. Wikipedia indique que la complexité de la multiplication de par B R n × p est O ( m n p ) (multiplication des manuels scolaires).ARm×nBRn×pO(mnp)

J'ai un cas où et n sont beaucoup plus petits que p , et j'espérais obtenir une meilleure complexité que linéaire en p , au prix de rendre la dépendance de m et n pire que linéaire.mnppmn

Des idées?

Merci.

Remarque: la raison pour laquelle j'espère que cela est possible est dû au résultat bien connu d'une dépendance inférieure à cubique en si m = n = p (lorsque les matrices sont toutes des carrés).pm=n=p

enquêteur
la source
8
La complexité d'un algorithme (séquentiel) ne peut pas être inférieure à la taille de sa sortie. Pour votre problème, pouvez-vous représenter l'entrée et la sortie en utilisant un espace qui est sublinéaire en p?
Colin McQuillan
les éléments sont-ils pour la plupart différents de zéro ou souvent nuls? c'est-à-dire clairsemé? cela conduit certainement à diverses optimisations. il semble également que la SVD [décomposition en valeurs singulières] pourrait être pertinente sur la base de la réponse actuelle se référant aux approximations.
vzn

Réponses:

13

Les travaux classiques de Coppersmith montrent que pour certains , on peut multiplier une matrice n × n α par une matrice n α × n dans les opérations arithmétiques ˜ O ( n 2 ) . C'est un ingrédient crucial du récent résultat célèbre de Ryan Williams.α>0n×nαnα×nO~(n2)

François le Gall a récemment amélioré le travail de Coppersmith, et son article vient d'être accepté au FOCS 2012. Pour comprendre ce travail, vous aurez besoin de quelques connaissances de la théorie de la complexité algébrique. L'article de Virginia Williams contient quelques conseils pertinents. En particulier, le travail de Coppersmith est complètement décrit dans Algebraic Complexity Theory , le livre.

Un autre volet de travail se concentre sur la multiplication approximative des matrices . Vous pouvez consulter ce travail de Magen et Zouzias. Ceci est utile pour manipuler de très grandes matrices, par exemple en multipliant une matrice et une matrice N × n , où N n .n×NN×nNn

L'approche de base consiste à échantillonner les matrices (cela correspond à une réduction de dimensionnalité aléatoire) et à multiplier les matrices échantillonnées beaucoup plus petites. L'astuce consiste à savoir quand et dans quel sens cela donne une bonne approximation. Contrairement au précédent volet de travail qui est complètement impraticable, les algorithmes d'échantillonnage sont pratiques et même nécessaires pour traiter de grandes quantités de données.

Yuval Filmus
la source
Juste une note: on sait (depuis novembre 2010) que la multiplication matricielle rectangulaire n'est pas nécessaire pour résoudre ACC SAT. (Ce qui est bien, car la matrice rectangulaire mult est "galactique" et complexe.)
Ryan Williams