Matrix-Inversion: Alternativen?

Bashar

Ich geh an die Frage mal mit Klein-Fritzchen-Logik ran.

Erstens hast du eine Matrix über einem endlichen Körper. Damit kommt nur exakte Rechnung in Frage, es gibt keine Fragen der Genauigkeit, Kondition, Konvergenz, keine approximativen Verfahren.

Zweitens, du willst dasselbe Gleichungssystem 1 Millionen mal mit verschiedenen rechten Seiten lösen. Invertieren einer n×n-Matrix ist auch nur das Lösen desselben Gleichungssystems mit den n Einheitsvektoren auf der rechten Seite. Die kannst du zu den 1 Millionen dazutun, damit nimmt das Berechnen der Inversen höchstens ca. 5% der Gesamtzeit in Anspruch -- möglicherweise weniger, wenn du einen schlaueren Algorithmus findest. (Es sei denn vielleicht, die Vektoren auf der rechten Seite liegen alle in einem kleinen Unterraum oder so.)

Bengo

Bashar schrieb:

Ich geh an die Frage mal mit Klein-Fritzchen-Logik ran.

Erstens hast du eine Matrix über einem endlichen Körper. Damit kommt nur exakte Rechnung in Frage, es gibt keine Fragen der Genauigkeit, Kondition, Konvergenz, keine approximativen Verfahren.

Ich vermute es ist eine Matrix über dem Körper der Reellen Zahlen, und damit nicht endlich, ja nicht mal abzählbar.
Wenn es eine Matrix über einem endlichen Körper wäre, wäre es glaube recht effizient zu lösen, in dem man einfach so lange mit sich selbst multipliziert, bis I raus kommt. (Was schneller ist, muss man aber im speziellen Testen)

Bashar

Bengo schrieb:

Ich vermute es ist eine Matrix über dem Körper der Reellen Zahlen

Im Anfangsposting steht $GF(2^{16})$ .

Bengo

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

volkard

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

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ß werden

Hab 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?

Jester

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.

Bengo

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?