LGS in Z/2Z < Gleichungssysteme < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:55 So 27.11.2011 | | Autor: | Rat62 |
| Aufgabe | | Zu lösen ist ein LGS in [mm] \IZ/2\IZ [/mm] mit [mm] n^2 [/mm] Variablen. Die Matrix ist dünn besetzt, in jeder Zeile sind höchstens 2n-1 Einträge [mm] \not= [/mm] 0. |
Ich habe das Gaußsche Eliminationsverfahren in Python programmiert und benutze Bit-Operatoren (and für Multiplikation, xor für Addition) auf großen Ganzzahlen. Das funktioniert ganz gut, berücksichtigt aber nicht, dass die Matrix dünn besetzt ist. Laufzeit bei n=145 also [mm] \approx [/mm] 21000 Variablen ist 50 Minuten auf meinem 5 Jahre alten Laptop. Ich möchte Aufgaben mit n=500 in erträglicher Zeit (< 1h) lösen können.
Ich freue mich über Tipps und Stichworte zum Weiter-Googlen und -Lernen. Namen und Beschreibungen von Algorithmen mit Pseudocode o.ä. sind mir lieber als fertige Lösungen in C.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Ich kenne das Krylow-Unterraum-Verfahren für allgemein dünnbesetzte Matrizen.
Für Google würde ich soetwas wie
- sparse integer matrices "Z/2Z"
- sparse integer matrices "mod 2"
- sparse integer matrices "GF(2)"
- binary sparse matrix solve
oder allgemein
- solve sparse matrices
vorschlagen. Meistens wird man im Englischen fündiger.
http://en.wikipedia.org/wiki/GMRES
Hat die Matrix noch eine Struktur (Bandmatrizen?)?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:31 So 27.11.2011 | | Autor: | Rat62 |
Vielen Dank für die Hinweise. Werde ich wohl ein bisschen dazulernen (müssen).
> Hat die Matrix noch eine Struktur (Bandmatrizen?)?
Danke für das gute Stichwort. Wahrscheinlich kann man die Variablen so umsortieren, dass ein 2n breites Band um die Diagonale entsteht, dann kann man den unteren rechten unabhängig vom oberen linken Teil lösen (evtl. sogar parallel) und dürfte in einem Bruchteil der Zeit fertig sein.
Da mach ich mich mal klüger. Danke nochmal.
|
|
|
|
