Complexité spatiale de l'algorithme Coppersmith – Winograd

L'algorithme de Coppersmith – Winograd est l'algorithme connu asymptotiquement le plus rapide pour multiplier deux matrices carrées. Le temps d'exécution de leur algorithme est O ( n 2.376 ) qui est le plus connu à ce jour. Quelle est la complexité spatiale de cet algorithme? Est-ce en Θ ( n 2 ) ?$n \times n$$O(n^{2.376})$$\Theta(n^2)$

Oui, tous les algorithmes qui dérivent de l'algorithme original de Strassen (cela inclut les algorithmes plus connus pour la multiplication matricielle, mais pas tous - voir les commentaires) ont une complexité spatiale Θ ( n 2 ) . Si vous pouviez trouver un algorithme de temps n 3 - ε avec une complexité spatiale de p o l y ( log n ) , ce serait une grande avancée. Une application serait un temps 2 ( 1 - ε ) n , p o l y $n^{3-\varepsilon}$$\Theta(n^2)$$n^{3-\varepsilon}$$poly(\log n)$$2^{(1-\varepsilon)n}$ algorithme d'espace pour le problème Subset-Sum.$poly(n)$

Cependant, il existe certains obstacles à un tel résultat. Pour certains modèles de calcul, il existe des bornes inférieures assez fortes pour le produit spatio-temporel de la multiplication matricielle. Des références comme Yesha et Abrahamson vous donneront plus d'informations.