Seite 2 von 3

Re: Segment-LLL Verständnisfragen

Verfasst: 11. Jun 2008 08:00
von rueckert
Cyrtox hat geschrieben:Haben nun die Aktualisierung der µ-Werte mit aufgenommen und es hat nichts verändert. Es war so, wie ichs mir bereits gedacht hatte, jeder µ-Wert wird innerhalb eines Reduce-Aufrufs nur einmal verwendet und vor einem erneuten Reduce-Aufruf wird ohnehin ComputeGS erneut aufgerufen. Schade... es sah so sehr nach dem Fehler aus.
Ich hatte hier ebenfalls euren Fehler vermutet. Schaut euch aber trotzdem die µ Werte nach der LRed Methode an und 1. vergleicht sie mit denen aus computeGS, 2. testet ob | µ_i,j | <= 1/2.

Re: Segment-LLL Verständnisfragen

Verfasst: 11. Jun 2008 12:50
von Cyrtox
Wenn wir immer den nächsten ganzzahligen Wert abziehen müssen sie ja < 1/2 sein. Es spielt aber wie gesagt ohnehin keine Rolle, da die Werte nur einmal benutzt werden. ComputeGS wird beim nächsten Berechnungsschritt ebenfalls etwas anderes ergeben, da ein LLL-Schritt dazwischen liegt.

Re: Segment-LLL Verständnisfragen

Verfasst: 11. Jun 2008 14:53
von Cyrtox
Ach ja nochmal kurz ne andere Frage:
Wieso können bei ComputeGS in dem Ergebnisvektor c manchmal negative Werte enthalten sein!? Dachte das seien die Längenquadrate -> immer positiv!
Ach und zu der Längenreduktion... haben nun mal getestet:
- Längenreduktion über die komplette Matrix
- Längenreduktion nur über die 2 Segmente
- Längenreduktion über die 2 Segmente, aber Einberechnung der Werte ausserhalb der Segmente (also der µ Werte die eigentlich nicht mehr im Segment liegen)
Leider alles ohne Erfolg... sieht immer ähnlich aus.

Re: Segment-LLL Verständnisfragen

Verfasst: 11. Jun 2008 15:45
von rueckert
Cyrtox hat geschrieben:Wenn wir immer den nächsten ganzzahligen Wert abziehen müssen sie ja < 1/2 sein.
Sind sie es nach eurem Algorithmus?

Re: Segment-LLL Verständnisfragen

Verfasst: 11. Jun 2008 15:48
von Cyrtox
Ja. Wie gesagt wir ziehen ja nun immer den nächsten ganzzahligen Wert ab. Aber es hat keinen Effekt, da wir die µ Werte nicht weiter verwenden.
Noch eine Frage... haben eben mal zum test nach dem Längenreduzieren ComputeGS aufgerufen auf die veränderte B Matrix. In dem Fall kommen nicht die gleichen µ Werte heraus wie bei dem manuellen Updaten durch das abziehen des nächsten ganzzahligen Wertes. Müssten bei ComputeGS nicht die selben Werte herauskommen? Beim Aufruf von ComputeGS kommen eben nicht überall Werte < 0.5 heraus.

Re: Segment-LLL Verständnisfragen

Verfasst: 12. Jun 2008 14:50
von rueckert
Wenn ihr für diese Diskrepanz keine vernünftige Erklärung findet, scheint euer LRed Algorithmus falsch zu sein. Kontrolliert bitte die Schritte manuell bei einem kleinen, nicht-trivialen Beispiel.

Re: Segment-LLL Verständnisfragen

Verfasst: 12. Jun 2008 16:05
von Cyrtox
Nochmal die Frage: Längenreduktion wie genau? Nur die 2 Segmente, aber die µ Werte bis zum "0ten" Element beachten? Oder nur die 2 Segmente und nur die µ Werte bis zum 1. Element des Segments beachten? Oder doch nicht nur beide Segmente sondern die ganze Matrix durchlaufen?

Re: Segment-LLL Verständnisfragen

Verfasst: 12. Jun 2008 16:50
von rueckert
Cyrtox hat geschrieben:Nochmal die Frage: Längenreduktion wie genau? Nur die 2 Segmente, aber die µ Werte bis zum "0ten" Element beachten? Oder nur die 2 Segmente und nur die µ Werte bis zum 1. Element des Segments beachten? Oder doch nicht nur beide Segmente sondern die ganze Matrix durchlaufen?
Mein Verständnis davon ist 1.
Wenn es tatsächlich in keiner der Quellen explizit steht, schaut euch an, was bei 1.,2.,3. passiert. Ggf. seht ihr dann welche Definition von "global" ausreichend ist.

Re: Segment-LLL Verständnisfragen

