Abbildung: Netzaufteilungsalgorithmus
Im Programm ist der Netzaufteilungsalgorithmus nach C. Farhat [Farhat, 1988] implementiert. Er dient dazu, eine Zuordnung der Elemente auf die Prozessoren zu erreichen. An einen solchen Algorithmus sind folgende Anforderungen zu stellen: Alle Teilgebiete sollen gleich groß sein, damit die Rechenlast auf allen Prozessoren gleich ist. Um einen möglichst geringen Austausch zwischen den Prozessoren zu haben, ist eine minimale Außenlänge der Gebiete notwendig. Eine weitere Anforderung an einen solchen Algorithmus ist, daß nur zusammenhängende Gebiete entstehen. Die Anzahl der Nachbarn eines Gebietes sollte möglichst gering sein.
Während der Aufteilung des Gebietes wird zuerst eine Wichtung der einzelnen Knoten vorgenommen. Diese ist gleich der Anzahl der an einen Knoten angrenzenden Elemente. Danach wird der Knoten mit der geringsten Wichtung gesucht, der auf einer Außengrenze des Gesamtgebietes liegt. Dem Teilgebiet werden nun alle Elemente zugeordnet, die an diesen Knoten anstoßen. Als nächstes werden alle nicht vergebenen Elemente, die an das Teilgebiet angrenzen, dem Teilgebiet zugeordnet. Die Wichtung der Knoten wird als nächstes reduziert und die den Teilgebieten zugeordneten Elemente werden markiert. Die Vorgänge Zuweisen, Reduzieren und Markieren werden nun solange wiederholt, bis dem Teilgebiet ausreichend viele Elemente zugeordnet wurden. Die Anzahl der Elemente je Teilgebiet ergibt sich aus der Division der Gesamtanzahl durch die Anzahl der gewünschten Teilgebiete. Das Teilgebiet, welches zuletzt ermittelt wird, erhält deshalb - wenn nötig - eine etwas geringere Anzahl. Für das zweite Teilgebiet wird nun wiederum der Knoten mit der geringsten Wichtung gesucht und der Vorgang wiederholt sich.