Bandbreitenoptimierung für Matrizen

[Bjoerk]

Am besten, ich mach ein Beispiel. Das Beispiel verwendet 5 Knoten und 4 Stäbe. Ein Knoten hat hier 3 Freiheitsgrade, eine Verschiebung in X-Richtung, eine Verschiebung in Y-Richtung und eine Verdrehung in Z-Richtung (Verdrehung um die Z-Achse). Man gibt die Koordinaten der Knoten vor und man gibt Stäbe an.

Ein Stab hat einen linken und einen rechten Anschlußknoten (FElements.Item[I].Left, FElements.Item[I].Right). Hier Stab 1 von Knoten 1 nach Knoten 2, Stab 2 geht von Knoten 2 nach Knoten 5, Stab 3 von Knoten 5 nach Knoten 3 und Stab 4 von Knoten 3 nach Knoten 4.

Dann gibt man an, welche Freiheitsgrade an Knoten ausgeschlossen werden (Auflager). Im Beispiel sind an den Knoten 1, 4 und 5 die Verschiebungen in Y-Richtung ausgeschlossen, am Knoten 5 zusätzlich die Verschiebung in X-Richtung.

Mit diesen Angaben kann man eine Indexliste aufbauen und damit eine Systemsteifigkeitsmatrix aufstellen. Die Indexliste gibt an, daß z.B. die Reihe/Spalte 2 der Matrix nach Reihe/Spalte 15 zu verschieben ist (IndexOfRow, IndexOfCol). Die Matrix ist symmetrisch und hat eine Bandstruktur. Wie groß die Bandbreite ist kann man berechnen.

Delphi-Quellcode:

procedure TFrame.SimulateLoad(const T1, T2: integer);
var
  k1, k2, i1, i2, Row, Col: integer;
begin
  i1 := FDG * (T1 - 1);
  i2 := FDG * (T2 - 1);
  for k1 := 1 to FDG do
  begin
    Row := FIndexOfU[i1 + k1];
    if Row <= FNU then
      for k2 := 1 to FDG do
      begin
        Col := FIndexOfU[i2 + k2];
        if (Col >= Row) and (Col <= FNU) then
          FNB := Max(FNB, Col - Row + 1);
      end;
  end;
end;

procedure TFrame.CalcNB; // Bandbreite;
var
  I: integer;
begin
  FNB := 0;
  for I := 1 to FElements.Count do
  begin
    SimulateLoad(FElements.Item[I].Left, FElements.Item[I].Left);
    SimulateLoad(FElements.Item[I].Right, FElements.Item[I].Right);
    SimulateLoad(FElements.Item[I].Left, FElements.Item[I].Right);
    SimulateLoad(FElements.Item[I].Right, FElements.Item[I].Left);
  end;
end;

Um die Bandbreite zu optimieren, benennt man die Knoten lediglich anders. Lisa heißt jetzt Petra und Petra Lisa. Damit ergibt sich eine andere Indexliste und eine andere Bandbreite. Man tauscht z.B. die Namen der Knoten von 1 und 5. Damit geht Stab 1 nicht mehr von Knoten 1 nach Knoten 2 sondern von Knoten 5 nach Knoten 2. Mit dieser Knotenbenennung durchläuft man den Algo nochmals. Gesucht ist die Knotenbenennung, die die kleinste Bandbreite ergibt.

[BUG]

Wenn ich das richtig verstanden habe, ist das Aufbauen der Indexliste (=> Permutation) quasi das Sortieren der Elemente/Knoten so dass die Bandbreite minimal wird?

[Bjoerk]

Ja, nur daß es mal leicht 1000 Knoten sein können. Deshalb scheidet Permutation eigentlich aus.

[BUG]

Zitat von Bjoerk:

Deshalb scheidet Permutation eigentlich aus.

Deswegen habe ich ja Branch and Bound vorgeschlagen, wobei hoffentlich viele Zweige schon für kürzere Listen verworfen werden.
Kann natürlich sein, dass das immer noch zu viel ist; das kommt auch auf die erste Schranke an.

EDIT: Hui, ich hab mal nach matrix bandwidth minimization gesucht und da gibt es einiges an Material. Einmal tatsächlich Branch&Bound-Verfahren, aber auch vieles anderes. Lies einfach ein paar der Paper durch, da wirst du schon einen passenden Ansatz finden

EDIT2: Der Cuthill-McKee-Algorithmus scheint gut implementierbar zu sein, ansonsten sieht das ganz interessant aus.

