Comment calculer les puissances des matrices carrées?

Supposons que l'on nous donne une matrice , et laissons . À quelle vitesse peut-on calculer la puissance de cette matrice?$A \in \mathbb R^{N\times N}$$m \in \mathbb N_0$$A^m$

La deuxième meilleure chose par rapport au calcul de produits est d'utiliser une exponentation rapide, qui nécessite des produits matriciels .$m$$\mathcal O(\log m )$

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?$A$

$A^m$$O(\log m)$$N \times N$$A$$B$$2n \times 2n$$C$

$[0~~A]$

$[B~~0]$

$C$$n \times n$$C^2$$A\cdot B$