Komplexität der Rechenmatrixleistungen

14

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?nn×nAO(M(n))AnO(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.Amo(M(n)log(m))o(logm)O(n)

Shitikanth
quelle
Was sind die Einträge der Matrix? Ganze Zahlen?
Kaveh
1
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 ( 0 A B 0 ) 2 funktioniert jedoch. Doch nur das gibt einen Ω ( M ( n ) ) auf die Berechnung A n . (A±B)2(0AB0)2Ω(M(n))An
Shitikanth

Antworten:

10

Wenn die Matrix diagonalisierbar ist, kann die te Potenz in der Zeit O ( D ( n ) + n log n ) genommen werden, wobei D ( n ) die Zeit zur Diagonalisierung von A ist .n

O(D(n)+nlogn)
D(n)A

Nur um die Details zu vervollständigen, wenn mit einem Diagonale D , dann A n = ( P - 1 D P ) n = P - 1 D n PA=P1DPD

An=(P1DP)n=P1DnP

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

Ran G.
quelle
6
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 O ( n 2,3727 log ( m ) ) Algorithmus zur Berechnung A m . O(n3)O(n2.3727log(m))Am
Shitikanth
1
(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
5

Ein guter Ausweg ist Singular Value Decomposition SVD . Bei einer reellen Matrix A mit vollem Rang teilt die SVD sie in der Zeit O ( n 3 ) in A = U Σ U T auf, wobei Σ eine diagonale Matrix ist . Aufgrund der Eigenschaften von SVD gilt A m = U Σ m U T , sodass nur die Diagonalmatrix potenziert werden muss und dies in O ( n log m ) erfolgen kann.n×nAA=UΣUTΣO(n3)Am=UΣmUTO(nlogm)U×Σm×UTO(n2.3727)O(n3+nlogm)

O(n2.3727+nlogm)o(M(n)log(m))o(logn)

PKG
quelle
O(n2.3727)O(n2.3727log(m))Amm=O(n)
1
die SVD gibt im Allgemeinen nicht - die rechte Matrix ist V U A=UΣUVU
Suresh
1
Es ist ein bisschen irreführend, für die Leistung zu haben , also verwende ich m . Wenn n = 1 ist , sollte O ( M ( 1 ) log m Zeit brauchen , um A m zu finden , was der Multiplikation von ganzen Zahlen entsprichtnmn=1O(M(1)logmAm
PKG
2
logm
1
Wie bereits erwähnt, war dies aus Ihrer Frage nicht ersichtlich.
PKG