Indizes fuer Dreiecksmatrix

Gregor

Hi.

Ich habe eine Dreiecksmatrix folgender Art

[m_1,1                   ]
(m_i,j) = [m_1,2 m_2,2       ...   ]
          [m_1,3 m_2,3 m_3,3       ]
          [      ...               ]

Diese Dreiecksmatrix ist in einem eindimensionalen Array wie folgt gespeichert:

(M_k) = [m_1,1 m_1,2 m_2,2 m_1,3 m_2,3 m_3,3 ...]

Bei mir beginnen die Arrays mit dem ersten und nicht mit dem nullten Element, so dass zum Beispiel M_5 = m_2,3 gilt. Allgemein gilt:

k = j(j-1)/2 + i

Ich habe jetzt k gegeben und moechte daraus die Indizes i und j extrahieren. Wenn ich mir die Gleichung oben angucke, dann geht das auch ohne Probleme, die Rechnung ist aber auf den ersten Blick kompliziert. Ich wuerde erstmal j als groesste ganze Zahl bestimmen, fuer die gilt k > j(j-1)/2. Damit kann ich dann problemlos i bestimmen. Wenn ich das so mache, muss ich aber bei der Bestimmung von j eine quadratische Gleichung loesen und irgendwie kommt mir das unnoetig kompliziert vor. Gibt es eine schlaue und einfache und vor allem schnelle Methode, um aus einem k die Indizes i und j zu bestimmen?

cooky451

Ohne wirklich Ahnung von Matrizen zu haben (Schüler), und leider vermutlich auch ohne hilfreich zu sein, hätte ich mal eine Frage. Ist k nicht mehrdeutig?

k = 2 = m_1,2 = m_2,1

Edit:
Ok, ich hab mir die Matrix noch mal angeguckt, jetzt weiß ich auch warum "Dreiecksmatrix"

volkard

Ich nehme an, Du hast die selbe Formel.
j=sqrt(2*k-1.75)+.5) oder j=(sqrt(8*k-7)+1)/2
Ich halte es für ausgeschlossen, daß Du ums Radizieren kommst.

Gregor

volkard schrieb:

Ich halte es für ausgeschlossen, daß Du ums Radizieren kommst.

Hmmm... inzwischen bin ich davon auch überzeugt. Schade. Dann muss ich mir wohl mehr Gedanken machen und das Problem umgehen.

Trotzdem danke für die Antwort.

volkard

Gregor schrieb:

Ich habe jetzt k gegeben und moechte daraus die Indizes i und j extrahieren.

Komisch. Ich kann mir eigentlich nur vorstellen, daß man i und j hat und k braucht als Arrayindex.
Die ganzen Algos arbeiten doch mit i und j und kennen k gar nicht.
Allenfalls das Laden aus ner Datei wird k hochzählen, aber das zählt auch i und j hoch.

Michael E.

Wie groß ist die Matrix?

Gregor

volkard schrieb:

Gregor schrieb:

Ich habe jetzt k gegeben und moechte daraus die Indizes i und j extrahieren.

Komisch. Ich kann mir eigentlich nur vorstellen, daß man i und j hat und k braucht als Arrayindex.
Die ganzen Algos arbeiten doch mit i und j und kennen k gar nicht.
Allenfalls das Laden aus ner Datei wird k hochzählen, aber das zählt auch i und j hoch.

Naja, ich passe einen alten Algorithmus an meine Bedürfnisse an und es ist nicht direkt offensichtlich, welche i,j dieser Algorithmus nun direkt behandelt. Der arbeitet halt auf so einem 1D-Array, ich _vorerst_ auf einem 2D Array. Deshalb nutzt der einfach nur k, ich hingegen brauche i und j. Aber da muss ich dann halt mal in den sauren Apfel beißen und mir die Indizes anders herleiten. Hatte gehofft, das umgehen zu können.

Michael E. schrieb:

Wie groß ist die Matrix?

Von der Größenordnung her 10.000x10.000. Zumindest groß genug, dass ich nicht unbedingt eine Lookup-Table haben will.

Jockelx

Edit: Ach, nee, was hier stand half auch nicht wirklich.

*john 0

Gregor schrieb:

Hi.

Ich habe eine Dreiecksmatrix folgender Art

[m_1,1                   ]
(m_i,j) = [m_1,2 m_2,2       ...   ]
          [m_1,3 m_2,3 m_3,3       ]
          [      ...               ]

Mit Verlaub hier läuft etwas schief. Mathematisch korrekt sieht Deine Matrix anders aus. Der erste Index ist für die Spalte, der zweite für die Zeile.

[m_1,1 m_1,2 m_1,3 m_1,4 ]
(m_i,j) = [      m_2,2 m_2,3 m_2,4 ]
          [            m_3,3 m_3,4 ]
          [                  m_4,4 ]

Das ist somit eine obere Dreiecksmatrix.

Diese Dreiecksmatrix ist in einem eindimensionalen Array wie folgt gespeichert:
(M_k) = [m_1,1 m_1,2 m_2,2 m_1,3 m_2,3 m_3,3 ...]

Das ist Fortran colum major order in packed form. Man zählt hierbei immer erst die Elemente in den Spalten durch und erhöht danach den Spaltenindex. Als leading dimension wird die Größe einer Spalte benötigt, und diese wird in irgend einer Form auch abgespeichert, und mit der LDA läßt sich Dein Problem auch lösen.

Gregor

Also ich habe das Problem inzwischen umgangen, insofern ist es für mich inzwischen gelöst.

~john schrieb:

Mit Verlaub hier läuft etwas schief. Mathematisch korrekt sieht Deine Matrix anders aus. Der erste Index ist für die Spalte, der zweite für die Zeile.

Oh, dann habe ich die Indizes aus Versehen vertauscht. Aber letztendlich spielt es auch keine Rolle, ob es eine obere oder untere Dreiecksmatrix ist. Das ändert nicht wirklich etwas an der Problemstellung. Bei mir handelt es sich eigentlich sogar um eine symmetrische Matrix, aber um Rechenzeit zu sparen, wird praktisch nur so eine Dreiecksmatrix betrachtet. Ob es jetzt die obere oder untere ist, ist völlig egal: m_i,j = m_j,i.