Matrix-Inversion: Alternativen?
-
Bengo schrieb:
Ich vermute es ist eine Matrix über dem Körper der Reellen Zahlen
Im Anfangsposting steht .
-
Ups, ok 2^16 ist leider recht viel, aber da so viele Nullen drin vorkommen, würd ich wirklich mal versuchen die Ordnung der Matrix in der Gruppe der Quadratischen Matrizen zu bestimmen, da diese endliche Ordnung hat.
Theoretisch kann die Ordnung aber leider schon noch sehr groß werden
-
mma schrieb:
Die Matrix ist allerdings recht schwach besetzt.
Sie entspricht I, wobei etwa 10% der Zeilen voll besetzt sind.
(Entsprechend speichere ich nur die voll besetzten Zeilen.)Vielleicht ist https://en.wikipedia.org/wiki/Invertible_matrix#Blockwise_inversion interessant.
"This strategy is particularly advantageous if A is diagonal and the Schur complement of A is a small matrix, since they are the only matrices requiring inversion."
-
Bengo schrieb:
Ups, ok 2^16 ist leider recht viel, aber da so viele Nullen drin vorkommen, würd ich wirklich mal versuchen die Ordnung der Matrix in der Gruppe der Quadratischen Matrizen zu bestimmen, da diese endliche Ordnung hat.
Theoretisch kann die Ordnung aber leider schon noch sehr groß werdenHab mir noch mal ein paar Gedanken darüber gemacht.
Du kannst Zeilenweise vorgehen. Du nimmst betrachtest eine Zeile und multiplizierst die Matrix immer wieder von rechts. Irgentwann wird die Zeile zu einer Identitätszeile (also so wie in I). Dann nimmst du dir diese Matrix und multiplizierst die immer wieder von rechts, bis eine neue Identitätszeile entsteht. Irgentwann hast du I und damit die Ordunung, wenn du die hast, kannst du mit einem "quadrieren und halbieren" algo das Inverse ausrechnen. Das kann immernoch langsamer sein, als Gauß-Jordan, aber je nachdem wie deine Matrix aussieht, geht es schneller. Besonders wenn du es schaffen solltest, in einem kleinern Körper zu rechnen zu können.
-
Darf ich mal wegen der Nomenklatur fragen, ob dieses schwach besetzt bedeutet, dass die entsprechenden Zeilen von denen angenommen wird, dass sie der Einheitsmatrix entsprechen, wirklich 000010000 sind, oder geht es hier darum, dass das nur so ungefährt gilt und man die Elemente nicht vernachlässigen darf?
-
decimad schrieb:
Darf ich mal wegen der Nomenklatur fragen, ob dieses schwach besetzt bedeutet, dass die entsprechenden Zeilen von denen angenommen wird, dass sie der Einheitsmatrix entsprechen, wirklich 000010000 sind, oder geht es hier darum, dass das nur so ungefährt gilt und man die Elemente nicht vernachlässigen darf?
Weišt du was GF(2^16) bedeutet?
-
Mir scheint, aufgrund Deine Frage, dass sich meine Frage erübrigte, wüsste ich es... Aber alles Mutmaßungen!
-
Hrmmm, bedeutet das in diesem Fall 16-Bit Zahlen irgendeiner Kodierung? Dann käme meiner Logik nach natürlich nicht in Betracht, dass eine schwach besetzte Matrix Elemente ungefähr gleich Null besitzt... Folgere ich da richtig?
Darf ich weiter davon ausgehen, dass im Moment schon nur eine 0.1n x 0.1n - Matrix-Inversion durch gewisse Umformungen betrieben wird?
-
Wobei ja nun eigentlich auch Q0.16 GF(2^16) wäre? Also war wohl mein Verständnis doch nicht so gut... hrmmm.
-
decimad schrieb:
Hrmmm, bedeutet das in diesem Fall 16-Bit Zahlen irgendeiner Kodierung? Dann käme meiner Logik nach natürlich nicht in Betracht, dass eine schwach besetzte Matrix Elemente ungefähr gleich Null besitzt... Folgere ich da richtig?
Darf ich weiter davon ausgehen, dass im Moment schon nur eine 0.1n x 0.1n - Matrix-Inversion durch gewisse Umformungen betrieben wird?Zumindest eine 0.1n x n Matix, die Zeilen können glaube komplett voll sein.
Und was ist Q0.16?