Companion Matrix Komplexität

Ich weiß, das ist mehr eine Frage der Komplexitätstheorie als eine Programmierfrage, hoffe, ich mache nicht das Falsche, hier zu schreiben, entschuldige mich, wenn es der falsche Ort ist, aber ich hoffe, jemand von euch hat die Antwort. Und es ist sogar irgendwie Programm-bezogen, indem es eine Frage der Komplexitätstheorie ist.Companion Matrix Komplexität

Ich studiere linear wiederkehrende Sequenzen, und ich lese, dass, um den n-ten Wert der Sequenz zu erhalten, die Sie benötigen, um eine Leistung einer Companion-Matrix zu bekommen, fragte ich mich, ob es bekannt ist Algorithmus, um Kräfte dieser Art Matrix auf eine schnelle Art und Weise zu bekommen ..

ich kann nicht Beispiel geben Codierung, aber ich werde versuchen, Ihnen etwas mehr Erklärung zu bekommen:

homogene lineare wiederkehrende Folge von k-ten Auftrag:
s (n + k) = a (k-1) s (n + k-1) + a (k-2) s (n + k-2) + ... + a (0)
für n = 0,1, .. wobei s (i) der i-te Wert der Sequenz ist e und die a (i) sind Koeffizienten in einem algebraischen Feld.

A die Begleitmatrix der obigen Sequenz, wenn es:
(0 0 0 0 0 ... a (0))
(1 0 0 0 0 ... a (1))
(0 1 0 0 ... 0 a (2))
(.. .. .. .. .. .. .. .. ..)
(0 0 0 0 ... 1 a (k -1))
Außerdem Theorie besagt, dass für die Zustandsvektoren der Folge haben wir:
s (n) = s (0) A^n für n = 0,1, ..
das ist es, vielen dank für die Hilfe.

Quelle

2009-04-07 luiss

Die übliche Strategie für Potenzen einer Matrix schnell zu finden, ist es zu diagonalise (führen Eigenvektor Zersetzung):

A = P ^-1 D P

wobei D eine Diagonalmatrix ist. Sie können dann

A ⁿ = P ^-1 D ⁿ P

wo D ⁿ schnellen A an den Strom n erhöhen durch die Berechnung zu berechnen ist, weil es eine diagonale Matrix ist, so Sie nehmen nur die Kräfte jedes Elements getrennt.

Allerdings sind nicht alle Matrizen diagonalisierbar - ich weiß nicht, ob Ihre Begleitmatrix sein wird oder nicht. Sie könnten auf jeden Fall this Wikipedia article hilfreich finden.

Quelle

2009-04-07 14:48:38

Es ist nicht immer diagonalizable, nur dann, wenn die Wurzeln der charakteristischen polynoials verschieden sind, trotzdem ok, es ist gut, aber ich frage mich, ob es eine Möglichkeit, die Struktur der Matrix, ty auszubeuten waren – luiss

können Sie berechnen die n te Potenz einer Matrix M mit O(log n) Matrixprodukte:

wenn n=0 Rückkehr I
wenn n gerade ist, berechnen N=M^n/2 und zurück N*N
Wenn n ungerade ist, berechnen Sie N=M^n-1 und zurück M*N

Quelle

2009-04-26 12:27:02

Es tut mir leid, aber ich kann nicht herausfinden, wie Sie es in O (log n) machen können, ich denke, dass jede Matrixmultiplikation noch O (n^2) ist, wobei n die Anzahl der Zeilen ist (angenommen eine quadratische Matrix)), ist das nicht so? – luiss

Oh ok, habe nicht gut gelesen: D es ist O (log n) * Kosten eines Matrixprodukts, also wird es O (n^2 log n), oder? Danke, aber ich denke, das ist nicht das, was ich brauche. Ich habe mich nach einer Art Exploit der Matrix der besonderen Art gefragt ... – luiss

Nicht genau. Das Matrixprodukt ist (vermutlich) härter als das, aber die Größe der Matrix, etwa m × m, ist völlig unabhängig vom Exponenten n, also wäre es O (m^2.807 log n) mit dem Algorithmus von Strassen oder O (m^3 log n) mit dem naiven Algorithmus. –

Companion Matrix Komplexität

Antwort

Verwandte Themen