Gibt es einen O (log n) -Algorithmus für die Matrixexponentiation?

Gibt es einen Algorithmus, um eine Matrix in Zeit auf die te Potenz zu bringen ? $n$ $O(\log n)$

Ich habe online gesucht, war aber bisher erfolglos.

algorithms matrices Jack H.
quelle

Sie meinen, Sie haben eine Matrix mit fester Größe? Wenn Ihre Matrix die Größe hat, können Sie nicht erwarten, einen

-Algorithmus zu finden.

m

$m$

O (l o g n)

$O(log \ n)$

Menschen bezeichnen dieses Problem normalerweise als Matrix-Powering. Matrixexponentiation bedeutet,

e^{X}

$e^X$

Shitikanth

@ Shitikanth Ok, danke. Ich werde das jetzt ändern.

Jack H

Antworten:

Hier ist der Pseudocode für einen -Matrix-Exponentiationsalgorithmus. Beachten Sie, dass der Operator * die gewöhnliche Matrixmultiplikation bezeichnet. $O(\lg n)$

MATHPOWER (M, n)
if n == 1
    then return M
else
    P = MATHPOWER (M, floor(n/2))
    if n mod 2 == 0
        then return P * P
    else
        return P * P * M

Massimo Cafaro
quelle

Für Menschen aus der Zukunft ist dies eine schreckliche Antwort. Es funktioniert O (n ^ 3 * log (n)), wenn stattdessen O (n ^ 3) -Algorithmen vorhanden sind. Siehe die Antwort von Yuval unten. In der Praxis erfolgt dies normalerweise durch SVD-Zerlegung, dann Anheben der N Elemente der D-Matrix auf die Potenz und erneutes Multiplizieren der Matrix.

Michael O

@ Michael O, ich denke du hast den Punkt wirklich verpasst. Sie haben falsch verstanden, wonach das OP gefragt hat, dh wie eine Matrix in auf die te Potenz . Der Schlüssel ist, dass das OP nur verlangt, dass die Anzahl der durchgeführten Schritte , nicht die Gesamtkomplexität, da dies auch die Berücksichtigung der Matrixreihenfolge erfordern würde.

n

$n$

O (\lg n) s t e p s

$O(\lg n) steps$

O (\lg n)

$O(\lg n)$

Massimo Cafaro

Es ist offensichtlich, dass der vorgeschlagene Divide and Conquer-Ansatz nur dann die Worst-Case-Komplexität , wenn die Matrixreihenfolge , da in diesem Fall die entsprechende Wiederholungsgleichung (als Beispiel kann für eine 3 × 3-Matrix eine Matrixmultiplikation unter Verwendung einer konstanten Anzahl von Skalarmultiplikationen und -additionen durchgeführt werden). Eine mögliche Anwendung des von mir angegebenen Algorithmus besteht darin, die te Fibonacci-Zahl zu berechnen , indem die Matrix mit den Einträgen berechnet wird nach der ten Potenz.

O (\lg n)

$O(\lg n)$

O (1)

$O(1)$

T (n) = T (n / 2) + O (1)

$T(n) = T(n/2) + O(1)$

n

$n$

a_{11} = 1, a_{12} = 1, a_{21} = 1, a_{22} = 0

$a_{11} = 1, a_{12} = 1, a_{21} = 1, a_{22} = 0$

n

$n$

Massimo Cafaro

Beachten Sie zum Schluss auch, dass dies bereits geklärt und vollständig verstanden wurde: Schauen Sie sich einfach den Kommentar zu der Frage von @ user742 an.

Massimo Cafaro

Es gibt zwei andere Algorithmen, die relevant sein können oder nicht. Der erste Algorithmus diagonalisiert Ihre Matrix (was normalerweise möglich ist) und schreibt sie als , wobei im Allgemeinen einen komplexen Wert haben kann. Sie berechnen dann . Beachten Sie, dass es sehr einfach ist, eine Diagonalmatrix auf die te Potenz anzuheben . Wenn nicht diagonalisierbar ist, finden Sie seine Jordan-Form und fahren wie zuvor fort (jetzt müssen Sie auch einige Binomialkoeffizienten berechnen). Dieser Algorithmus ist wahrscheinlich nicht numerisch stabil. $M = PDP^{-1}$ $M,D$ $M=PD^nP^{-1}$ $n$ $M$

Ein anderer Algorithmus nutzt die Tatsache, dass sein charakteristisches Polynom (oder sogar sein minimales Polynom) erfüllt. Angenommen, für einige , sagen wir das charakteristische Polynom. Dann können wir über berechnen und dann ersetzen . Das heißt, wir berechnen als Polynom, unter Verwendung der Tatsache , daß , und nur am Ende Ersatz werden die Werte von . Wir könnten sogar alle notwendigen Potenzen von und alle Werte von für $M$ $P(M) = 0$ $P$ $M^n$ $\mathbb{R}[M]/(P(M))$ $M$ $M^n$ $P(M) = 0$ $M$ $M$ $M^k \pmod{P(M)}$ $k < 2\deg P-1$ , und dann könnte dieser Algorithmus schneller sein als der Algorithmus, lautet die Antwort von Massimo Cafaro. Es ist möglicherweise numerisch stabiler als der vorherige Algorithmus.

Yuval Filmus
quelle