Existe-t-il des algorithmes d'exponentiation à matrice parallèle plus efficaces que la multiplication séquentielle?

Il faut trouver la puissance (entier positif) de la matrice des nombres réels. Il existe de nombreux algorithmes de multiplication matricielle efficaces (par exemple, certains algorithmes parallèles sont ceux de Cannon, DNS ), mais existe-t-il des algorithmes qui sont exactement destinés à trouver la puissance de la matrice et qui sont plus efficaces que l'exécution séquentielle de la multiplication matricielle? Je suis particulièrement intéressé par les algorithmes parallèles.

Si vous avez plusieurs processeurs qui peuvent fonctionner en parallèle, vous pouvez calculer n'importe quelle puissance jusqu'à la puissance (2 ^ k) en k étapes. Par exemple: Pour calculer , vous calculez:$M^{15}$

Étape 1: Calculez$M^2$

Étape 2: Calculez et$M^3 = M^2 * M$$M^4 = M^2 * M^2$

Étape 3: Calculez et$M^7 = M^4 * M^3$$M^8 = M^4 * M^4$

Étape 4: Calculez$M^{15} = M^8 * M^7$

C'est une multiplication de plus que de calculer en trois multiplications et d'élever à la troisième puissance dans deux autres multiplications, mais devrait être plus rapide si vous avez deux processeurs. Pour des puissances élevées arbitraires, vous aurez besoin de plus de processeurs.$M^5$$M^5$

Si vous utilisez un algorithme de force brute pour la multiplication, en multipliant ligne par colonne, vous pouvez gagner du temps en calculant une ligne d'un produit, puis en utilisant immédiatement cette ligne pour le produit suivant. Cela aiderait au calcul de où nous pouvons commencer à calculer dès que la première ligne de a été calculée; ce ne serait pas très utile avec car nous avons besoin à la fois de lignes et de colonnes de . Pour les grandes puissances, vous pouvez probablement définir les puissances à calculer.$M^3$$M^3$$M^2$$M^4$$M^2$

Et après avoir publié cela , il devient évident que vous pouvez utiliser plusieurs processeurs très facilement: Vous commencez par le calcul de la première rangée de . Lorsque vous avez cette ligne, vous disposez de toutes les informations dont vous avez besoin pour calculer la première ligne de , vous calculez donc la deuxième ligne de et la première ligne de en parallèle. Ensuite, vous pouvez calculer la troisième rangée de , la deuxième rangée de et la première rangée de en parallèle et ainsi de suite.$M^2 = M * M$$M^3 = M^2 * M$$M^2$$M^3$$M^2$$M^3$$M^4$

Cela fera beaucoup plus d'opérations que nécessaire (par exemple, 14 multiplications matricielles pour au lieu du minimum 5 ou 6 de la méthode en quatre étapes). Si la puissance n'est pas importante par rapport au nombre de processeurs, ce sera encore plus rapide. Mais le calcul de avec quatre processeurs utilisant cette méthode sera inefficace; le faire de manière optimale serait un problème intéressant.$M^{15}$$M^{1000}$

Combinaison d'approches: en utilisant quatre processeurs par exemple, vous pouvez calculer AB, ABC, ABCD et ABCDE presque en parallèle en calculant chaque produit une ligne à la fois. Cela permet de calculer les quatre à utilisant quatre processeurs à peu près en même temps qu'un produit avec un processeur.$M^2$$M^5$

Compte tenu de ces quatre résultats et du M d'origine, vous pouvez à nouveau calculer quatre des matrices à , à condition que les matrices aient au plus cinq puissances les unes des autres. Ainsi, chaque puissance jusqu'à peut être calculée en environ deux fois le temps d'un produit matriciel à processeur unique.$M^6$$M^{25}$$M^{25}$

Avec ces matrices calculées, toutes les matrices jusqu'à et certaines autres jusqu'à peuvent être calculées en trois fois le temps d'un seul produit matriciel si quatre processeurs sont disponibles. Avec k processeurs, cela devrait atteindre au moins la puissance .$M^{108}$$M^{125}$$k (k+1)^2$

Il y a deux niveaux que vous pouvez analyser les accélérations parallèles avec une exponentiation matricielle: le niveau "macro-algorithmique" qui décide quelles matrices multiplier, et le niveau "micro-algorithmique" où vous pouvez accélérer les multiplications elles-mêmes avec le parallélisme.

Pour ce dernier, Wikipedia suggère que pour multiplier une matrice par , nous pouvons atteindre une complexité de théoriquement avec un nombre illimité de processeurs, ou avec un algorithme parallèle plus réaliste .$n$$n$$O(\log^2(n))$$O(n)$

(Remarque: la page wikipedia est destinée au calcul matriciel général. Je ne sais pas si cela peut être parallélisé encore plus en utilisant les informations que nous mettons au carré une matrice.)

Pour les premiers, la question se transforme en combien de tours de multiplication matricielle sont nécessaires pour calculer pour une matrice ? (Je dis rounds, car toutes les multiplications dans un round donné peuvent se faire en parallèle).$A^m$$A$

L'algorithme séquentiel à battre, comme indiqué dans d'autres réponses, est l' exponentiation par quadrature . Cela vous permet de calculer dans multiplications.$A^k$$O(\log(k))$

La question est: pouvons-nous battre cela avec le parallélisme? Je prétends que la réponse est non.

La raison simple est que l'exponentiation par quadrature est essentiellement un algorithme de programmation dynamique; il vous permet de sauter tout le travail en réutilisant les sous-résultats, mais cela crée à son tour une dépendance aux données qui interdit le parallélisme. Si nous nous débarrassons de la dépendance aux données, mais nous augmentons également considérablement la quantité de travail que nous devons faire.

Pour mieux illustrer cela, regardons comment vous pourriez paralléliser la multiplication matricielle si nous ne faisions pas d'exponentiation. Supposons que vous cherchiez à paralléliser en multipliant matrices carrées distinctes :$k$

La manière naturelle de paralléliser ceci est évidente, vous devez abuser de l'associativité pour effectuer des multiplications au premier tour:$\frac{k}{2}$

À partir de cela, nous pouvons clairement multiplier nos matrices en tours de multiplication car nous réduisons la taille de notre problème de moitié à chaque tour.$k$$O(\log(k))$

Cependant, si nous devions effectuer l'exponentiation de cette façon, cela ressemblerait à ceci:

En d'autres termes, tout notre parallélisme nous gagne, c'est recalculer le même produit matriciel pour calculer ! Ainsi, si nous utilisons un algorithme mémorisé tel que l'exponentiation par quadrature, nous pouvons faire la même chose que l'algorithme parallèle à chaque cycle de multiplication.$A^2$

En mettant tout cela ensemble, si nous voulons calculer pour par matrice , la complexité parallèle est pour l'algorithme parallèle optimiste, ou pour le réaliste.$A^k$$n$$n$$A$$O(\log^2(n)\log(k))$$O(n\log(k))$

Si par séquentiel vous entendez multiplier fois, la solution consistant initialement à calculer uniquement les puissances pertinentes de (alias Exponentiation par quadrature ) est clairement meilleure pour les grands .$m$$\log m$$2$$m$

L'amélioration peut être spécifique à certains types de matrices. Par exemple, si votre matrice est diagonalisable, Ainsi, le calcul de la ème puissance est dans . m O ( 1 )