Verfasst: 13. Jun 2008 15:24
von Cyrtox
Wie bereits gesagt es funktioniert ohnehin mit keiner Variante. :/
Ach ja, eine LLL reduzierte Basis müsste doch nach den Längen der Spalten (also bei uns im Code Zeilen) sortiert sein korrekt? Weil das ist es bei uns nie... wieder ein Fehler, den es zu finden gilt.

Re: Segment-LLL Verständnisfragen

Verfasst: 13. Jun 2008 16:27
von Cyrtox
Wir haben wohl nen Fehler gefunden... aber können ihn nicht so einfach beheben. Entweder wir haben grundlegend was falsch verstanden oder es wird so berechnet. Wäre nett, wenn ihr euch das genauer anschauen könntet. Wir haben alles mögliche probiert um den Fehler zu finden. Bisher hatten wir dabei den bestehenden LLL Algo als korrekt funktionierende Blackbox gesehen. Ansich funktioniert der Algo ja auch...
Naja wie auch immer, wir haben uns mal die Rl (also den Ausschnitt aus R, den wir in den LLL als Eingabe geben) ausgeben lassen und dann das Ergebnis, das LLL zurückgibt. Wir schreiben dieses Ergebnis ja anschließend in die R Matrix zurück! Das Problem ist nun scheinbar... der LLL gibt eine Matrix zurück, die nicht mehr obere (bzw untere im code) Dreiecksgestalt hat! Das kann eigentlich nicht korrekt sein? Oder doch? Oder soll man nach jedem lokalen LLL Schritt etwa global die neue R matrix erneut berechnen!? Mit einer neu berechneten globalen R Matrix stimmen die Ergebnisse allerdings auch nicht... aber das kann ja auch andere Gründe haben. Wäre jedenfalls toll zu wissen was wir nun machen müssen.
Ach ja... was mir auch noch aufgefallen ist. Laut der filipovic Diplomarbeit wird die lokale LLL reduktion nicht ind ganzen Zahlen berechnet... !?

Re: Segment-LLL Verständnisfragen

Verfasst: 16. Jun 2008 08:46
von rueckert
Cyrtox hat geschrieben: Naja wie auch immer, wir haben uns mal die Rl (also den Ausschnitt aus R, den wir in den LLL als Eingabe geben) ausgeben lassen und dann das Ergebnis, das LLL zurückgibt. Wir schreiben dieses Ergebnis ja anschließend in die R Matrix zurück! Das Problem ist nun scheinbar... der LLL gibt eine Matrix zurück, die nicht mehr obere (bzw untere im code) Dreiecksgestalt hat! Das kann eigentlich nicht korrekt sein? Oder doch? Oder soll man nach jedem lokalen LLL Schritt etwa global die neue R matrix erneut berechnen!? Mit einer neu berechneten globalen R Matrix stimmen die Ergebnisse allerdings auch nicht... aber das kann ja auch andere Gründe haben. Wäre jedenfalls toll zu wissen was wir nun machen müssen.
LLL muss keine Dreiecksmatrix zurückliefern. Im Prinzip muss die QR Zerlegung erneut berechnet werden. In Filipovic und Koys Arbeiten geschieht das mit einer lokalen Korrektur. Für uns ist diese Verbesserung aber zunächst egal.
Cyrtox hat geschrieben: Ach ja... was mir auch noch aufgefallen ist. Laut der filipovic Diplomarbeit wird die lokale LLL reduktion nicht ind ganzen Zahlen berechnet... !?
LLL_FP arbeitet intern mit Gleitkommaarithmetik. Das ist damit gemeint. Der ganzzahlige LLL Algorithmus wird in der Regel nicht verwendet.

Re: Segment-LLL Verständnisfragen

Verfasst: 16. Jun 2008 15:18
von Cyrtox
Ok wir benutzen nun LLL_FP (bzw QP, XD, je nach fpaType) für den internen LLL auf die Matrix Rl. Hat allerdings leider keinen Fortschritt gebracht.
Wir berechnen nun auch jedes mal nach dem LLL über Rl das gesamte R erneut. Seitdem springt er allerdings NIE mehr zurück! Das Ergebnis ist öfter "kleiner", aber immernoch nicht immer... und ich halte es für unwahrscheinlich, dass der Algo nie zurückspringen sollte?
Ach und nochmal die Frage zu der Sortierung. Ich dachte die Basis B und das Ergebnis unseres ganzen Algos müssten der Länge nach sortiert sein? Weil weder die Eingabematrix noch das Ergebnis sind sortiert? Habe auch einfach mal LLL_FP über die Eingabematrix B laufen lassen, da ist das Ergebnis ebenfalls nicht der Länge nacht sortiert. Hatte ich da was falsch im Kopf oder stimmt hier irgendetwas nicht?

Re: Segment-LLL Verständnisfragen

