Berechnung der Sparsity-Struktur für Finite-Elemente-Matrizen

13

Frage: Mit welchen Methoden kann die Sparsity-Struktur einer Finite-Elemente-Matrix genau und effizient berechnet werden?

Info: Ich arbeite an einem Poisson-Druckgleichungslöser nach der Methode von Galerkin auf quadratischer Lagrange-Basis, geschrieben in C, und verwende PETSc für die Speicherung von spärlicher Matrix und KSP-Routinen. Um PETSc effizient zu nutzen, muss der globalen Steifheitsmatrix Speicher zugewiesen werden.

Momentan mache ich eine Mock-Assembly, um die Anzahl der Nonzeros pro Zeile wie folgt zu schätzen (Pseudocode)

int nnz[global_dim]
for E=1 to NUM_ELTS
  for i=1 to 6
    gi = global index of i 
    if node gi is free
      for j=1 to 6
        gj = global index of j
        if node gj is free 
          nnz[i]++

Dies überschätzt jedoch nnz, da einige Knoten-Knoten-Interaktionen in mehreren Elementen auftreten können.

Ich habe überlegt, welche Interaktionen ich gefunden habe, aber ich bin mir nicht sicher, wie ich dies tun soll, ohne viel Speicherplatz zu verbrauchen. Ich könnte auch die Knoten durchlaufen und die Unterstützung der Basisfunktion finden, die auf diesen Knoten zentriert ist, aber dann müsste ich alle Elemente für jeden Knoten durchsuchen, was ineffizient zu sein scheint.

Ich fand diese kürzlich gestellte Frage, die einige nützliche Informationen enthielt, insbesondere von Stefano M., der schrieb

Mein Rat ist, es in Python oder C zu implementieren, einige graphentheoretische Konzepte anzuwenden, dh Elemente in der Matrix als Kanten in einem Graphen zu betrachten und die Sparsity-Struktur der Adjazenzmatrix zu berechnen. Eine Liste von Listen oder ein Wörterbuch von Schlüsseln sind häufige Auswahlmöglichkeiten.

Ich bin auf der Suche nach weiteren Details und Ressourcen. Zugegebenermaßen kenne ich nicht viel Graphentheorie und kenne nicht alle CS-Tricks, die nützlich sein könnten (ich gehe dies von der mathematischen Seite aus an).

Vielen Dank!

matrix finite-element petsc performance John Edwardson
quelle

5

Ihre Idee, zu verfolgen, welche Interaktionen Sie gefunden haben, kann funktionieren. Ich denke, das ist der "CS-Trick", auf den Sie und Stefano M sich beziehen. Dies bedeutet, dass Sie eine dünne Matrix im Listenformat erstellen .

Nicht sicher, wie viel CS Sie haben, also entschuldige ich mich, wenn Ihnen dies bereits bekannt ist: In einer verknüpften Listendatenstruktur speichert jeder Eintrag einen Zeiger auf den Eintrag danach und den Eintrag davor. Es ist billig, Einträge hinzuzufügen und zu löschen, aber nicht so einfach, darin Elemente zu finden - möglicherweise müssen Sie alle durchsuchen.

Sie speichern also für jeden Knoten i eine verknüpfte Liste. Dann durchlaufen Sie alle Elemente. Wenn Sie feststellen, dass zwei Knoten i und j verbunden sind, sehen Sie sich die verknüpfte Liste von i an. Wenn j noch nicht vorhanden ist, fügen Sie es der Liste hinzu und fügen i ebenfalls der Liste von j hinzu. Am einfachsten ist es, wenn Sie sie der Reihe nach hinzufügen.

Sobald Sie Ihre Liste mit Listen gefüllt haben, kennen Sie die Anzahl der Einträge ungleich Null in jeder Zeile der Matrix: Es ist die Länge der Liste dieses Knotens. Diese Informationen sind genau das, was Sie benötigen, um eine dünne Matrix in der Matrixdatenstruktur von PETSc vorab zuzuweisen. Dann können Sie Ihre Listenliste freigeben, da Sie sie nicht mehr benötigen.

Bei diesem Ansatz wird jedoch davon ausgegangen, dass Sie nur die Liste der Knoten haben, die jedes Element enthält.

Einige Maschengenerierungspakete - beispielsweise Triangle - können nicht nur eine Liste von Elementen und deren Knoten ausgeben, sondern auch eine Liste aller Kanten in Ihrer Triangulation. In diesem Fall besteht keine Gefahr, dass Sie die Anzahl der Einträge ungleich Null überschätzen: Bei stückweise linearen Elementen erhalten Sie für jede Kante genau 2 Einträge in der Steifheitsmatrix. Wenn Sie stückweise quadratisch verwenden, zählt jede Kante für 4 Einträge, aber Sie haben die Idee. In diesem Fall können Sie die Anzahl der Einträge ungleich Null pro Zeile mit einem Durchlauf durch die Kantenliste mithilfe eines normalen Arrays ermitteln.

Bei diesem Ansatz müssen Sie eine besonders große Datei von der Festplatte lesen, die langsamer sein kann als die Verwendung der Elementliste, wenn Ihre tatsächliche Berechnung nicht so groß ist. Trotzdem denke ich, dass es einfacher ist.

Daniel Shapero
quelle

