Seite 1 von 1

Hausübung 6 (HNF)

Verfasst: 21. Feb 2010 13:03
von Richie
Hi,

könnte jemand von euch kurz skizzieren, wie man auf die HNF kommt? Ich bin schon damals nicht drauf gekommen und auch jetzt rate ich nur mit unimodularen Transformationen rum und komme auf nix gescheites. Hat irgendjemand Tipps?

Danke!

Re: Hausübung 6 (HNF)

Verfasst: 21. Feb 2010 20:38
von \Hannes
Es gibt da im Netz so diverse relativ (post-quantum-, hahaha) kryptische Anleitungen. Ich bin eigentlich gut damit gefahren, die Matrix auf obere Dreiecksgestalt zu bringen und dabei panisch aufzupassen, dass die Diagonalelemente schön groß sind. Dann auf den Teil oberhalb der Diagonalen konzentrieren und den Rest wegaddiern.

Re: Hausübung 6 (HNF)

Verfasst: 22. Feb 2010 10:20
von marlic
Ich fands für den Beweis der eindeutigkeit auch ziemlich hilfreich, sich die allgemeine Methode, auf die HNF zu kommen, anzuschauen.

Re: Hausübung 6 (HNF)

Verfasst: 22. Feb 2010 13:30
von Richie
Danke auf jeden Fall schonmal.
Ich habe ja auch gesucht, aber ich habe da keinen Algorithmus zu gefunden (außer: "mach Gauß mit unimodularen Transformationen").
Hat da jemand evtl. einen Link?

Re: Hausübung 6 (HNF)

Verfasst: 23. Feb 2010 17:54
von marlic
Also ich habs heute nochmal probiert und bin auf folgenden Algorithmus gekommen:

Teil 1. Auf obere Dreiecksgestalt bringen:
Dazu jeweils - wie im euklidischen Algorithmus - das kleinste Element der Zeile von den anderen abziehen, sodass sie gerade noch positiv bleiben. Dass eben so lange machen, bis nur noch ein Eintrag in der Zeile >0 ist, den dann ganz nach rechts tauschen. Sollte einer der Einträge mal < 0 sein, einfach die Spalte mal -1 nehmen. Generell sind die hier genannten Operationen Spaltenoperationen.

Teil 2. HNF sicherstellen:
Wieder von unten nach oben vorgehen, alle Einträge rechts der Diagonalen modulo der Diagonale reduzieren, also sooft die Spalte mit der diagonalen abziehen / addieren, dass der jeweilige Eintrag kleiner dem Diagonaleintrag und nichtnegativ ist. Auch hier sind die Operationen als Spaltenoperationen zu verstehen.

Ich hoffe es hilft euch noch ;)

Michi

Re: Hausübung 6 (HNF)

Verfasst: 23. Feb 2010 18:36
von C0RNi666
Find ich gut, dass du deine Idee gepostet hast ;)

Re: Hausübung 6 (HNF)

Verfasst: 23. Feb 2010 19:03
von Richie
Schonmal super vielen Dank auch dafür, bin aber noch etwas verwirrt :)
marlic hat geschrieben:Also ich habs heute nochmal probiert und bin auf folgenden Algorithmus gekommen:
Teil 1. Auf obere Dreiecksgestalt bringen:
Dazu jeweils - wie im euklidischen Algorithmus - das kleinste Element der Zeile von den anderen abziehen, sodass sie gerade noch positiv bleiben. Dass eben so lange machen, bis nur noch ein Eintrag in der Zeile >0 ist, den dann ganz nach rechts tauschen. Sollte einer der Einträge mal < 0 sein, einfach die Spalte mal -1 nehmen. Generell sind die hier genannten Operationen Spaltenoperationen.
Was genau meinst du mit "kleinstes Element"? Also wahrscheinlich 'ne Zahl, aber ich kann ja nur Zeilen von Zeilen oder Spalten von Spalten abziehen, oder? Also kann ich mir doch mit einer Zeile 'ne andere kaputt machen?
Meinst du den Gauß statt den euklidischen Algorithmus? Wenn nicht, weiß ich nicht, welchen Algorithmus du meinst :)
Teil 2. HNF sicherstellen:
Wieder von unten nach oben vorgehen, alle Einträge rechts der Diagonalen modulo der Diagonale reduzieren, also sooft die Spalte mit der diagonalen abziehen / addieren, dass der jeweilige Eintrag kleiner dem Diagonaleintrag und nichtnegativ ist. Auch hier sind die Operationen als Spaltenoperationen zu verstehen.

Re: Hausübung 6 (HNF)

Verfasst: 24. Feb 2010 07:18
von marlic
"Generell sind die hier genannten Operationen Spaltenoperationen." Damit meine ich, dass man jedes "<Prädikat> Element in der aktuellen Zeile" im Text durch "Spalte, die das <Prädikat> Element in der aktuellen Zeile enthält" ersetzen muss.