Comment calculer la puissance n ieme d’une matrice ?

Réponse publiée sur Quora

Pour n “grand”, le mieux est d’utiliser l’Exponentiation rapide .

par exemple pour n=13,

on calcule $A^2=A\times A$, puis $A^4=A^2\times A^2$, puis$A^8=A^4\times A^4$

et là on s’arrête parce que 8 > 13/2

et yapluka calculer $A^{13}=A^8\times A^4\times A$

et on a le résultat en 5 multiplications au lieu de 13.

Ca paraît être une petite amélioration, mais pour$n=10^{19}$ il suffit de 63 multiplications …

C’est l’algo utilisé par des librairies comme NumPy (numpy.linalg.matrix_power ) mais comme il travaille en nombres flottants ils bute assez vite sur de grands nombres, donc j’ai implanté

Goulib.math2 mod_mathpow pour calculer le 10'000'000'000'000'000'000 ème terme de la suite de Fibonacci .

Ouais, parce que figurez vous qu’on peut calculer ce terme en 63 multiplications de matrices 2x2 …