Indizieren einer oberen Dreiecksmatrix

[Senior Sanchez]

Hallo,

Ich habe gerade folgendes Problem: Ich habe eine zweidimensionale Matrix, in der jede Dimension eine Größe von 300 hat; es gibt in der gesamten Matrix also 90.000 Elemente. Mich interessiert aber nur die obere Dreiecksmatrix inklusive der Diagonalen von oben links nach unten rechts.

Ich habe nun einen linearen, eindimensionalen Index. Den möchte ich auf diese Dreiecksmatrix abbilden, sodass ich zu jedem linearen Index eine Spalte und Zeile in der Matrix erhalte. Wie der Index durch die Matrix gelegt wird, ist mir eigentlich egal. Ich möchte eben bloß zu diesem eindimensionalen Index wissen, in welcher Spalte und Zeile die betreffende Zelle ist.

Beispiel: Matrix mit Dimensionsgröße von 5:


1 2 3 4 5
6 7 8 9
10 11 12
13 14
15


Kennt irgendjemand einen Algorithmus um das effizient zu berechnen? Nach Möglichkeit möchte ich es auch vermeiden, das mit Hilfe eines Arrays abzubilden.

[Senior Sanchez]

Ich glaube, ich habe eine Lösung für das Problem gefunden! Das teste ich mal kurz aus.

[labecula]

Der wäre?

[Senior Sanchez]

Die Zeile kann ich herausbekommen mittels Interpolation. ;) Mittels Excel kann man nämlich eine sehr gut passende Interpolationsfunktion finden, die die Diagonale abbildet. Wenn man die kennt, sollte sich die zugehörige Spalte leicht bestimmen lassen.

[pest]

also die einfachste Lösung ist jeweils einfach eine Schleife :confused:

die Algebraische ist etwas komplizierter

[Senior Sanchez]

also die einfachste Lösung ist jeweils einfach eine Schleife :confused:

die Algebraische ist etwas komplizierter

Die einfachste Lösung ist wirklich eine Schleife, aber sie ist einfach ziemlich inperformant, wenn ich eben teilweise bis 50.000 oder so iterieren muss. Mit Hilfe eines Baumes kann man das sicherlich schneller lösen, aber dann habe ich wieder das Speicherproblem.

Ich probiere das heute mal mit der Interpolation. Das mach ich erstmal hartkodiert, weil ich die Dimensionsgröße der Matrix konstant halte. In Zukunft kann das variabel sein, aber den Fall will ich der Einfachheit halber erstmal nicht betrachten.

Vielleicht zum Hintergrund: Ich will ein Programm für GPGPU schreiben, wobei ich per Brute-Force alle sinnvollen Kombinationen einer diskreten, zwei-argumentigen Funktion ausprobieren will, um das Optimum zu finden. Und dazu brauche ich eine Möglichkeit, den Threadindex auf die Kombination der zwei Argumente abzubilden.

[Monger]

Mal rein interessehalber: was verwendest du denn als GPGPU Framework? CUDA?

[pest]

Die einfachste Lösung ist wirklich eine Schleife, aber sie ist einfach ziemlich inperformant, wenn ich eben teilweise bis 50.000 oder so iterieren muss.


in jeder schleifeniteration zählst du doch über die spaltenanzahl
d.h. die anzahl der iterationen ist von oben durch die zeilenanzahl begrenzt

soll ich es in einem 3-zeiler hinschreiben :confused:


Ich probiere das heute mal mit der Interpolation. Das mach ich erstmal hartkodiert, weil ich die Dimensionsgröße der Matrix konstant halte. In Zukunft kann das variabel sein, aber den Fall will ich der Einfachheit halber erstmal nicht betrachten.
Mit Hilfe eines Baumes kann man das sicherlich schneller lösen, aber dann habe ich wieder das Speicherproblem.


wenn du den pythagoras kennengelernt hast, sollte die erarbeitung einer algebraischen lösung kein problem sein.


Vielleicht zum Hintergrund: Ich will ein Programm für GPGPU schreiben, wobei ich per Brute-Force alle sinnvollen Kombinationen einer diskreten, zwei-argumentigen Funktion ausprobieren will, um das Optimum zu finden. Und dazu brauche ich eine Möglichkeit, den Threadindex auf die Kombination der zwei Argumente abzubilden.