Verfasst: 16. Jun 2008 17:11
von Cyrtox
Oooookay... also wir haben nun sowohl die globale Größenreduktion (immer über ALLE Vektoren, alles reduzieren) und auch LLL_FP drin. Zudem berechnen wir nun jedes mal R neu nachdem LLL_FP einmal durchgelaufen ist. Die Ergebnisse sehen fast immer gut aus! (Orthogonaldefekt fast immer verkleinert, nur manchmal plötzlich größer, keine Ahnung wieso) Aber nun stehen wir vor einem ganz anderen Problem. Das Programm säuft regelmäßig ab und zwar, weil wir zur erneuten Berechnung von R ja die Daten aus ComputeGS nutzen müssen. Wir brauchen dazu die Wurzeln aus dem Inhalt des C-Vektors. Diese sind aber manchmal negativ!? Wie kann das sein? Dort sollen doch die Längenquadrate stehen, die MÜSSEN immer positiv sein! Wenn ich eine Abfrage auf Negativität einbaue und dann *-1 rechne funktioniert der Algo nicht mehr richtig und gibt seltsame Endergebnisse aus.

Edit: Habe mir mal unsere zu bearbeitende Matrix ausgeben lassen bevor er zur Neuberechnung von R kommt (vor ComputeGS). Der Fehler mit Wurzel aus negativer Zahl und Teilung durch 0 (in ComputeGS) kommt scheinbar immer dann, wenn der Algo anfängt zwischen zwei Segmenten hin und her zu springen. Also z.b. l=3, l=4, l=3, ... usw. Die Zahlen in diesen Segmenten werden dadurch immer größer (egal ob nun negativ oder positiv), bis der Fehler auftritt und das Programm terminiert. Wir haben bisher keine Idee wie das zustande kommen kann...

Re: Segment-LLL Verständnisfragen

Verfasst: 17. Jun 2008 11:16
von rueckert
Schick uns bitte die Gitterbasis deren GS Werte c negativ sind.

Re: Segment-LLL Verständnisfragen

Verfasst: 17. Jun 2008 13:30
von Cyrtox
Wie bereits im Edit geschrieben, es passiert nur, wenn er ohnehin in einer Endlosschleife zwischen 2 Segmenten festhängt und dadurch die Werte explodieren. Keine Ahnung wodurch das passiert. Nehme an, dass durch den Overflow die Zahl negativ wird. Manchmal hat er dann auch den Fehler, dass er in ComputeGS durch 0 teilen muss, aber unter den selben Umständen.
Die Hauptfragen, die wir uns derzeit stellen sind:
1. Wieso ist ergibt ComputeGS NACH dem globalen Größenreduztieren eine andere µ Matrix als das Größenreduzieren angepasst hat?
2. Wann die neue R Matrix berechnen? Nach LLL? Nach Größenreduktion? (Sprich mit welchen µ Werten?)
3. Woher kommt unsere Endlosschleife? Wie kann das Programm zwischen 2 Segmenten hin und her springen ohne zu einem Ende zu gelangen?
Wie bereits gesagt, wenn keine Endlosschleife auftritt ist das Ergebnis beinahe immer "besser" als die Ausgangsbasis (kleinerer Orthogonaldefekt, vorausgesetzt den habe ich richtig implementiert). Falls wir keine Lösung finden wäre es wohl am besten beim nächsten Treffen darauf einzugehen (falls mehr Zeit) oder wir kommen mal so vorbei.

Ein Beispiel für eine Basis bei der bei uns in l=2 angeblich ein negativer Wert in c auftaucht:
[[0 8 4 10 6 3 5 4 9 0]
[0 0 8 4 10 6 3 5 4 9]
[0 8 10 9 7 1 8 2 7 4]
[0 6 10 8 3 3 8 10 9 7]
[0 5 4 1 3 7 7 6 3 9]
[0 8 4 5 4 5 9 6 8 3]
[0 10 4 8 6 1 2 5 3 8]
[0 1 3 0 7 9 4 6 8 3]
[0 10 8 7 1 4 6 0 3 8]
[0 1 3 4 6 4 7 10 3 3]
]
Bei diesem Beispiel sind übrigens ausnahmsweise mal nicht die Zahlen explodiert vor dem Abbruch durch die Wurzelfunktion. Wir berechnen in diesem Beispiel µ NACH der Längenreduktion erneut durch ComputeGS, R bezieht sich allerdings auf die µ Matrix VOR der Längenreduktion. Daher kann in diesem Fall also auch der Fehler kommen. Sind halt gerade am rumprobieren.
Ach ja eine letzte Sache noch... wenn wir R NACH der Längenreduktion erneut berechnen, dann läuft das Programm bisher immer durch, ALLERDINGS geht er quasi niemals ein Segment zurück, daher halte ich die Lösung nicht für korrekt...