Verschachtelte Dissektion im regulären Raster

9

Bei der Lösung spärlicher linearer Systeme mit direkten Faktorisierungsmethoden wirkt sich die verwendete Ordnungsstrategie erheblich auf den Füllfaktor von Nicht-Null-Elementen in den Faktoren aus. Eine solche Bestellstrategie ist die verschachtelte Dissektion. Ich frage mich, ob es möglich ist, die verschachtelte Dissektionsreihenfolge vorzeitig zu erstellen, wenn nur die Gitterparameter gegeben sind (nehmen Sie ein M x N quadratisches Finite-Differenzen-Gitter mit Differenzen erster Ordnung an).

Bearbeiten Ich habe gerade festgestellt, dass es Code gibt, der dies tut: http://www.cise.ufl.edu/research/sparse/meshnd/

linear-algebra Victor Liu
quelle

Antworten:

8

Ja. Ich habe kürzlich Code geschrieben, um genau dies zu tun.

Angenommen, Sie haben ein Raster und es ist akzeptabel, Blattknoten mit 100 Eckpunkten zu haben. Man kann dann eine rekursive Funktion definieren, bei der die Argumente sind:nx×ny

  • die Abmessungen und Offsets einer rechteckigen Subdomain
  • Ein Zeiger in ein Array, in dem die Neuordnung gespeichert wird

neintureinl(x,y)=x+ynxnx×ny

Jack Poulson
quelle
Ich denke, meine Frage lautet eher: Schneidet verschachtelte Dissektion den Raum wirklich nur rekursiv in zwei Hälften? Ist die Reihenfolge auch, die Grenzindizes vor jeder rechten und linken Hälfte zu platzieren? Ich habe nie eine einfache Erklärung dafür gefunden, was los ist.
Victor Liu
1
Ja, verschachtelte Dissektion ist sehr einfach, aber Sie speichern die Grenzindizes nach der linken und rechten Hälfte. Es geht darum sicherzustellen, dass die beiden Subdomänen nicht direkt miteinander verbunden sind. Bei endlichen Unterschieden ist es daher wichtig, die Größe Ihrer Schablone zu berücksichtigen, wenn Sie entscheiden, wie dick der Separator sein muss. Ich empfehle Ihnen, Lius Übersicht über die multifrontale Methode zu lesen und die Verbindung herzustellen, dass jedes Trennzeichen als Superknoten behandelt wird.
Jack Poulson
Ah ja, das habe ich kurz nach dem Kommentieren gemerkt und dann bearbeitet. Danke für den Hinweis.
Victor Liu