Vielen Dank. Ich habe eine Edge-Liste zur Verfügung, daher werde ich wahrscheinlich vorerst Ihre zweite Methode anwenden, aber ich gehe möglicherweise zurück und versuche die erste Methode, nur um meine Hände mit verknüpften Listen und dergleichen zu beschmutzen (danke für die Einführung ... I ' Ich habe nur eine grundlegende CS-Klasse belegt, und obwohl ich ein Händchen für die Programmierung habe, weiß ich nicht so viel wie ich sollte über Datenstrukturen und Algorithmen)

John Edwardson

Freue mich zu helfen! Ich habe eine Menge meiner CS-Kenntnisse in folgenden Quellen gesammelt: books.google.com/books?isbn=0262032937 - Lesen Sie aus Liebe zu Gott etwas über amortisierte Analysen. Das Programmieren einer eigenen verknüpften Liste oder einer binären Suchbaum-Datenstruktur in C ist die Mühe wert.

Daniel Shapero

5

Wenn Sie Ihr Netz als DMPlex und Ihr Datenlayout als PetscSection angeben, erhalten Sie mit DMCreateMatrix () automatisch die korrekt vorab zugewiesene Matrix. Hier sind PETSc-Beispiele für das Poisson-Problem und das Stokes-Problem .

Matt Knepley
quelle

2

Upvoted

Ich persönlich kenne keinen billigen Weg, um dies zu tun, also überschätze ich einfach die Zahl, dh verwende einen ziemlich großen Wert für alle Zeilen.

Beispiel: Für ein perfekt strukturiertes Netz aus linearen 8-Knoten-Hex-Elementen beträgt die Anzahl der Zeilen in den diagonalen und außerdiagonalen Blöcken dof * 27. Für die meisten vollständig unstrukturierten, automatisch generierten Hex-Maschen überschreitet die Anzahl selten dof * 54. Bei linearen Tets hatte ich nie die Notwendigkeit, über dof * 30 hinauszugehen. Für einige Netze mit sehr schlecht geformten Elementen mit niedrigem Seitenverhältnis müssen Sie möglicherweise etwas größere Werte verwenden.

Der Nachteil ist, dass der lokale Speicherverbrauch (nach Rang) zwischen 2x und 5x liegt. Daher müssen Sie möglicherweise mehr Rechenknoten in Ihrem Cluster als üblich verwenden.

Übrigens habe ich versucht, durchsuchbare Listen zu verwenden, aber die Zeit, die benötigt wurde, um die Sparsity-Struktur zu bestimmen, war mehr als die Montage / Lösung. Meine Implementierung war jedoch sehr einfach und verwendete keine Informationen zu Kanten.

Die andere Option ist die Verwendung von Routinen wie DMMeshCreateExodus, wie in diesem Beispiel gezeigt.

stali
quelle

0

Sie möchten alle eindeutigen (gi, gj) Verbindungen auflisten. Dies schlägt vor, sie alle in einen (nicht duplizierenden) assoziativen Container zu platzieren und dann dessen Kardinalität zu zählen. In C ++ wäre dies ein std :: set <std :: pair <int, int>>. In Ihrem Pseudocode würden Sie "nnz [i] ++" durch "s.insert [pair (gi, gj)]" ersetzen, und dann ist die endgültige Anzahl der Nonzeros s.size (). Es sollte in der Zeit O (n-log-n) ausgeführt werden, wobei n die Anzahl der Nichtzeros ist.

Da Sie wahrscheinlich bereits den Bereich der möglichen GIs kennen, können Sie die Tabelle nach dem GI-Index "aufspreizen", um die Leistung zu verbessern. Dies ersetzt Ihren Satz durch einen std :: vector <std :: set <int>>. Sie füllen das mit "v [gi] .insert (gj)", dann ergibt sich die Gesamtzahl der Nichtzeros aus der Summierung von v [gi] .size () für alle gis. Dies sollte in O (n-log-k) ausgeführt werden, wobei k die Anzahl der Unbekannten pro Element ist (sechs für Sie - im Wesentlichen eine Konstante für die meisten PDE-Codes, sofern Sie nicht über HP-Methoden sprechen).

(Hinweis - wollte, dass dies ein Kommentar zur ausgewählten Antwort ist, war aber zu lang - Entschuldigung!)

rchilton1980
quelle

0

Gehen Sie von einer dünnen Matrix aus $E^T$ von Größenelementen $\times$ dofs.

E_{ich j}^{T} = {\begin{array}{cc} 1 & ich f d Ö f j \in e l e m e n t ich \\ 0 & e l s e w h e r e \end{array}

$E_{ij}^T = \left\{ \begin{array}{cc} 1 & \mathrm{if\ dof}\ j \in \mathrm{element}\ i \\ 0 & \mathrm{elsewhere} \end{array} \right.$ Matrix

A = E E^{T}

$A = E\, E^T$ hat das Sparsity-Muster, das Sie suchen. Denken Sie daran, dass die Umsetzung

E^{T}

$E^T$ ist einfacher, deshalb habe ich definiert

E^{T}

$E^T$ Anstatt von

E

$E$ .

Nicola Cavallini
quelle

Berechnung der Sparsity-Struktur für Finite-Elemente-Matrizen

Antworten: