Comment calculer les puissances des matrices carrées?

16

Supposons que l'on nous donne une matrice , et laissons . À quelle vitesse peut-on calculer la puissance de cette matrice?UNERN×NmN0UNEm

La deuxième meilleure chose par rapport au calcul de produits est d'utiliser une exponentation rapide, qui nécessite des produits matriciels .mO(Journalm)

Pour les matrices diagonalisables, la décomposition des valeurs propres peut être utilisée. C'est la généralisation naturelle, la décomposition de Jordan, est instable sous pertubation et ne compte donc pas (afaik).

L'exponentiation matricielle peut-elle être accélérée dans le cas général?

Une exponentation rapide suggère qu'une variation de cette question est également utile:

Le carré d'une matrice générale peut-il être calculé plus rapidement que par les algorithmes de multiplication matriciels connus?UNE

shuhalo
la source
Si vous vous souciez de la stabilité sous perturbations, une exponentiation rapide ne semble pas non plus sûre.
MCH
Eh bien, je suppose que ce n'est pas moins sûr que la multiplication répétée, qui est aussi sûre que l'exponentation scalaire, n'est-ce pas?
shuhalo

Réponses:

20

UNEmO(Journalm)N×NUNEB2n×2nC

[0  UNE]

[B  0]

Cn×nC2UNEB

Ryan Williams
la source
UNEmO(n)O(M(n)Journal(n))Ω(M(n))