4. Matrixgleichung kleinste Lösung

Matrixgleichung kleinste Lösung

  • C

    Hallo 🙂

    Einleitung (Nicht umbedingt erforderlich für deine Antwort 🙂 )
    ich schreibe gerade eine Forschungsarbeit, und ein Teil meines Algorithmuses berechnet aktuell ~5.2 Millionen Schnittpunkte. Um das zu optimieren möchte ich so viele Berechnungen wie möglich streichen. Wie genau und worum es eigentlich geht beantworte ich gerne auf Wunsch, ist an sich nur relevant für eure Neugier 🙂
    Meine Frage ist eigentlich relativ simpel, ich suche jedoch nach der schnellsten Lösung für das Problem.

    Die Aufgabe:
    Ax=B
    A ist eine 3x3 Matrix mit float Zahlen.
    x ist ein ganzahliger Vektor dessen Elemente maximal Zahlen von -10 bis 10 annehmen können.
    B ist ein Vektor der minimiert wird.

    (Für Interesse: A beinhaltet 3 3D Punkte, x ist ein MillerIndex Vektor, und B ist dann der Schnittpunkt der 3 Geraden)

    Problem:
    x so wählen das B = min.
    x != 0

    Weitere Information für Interesse:
    x ist eigentlich X und damit eine Matrix aller Kombinationen. also -10 bis +10 = 21 Einträge pro Element = 21*21*21 = 9261 Kombinationen.
    X ist 3x9261. Da 9261 Schnittpunkte zwischen geraden Zustande kommen.
    Diese Schnittpunkte sind aber größtenteils völlig unnötig. gebraucht werden nur Schnittpunkte die im Raum [-5 < x, y, z < 5] liegen.
    Reichen würde mir schon ein X das 3x2 groß wäre und die zwei kleinsten (von 0 ungleichen) Lösungen beinhaltet.

    Gruß
    Chris

    0
  • G

    Zur Einordnung:

    Jenseits der Einschränkung des Wertebereichs der Einträge von x auf -10 bis 10 hört sich das nach dem Shortest Vector Problem an:

    https://en.wikipedia.org/wiki/Lattice_problem#Shortest_vector_problem_.28SVP.29

    Hast Du unter dem Stichwort schon ein bisschen gesucht, ob es für Deinen speziellen Fall gute Ansätze gibt?

    Brauchst Du die exakte Lösung oder reicht eine approximative Lösung?

    Gibt es Einschränkungen bezüglich A?

    0
  • C

    Ich bin bei meiner Recherche auf den LLL Algo gestoßen.
    Der LLL Latice Basis Reduction Algorithm löst das Problem ziemlich gut, benötigt aber auch zeit dafür.
    Meistens wird die Minimale Basis wohl irgendwo um -2 bis +2 in allen Dimensionen liegen, aber das ist eben nur ein "meistens". um es sicher zu machen muss ich wohl wirklich den LLL komplett implementieren 😞

    Die Lösung kann sogar super schwammig sein, da ich am ende ja ganzzahlig auf die Miller Indizes runden kann. Sie müsste also nur eine Genauigkeit um 0.5 haben.
    Matrix A wird vermutlich immer den R3 aufspannen, es ist unter umständen aber auch möglich das es nur einen R2 oder einen R1 aufspannt. Wenn die Punkte eben gemeinsam auf einer Geraden oder Ebene liegen. Das sollte allerdings nie der Fall sein, da die Punkte auf einer Sphäre liegen und nur durch Noise in solche positionen rutschen könnten.

    Aktuell implementiere ich den Latice Basis Reduction Algorithm neu, da ich keine vorkompilierten Libs benutzen kann.
    Ich bin aber zuverzichtlich das die Rechenkosten des LLL Algos unter denen liegen werden die 3Mio Punkte zu berechnen. Theorethisch darf ich jeden der 42.000 gebrauchten Punkte 70 mal so aufwändig rechnen und würde dennoch einen Zeitgewinn haben.

    Also vermutlich gibt es keine andere super tolle Lösung...

    0
  • G

    Dir ist bewusst, dass der LLL Algorithmus nur eine Naeherungsloesung liefert, oder?

    0
  • ?

    Ich denke auch, dass LLL dir hier nicht weiterhilft, weil die Ausgaben von diesem Algorithmus tatsächlich ziemlich schlechte Näherungen sind, d.h. ziemlich nahe am theoretischen Worst-Case.

    Ich habe nicht ganz nachvollziehen können, wie du das mit der Matrix X meinst. Aber wenn wir uns nur min Ax anschauen (ich nehme mal an, bzgl. der euklidischen Norm?) und zwei der drei x-Komponenten bereits festgelegt haben, dann ist das Finden der optimalen dritten x-Komponente lediglich das Minimieren einer quadratischen Funktion. Das bedeutet, dass du nicht 21*21*21 = 9261 Kombinationen durchprobieren musst, sondern nur 21*21 = 441 Kombinationen und für jede dieser Kombinationen eine quadratische Funktion minimieren. Wenn du die L_1- oder die L_\infty-Norm minimieren willst, wird es sogar noch einfacher.

    0
  • C

    Eine Näherungslösung ist exakt das was ich suche.
    Der Punkt ist folgender:

    Ich berechne einmal eine Nährungslösung und schließe Tausende Punkte aus,
    als einfach jedes mal 9261 Schnittpunkte von Ebenen Auszurechnen.

    Jetzt mal etwas ausführlicher:

    N ist die Matrix aus Nodes mit jeder menge Noise!
    Ein Node ist ein Punkt im R3.
    Ich muss jeweils Jeden Punkt mit jedem Punkt Untersuchen.
    Ich habe also (Anzahl ncr 3) Kombinationen. Also z.b. 16 Nodes machen 560 Kombinationen für N. (16 ncr 3 = 560)

    Also habe ich 560 verschiedene 3x3 N-Matrizen.

    Diese 560 Matrizen mit den 3x3 Nodes entsprechen irgendwelchen Ebenen im R3. Alles was ich weiß ist, dass sie ein Gitter Formen welches ich durch ganzhalige MillerIndizes ausdrücken kann. Da ich aber keine Ahnung habe welcher Index der richtige ist muss ich quasi alle berechnen. Und das sind die 21x21x21 Miller indizes. Diese Millionnen Schnittpunkte die ich dann habe, jage ich durch meinen ClusterAlgorithmus und suche Häufungen mit besonders hoher Dichte.

    Der Punkt ist das ich Milionen von Schnittpounkten außerhalb des Raumes -5 < x,y,z < 5 liegen und somit unnötig berechnet werden.

    lll schrieb:

    Ich denke auch, dass LLL dir hier nicht weiterhilft, weil die Ausgaben von diesem Algorithmus tatsächlich ziemlich schlechte Näherungen sind, d.h. ziemlich nahe am theoretischen Worst-Case.

    Ich habe nicht ganz nachvollziehen können, wie du das mit der Matrix X meinst. Aber wenn wir uns nur min Ax anschauen (ich nehme mal an, bzgl. der euklidischen Norm?) und zwei der drei x-Komponenten bereits festgelegt haben, dann ist das Finden der optimalen dritten x-Komponente lediglich das Minimieren einer quadratischen Funktion. Das bedeutet, dass du nicht 21*21*21 = 9261 Kombinationen durchprobieren musst, sondern nur 21*21 = 441 Kombinationen und für jede dieser Kombinationen eine quadratische Funktion minimieren. Wenn du die L_1- oder die L_\infty-Norm minimieren willst, wird es sogar noch einfacher.

    Leider nein. im 2D gibt es 21x21 Miller Indizes. im 3D 21x21x21. Das hat nichts mit X zu tun, es ergibt sich aus der Formel:

    (N^-1) * M'=B

    N sind die Nodes, invers.
    M sind die MillerIndizes. (M ist 3x9261)
    Also quasi:
    -10 -10 -10
    -10 -10 -10 ...
    -09 -08 -07

    B ist dann die Matrix der Schnittpunkte.
    Da ich 560 Ns habe habe ich 5.185.600 Schnittpunkte.

    0
Anmelden zum Antworten