[Bjoerk]

Ja, der letzte Link sieht gut aus. Vielen Dank Robert. Ich denke was man auf jeden Fall sagen kann, daß die Bandbreite proportional dem max. Knotenabstand ist. Mir fällt halt keine "SortByKnotenabstand" ein und einen Baum wollte ich vermeiden (weil ich da keine Plan von hab. )

@Bcvs, bei Stabwerken geht das gerade noch so. Würde das dann aber auch bei meinen FE (Platten/Scheiben) einbauen.

@All, ich hab ALLE Posts gelesen und freue mich über das Interssse. Hab ja deshlab auch das Beispiel angehängt.

[Bjoerk]

Kannst du mir sagen was der Autor hier macht? Und wie ich das ggf. auf mein Problem übertragen kann? Nur falls du Zeit und Lust hast.. In FormCreate ist übrigens Decimalseparator := '.' zu ergänzen.

[BUG]

Auf den ersten Blick: Das Programm testet verschiedene Verfahren zur Bandbreitenreduktion

Zu Cuthill-McKee: Jede symmetrische Matrix entspricht einem Graph, wobei jede Zeile/Spalte einem Knoten entspricht und jeder nicht-null Eintrag einer Kante. Dieser Graph wird in einer günstigeren Datenstruktur gespeichert (Knoten mit Nachbarschaftsliste) um nicht ständig in der Matrix suchen zu müssen. Gerade bei nicht dicht besetzten Matrizen ist das sehr viel günstiger. Dann werden die Knoten des Graphen des Graphen nach Cuthill-McKee sortiert. Diese Sortierung entspricht dann einer Permutation der Matrix, die dann "angewendet" wird.

Zu dem anderen Verfahren kann ich nichts sagen. Sieht auf den ersten Blick aus wie jeder anderer evolutionäre Algorithmus.

EDIT: Hast du den begleiteten Blogpost gelesen?

[Bjoerk]

Ja, hatte ich gelesen. Ich hab aber leider keine Ahnung von solchen Grafen, sprich, wie man die Matrix für den Cuthill-McKee-Algorithmus erstellen muß? Wenn du magst, kannst das anhand des Beispiels von Post # 9 kurz erläutern? Der Input soll rein aus den Linken und Rechten Knotenzuordnungen der Stäbe erfolgen. Das Beispiel verwendet 5 Knoten und 4 Stäbe.

Stab 1: von Knoten 1 nach Knoten 2
Stab 2: von Knoten 2 nach Knoten 5
Stab 3: von Knoten 5 nach Knoten 3
Stab 4: von Knoten 3 nach Knoten 4

Die Löung sollte dann z.B. so aussehen:

Stab 1: von Knoten 1 nach Knoten 2
Stab 2: von Knoten 2 nach Knoten 3
Stab 3: von Knoten 3 nach Knoten 4
Stab 4: von Knoten 4 nach Knoten 5

[BUG]

Zitat von Bjoerk:

Stab 1: von Knoten 1 nach Knoten 2
Stab 2: von Knoten 2 nach Knoten 5
Stab 3: von Knoten 5 nach Knoten 3
Stab 4: von Knoten 3 nach Knoten 4

Ich hab noch mal darüber nachgedacht. Im Prinzip hast du hier ja schon einen Graphen. Die Stäbe sind die Kanten und die Knoten sind ... die Knoten.

Wenn ich dich richtig verstehe, erstellst du daraus die folgende Matrix:

Code:

 | 1 2 3 4 5
------------
1| - 1 0 0 0
2| 1 - 0 0 1
3| 0 0 - 1 1
4| 0 0 1 - 0
5| 0 1 1 0 -

Das ist dann auch schon die Verbindung zwischen symmetrischen Matrizen und ungerichteten Graphen. Wenn das so stimmt, kannst du deinen Graphen direkt für die Cuthill-McKee-Algorithmus benutzen.
Der Algorithmus in der Zip-Datei benutzt eine Adjazenzliste zur Speicherung des Graphen und den schnellen Zugriff; so eine ähnliche Datenstruktur hast du bestimmt schon irgendwo herumzuliegen.

[Bjoerk]

Dann wär es ja doch nicht so schwer, also nur Dank deiner Ausführungen. Ich schau mir den Algo der zip näher an (kann etwas dauern) und teste ein paar Beispiele. Melde mich nochmal.