Complexité des puissances de la matrice de calcul

Je suis intéressé par le calcul de la $n$ ième puissance d'un la matrice . Supposons que nous ayons un algorithme de multiplication matricielle qui s'exécute en temps . Ensuite, on peut facilement calculer en temps. Est-il possible de résoudre ce problème en moins de temps? $n\times n$ $A$ $\mathcal{O}(M(n))$ $A^n$ $\mathcal{O}(M(n)\log(n))$

Les entrées de matrice peuvent, en général, provenir d'un semiring mais vous pouvez assumer une structure supplémentaire si cela vous aide.

Remarque: Je comprends qu'en calculant en temps donnerait un algorithme pour l'exponentiation. Mais, un certain nombre de problèmes intéressants se réduisent au cas particulier de l'exponentiation matricielle où m = , et je n'ai pas pu prouver la même chose à propos de ce problème plus simple. $A^m$ $o(M(n)\log(m))$ $o(\log m)$ $\mathcal O(n)$

algorithms complexity-theory time-complexity computer-algebra Shitikanth
la source

quelles sont les entrées de la matrice? Entiers?

Kaveh

Les entrées peuvent, en général, provenir d'un semiring mais vous pouvez assumer une structure supplémentaire si cela vous aide.

Shitikanth

Je n'ai pas pu obtenir une réduction de la multiplication à la quadrature de la méthode proposée ci-dessus (c'est-à-dire en utilisant ). Cependant, utiliser fonctionne. Cependant, cela ne donne qu'un sur le calcul de .

(A \pm B)^{2}

$(A\pm B)^2$

{(\begin{array}{cc} 0 & A \\ B & 0 \end{array})}^{2}

$\left( \begin{array}{cc} 0 & A \\ B & 0 \end{array} \right)^2$

Ω (M (n))

$\Omega(M(n))$

A^{n}

$A^n$

Shitikanth

Réponses:

Si la matrice est diagonalisable, la prise de la ème puissance peut se faire dans le temps où $n$

O (D (n) + n \log n)

$O(D(n)+ n\log n)$

est le temps de diagonaliser

D (n)

$D(n)$

A

$A$

Pour compléter les détails, si avec une diagonale , alors $A=P^{-1}DP$ $D$

A^{n} = (P^{- 1} D P)^{n} = P^{- 1} D^{n} P

$A^n = (P^{-1}DP)^n = P^{-1}D^nP$

et peut être calculé en prenant simplement chaque élément de la diagonale (chaque valeur propre de $D^n$ ) à la e puissance. $A$ $n$

A sonné.
la source

Même si la matrice est diagonalisable, les algorithmes les plus connus pour la composition par eigend prennent du temps

. En utilisant l'algorithme Coppersmith-Winograd, nous avons déjà un algorithme

pour calculer

O (n^{3})

$O(n^3)$

O (n^{2.3727} \log (m))

$O(n^{2.3727}\log(m))$

A^{m}

$A^m$

Shitikanth

(1) Le temps que vous citez n'est pas celui de Coppersmith-Winograd (comme vous le savez probablement). (2) Tous les algorithmes de cette forme ne fonctionnent que pour les anneaux; ils ne fonctionnent pas pour les semirings généraux (comme vous le permettez dans votre question).

Ryan Williams

Une bonne solution est la SVD de décomposition en valeurs singulières . Étant donné une matrice réelle de rang complet , SVD la sépare en où est une matrice diagonale, dans le temps . Par les propriétés de SVD, , donc seule la matrice diagonale doit être exponentiée, et cela peut être fait en $n\times n$ $A$ $A=U\Sigma U^T$ $\Sigma$ $O(n^3)$ $A^m = U \Sigma^m U^T$ $O(n\log m)$ temps de . Réalisation de la multiplication finale prend , donc nous avons tout à fait $U \times \Sigma^m \times U^T$ $O(n^{2.3727})$ opérations. $O(n^3 + n \log m)$

Mise à jour après commentaire Le fait est qu'une fois le SVD trouvé, toute puissance ne prend que pour calculer par votre propre algorithme CW. Mais ce n'est pas votre question: s'il y avait vraiment un algorithme , il se convertirait immédiatement en $O(n^{2.3727}+n \log m)$ $o(M(n)\log(m))$ $o(\log n)$ algorithme pour les entiers. Je soupçonne qu'un tel n'existe pas.

PKG
la source

Puisque l'algorithme de Coppersmith – Winograd trouve le produit de deux matrices en temps

, nous avons déjà un algorithme

pour calculer

. Je suis intéressé à savoir si cela peut être amélioré sans nécessiter un meilleur algorithme de multiplication matricielle, en particulier pour

O (n^{2.3727})

$O(n^{2.3727})$

O (n^{2.3727} \log (m))

$O(n^{2.3727}\log(m))$

A^{m}

$A^m$

m = O (n)

$m=O(n)$

Shitikanth

la SVD ne donne pas

en général - la matrice de droite est

A = U Σ U^{⊤}

$A = U \Sigma U^\top$

V \neq U^{⊤}

$V \ne U^\top$

Suresh

C'est un peu trompeur d'avoir

pour la puissance aussi, donc je vais utiliser

. Si

il faut

temps pour trouver

, ce qui équivaut à multiplier des entiers

n

$n$

m

$m$

n = 1

$n=1$

O (M (1) \log m

$O(M(1)\log m$

A^{m}

$A^m$

PKG

\log m

$\log m$

Cela n'était pas clair à partir de votre question, comme indiqué.

PKG