und du machst dir sorgen, dass 900 inkrement-operationen das programm verlangsamen?
am anfang kannst du ja mal einen branch-and-bound algorithmus schreiben Branch-and-Bound (http://de.wikipedia.org/wiki/Branch-and-Bound)

ich kenne mich in optimierung übrigens ganz gut aus, das mache ich in meiner doktorarbeit :freak:

[Senior Sanchez]

Mal rein interessehalber: was verwendest du denn als GPGPU Framework? CUDA?

Aparapi

in jeder schleifeniteration zählst du doch über die spaltenanzahl
d.h. die anzahl der iterationen ist von oben durch die zeilenanzahl begrenzt

soll ich es in einem 3-zeiler hinschreiben :confused:

wenn du den pythagoras kennengelernt hast, sollte die erarbeitung einer algebraischen lösung kein problem sein.

und du machst dir sorgen, dass 900 inkrement-operationen das programm verlangsamen?
am anfang kannst du ja mal einen branch-and-bound algorithmus schreiben Branch-and-Bound (http://de.wikipedia.org/wiki/Branch-and-Bound)

ich kenne mich in optimierung übrigens ganz gut aus, das mache ich in meiner doktorarbeit :freak:

Das die Schleife kurz ist, weiß ich selber. Aus GPU-Sicht ist die aber Mist, da sie keine konstante Länge hat.

Dann nenne mir doch die algebraische Lösung, dann brauch ich mir diese Probleme nicht machen. :)

Es ist nicht Sinn und Zweck der Übung jetzt einen komplexen Optimierungsalgorithmus aufzustellen. Mir geht es um die Anwendung im GPGPU-Bereich. Da ich es noch nicht getestet habe, weiß ich auch nicht, über welchen Zeitaufwand wir hier sprechen. Ich frage mich aber gerade, wie du auf 900 Inkrement-Operationen kommst.

[pest]

Das die Schleife kurz ist, weiß ich selber. Aus GPU-Sicht ist die aber Mist, da sie keine konstante Länge hat.
Ich frage mich aber gerade, wie du auf 900 Inkrement-Operationen kommst.


konstante Länge?
Ich habe mich verlesen, dachte an max 900 Zeilen..., naja hier ist ein bissl Code


void rowcol_diag(int index,int numcols,int &row,int &col)
{
row=0;
while (index>=numcols) {row++;index-=numcols--;};
col=row+index;
}



Dann nenne mir doch die algebraische Lösung, dann brauch ich mir diese Probleme nicht machen. :)


Grafischer-TR Generation? Selber denken macht schlau


Es ist nicht Sinn und Zweck der Übung jetzt einen komplexen Optimierungsalgorithmus aufzustellen.


Lieber 30min nachdenken anstatt sinnlos Quatsch machen. Mein derzeitiger favorisierter Algorithmus zum kalibrieren von BlackBox-Problemen ist 20 Zeilen lang.


Mir geht es um die Anwendung im GPGPU-Bereich. Da ich es noch nicht getestet habe, weiß ich auch nicht, über welchen Zeitaufwand wir hier sprechen.

Ich würde dann eher etwas Sinnvolles implementieren und nicht GPGPU dazu benutzen die eigene Unfähigkeit zu demonstrieren über ein Problem tiefer nachzudenken.

Wie wäre es daher mit einem Problem aus der Kombinatorik (Graphentheorie), z.b. die Ramsey-Zahlen (http://de.wikipedia.org/wiki/Satz_von_Ramsey) für 2 Farben

[Senior Sanchez]

pest, findest du dein Auftreten nicht etwas überheblich?

Ich suche mir außerdem Probleme nicht zum Spaß aus, sondern sie sind relevant für mich. Dieses Problem soll als kleiner Einstieg dienen. Außerdem, ob das 10 oder 20 Zeilen hat, ist mir reichlich egal. Es geht mir um Geschwindigkeit.

[pest]

wenn das Problem relevant ist, solltest du erst Recht von vornherein das Ganze durchdenken, alles ist besser als jede Möglichkeit durchzuprobieren

ein einfacher genetischer Algorithmus lässt sich wunderbar auf ein ganzzahliges Problem anwenden und im Rahmen der Populationsgröße parallelisieren


pest, findest du dein Auftreten nicht etwas überheblich?


Überheblichkeit liegt im Auge des Betrachters


Dann nenne mir doch die algebraische Lösung, dann brauch ich mir diese Probleme nicht machen.

[Senior Sanchez]

wenn das Problem relevant ist, solltest du erst Recht von vornherein das Ganze durchdenken, alles ist besser als jede Möglichkeit durchzuprobieren

ein einfacher genetischer Algorithmus lässt sich wunderbar auf ein ganzzahliges Problem anwenden und im Rahmen der Populationsgröße parallelisieren

Wie gesagt, ich probiere meine Variante mal aus. Und dann schaue ich mal, was sich zum Beispiel mit einem genetischen Algorithmus rausholen lässt. Ich glaube der Vergleich ist interessant. :)

[AnPapaSeiBua]

Hi,

das kannst du über die Invertierung der Gaußschen Summenformel machen.

Um es zu vereinfachen, würde ich die Indizierung so ändern:

0 1 3 6
2 4 7
5 8
9


Damit ist das unabhängig von der Matrix-Größe.

n = Index
s = Spalte
z = Zeile

Alle beginnend mit 0.

Dann geht das so:
s = floor((sqrt(8*n+1)-1)/2)
z = n - (s*s + s) / 2

[Senior Sanchez]

Cool danke!
Das scheint wirklich zu klappen.

Ich bin jetzt aber etwas umgeschwenkt und verfolge eine Kombination aus dem GPU-Ansatz und dem genetischen Algorithmus. Das funktioniert recht gut.