Komplexität der Rechenmatrixleistungen

Ich bin daran interessiert, die -te Potenz einer Matrix berechnen . Angenommen, wir haben einen Algorithmus für die Matrixmultiplikation, der in läuft . Dann kann man leicht in Zeit berechnen . Kann dieses Problem in kürzerer Zeit gelöst werden? $n$ $n\times n$ $A$ $\mathcal{O}(M(n))$ $A^n$ $\mathcal{O}(M(n)\log(n))$

Matrixeinträge können im Allgemeinen aus einem Semiring stammen, Sie können jedoch eine zusätzliche Struktur annehmen, wenn dies hilfreich ist.

Anmerkung: Ich verstehe, dass im Allgemeinen das Berechnen von in der Zeit einen Algorithmus für die Exponentiation ergeben würde. Einige interessante Probleme beschränken sich jedoch auf den Sonderfall der Matrixexponentiation mit m = , und ich konnte dies bei diesem einfacheren Problem nicht beweisen. $A^m$ $o(M(n)\log(m))$ $o(\log m)$ $\mathcal O(n)$

algorithms complexity-theory time-complexity computer-algebra Shitikanth
quelle

Was sind die Einträge der Matrix? Ganze Zahlen?

Kaveh

Die Einträge können im Allgemeinen aus einem Semiring stammen, Sie können jedoch eine zusätzliche Struktur annehmen, wenn dies hilfreich ist.

Shitikanth

Ich konnte mit der oben vorgeschlagenen Methode (dh mit

) keine Reduktion von Multiplikation zu Quadrierung erzielen . Die Verwendung von

funktioniert jedoch. Doch nur das gibt einen

auf die Berechnung

(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

Antworten:

Wenn die Matrix diagonalisierbar ist, kann die te Potenz in der Zeit wobei die Zeit zur Diagonalisierung von . $n$

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

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

D (n)

$D(n)$

A

$A$

Nur um die Details zu vervollständigen, wenn mit einem Diagonale , dann $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$

und kann berechnet werden, indem einfach jedes Element der Diagonale (jeder Eigenwert von ) zur ten Potenz genommen wird. $D^n$ $A$ $n$

Ran G.
quelle

Selbst wenn die Matrix diagonalisierbar ist, benötigen die bekanntesten Algorithmen für die Neuzusammenstellung

-Zeit . Unter Verwendung der Kupferschmiede-Winograd - Algorithmus, haben wir bereits ein

Algorithmus zur Berechnung

O (n^{3})

$O(n^3)$

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

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

A^{m}

$A^m$

Shitikanth

(1) Die von Ihnen angegebene Zeit ist nicht von Coppersmith-Winograd (wie Sie wahrscheinlich wissen). (2) Alle Algorithmen dieser Form funktionieren nur für Ringe; Sie funktionieren nicht für allgemeine Semirings (wie Sie in Ihrer Frage zulassen).

Ryan Williams

Ein guter Ausweg ist Singular Value Decomposition SVD . Bei einer reellen Matrix mit vollem Rang teilt die SVD sie in der Zeit in wobei eine diagonale Matrix ist . Aufgrund der Eigenschaften von SVD gilt , sodass nur die Diagonalmatrix potenziert werden muss und dies in $n\times n$ $A$ $A=U\Sigma U^T$ $\Sigma$ $O(n^3)$ $A^m = U \Sigma^m U^T$ $O(n\log m)$ $U \times \Sigma^m \times U^T$ $O(n^{2.3727})$ $O(n^3 + n \log m)$

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

PKG
quelle

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)$

die SVD gibt im Allgemeinen nicht

- die rechte Matrix ist

A = U Σ U^{⊤}

$A = U \Sigma U^\top$

V \neq U^{⊤}

$V \ne U^\top$

Suresh

Es ist ein bisschen irreführend,

für die Leistung zu haben , also verwende ich

. Wenn

, sollte

Zeit

, um

zu finden , was der Multiplikation von ganzen Zahlen entspricht

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$

Wie bereits erwähnt, war dies aus Ihrer Frage nicht ersichtlich.

PKG