Algebraische Algorithmen

Einer der wichtigsten Vertreter der algebraischen Algorithmen ist die Spektral-Bisektion, die auch Eigenwert-Bisektion [Pothen u. a. 1990], [Barnes und Hoffmann 1982], [Powers 1988] oder Simon's Methode [Khan und Topping 1996] genannt wird. Zwischen der Spektral-Bisektion und der Finite-Elemente-Berechnung besteht ein direkter mechanischer Zusammenhang. Zur Partitionierung wird die Laplace-Matrix (siehe Abbildung 2.18) aufgestellt. Diese quadratische Matrix hat für jedes Element eine Zeile und Spalte. Auf der Hauptdiagonalen steht die Anzahl der an ein Element angrenzende Elemente. Für Elemente, die miteinander verbunden sind, steht auf den beiden zugehörigen Nebendiagonalenelementen eine $-1$. Die restlichen Matrixeinträge sind $0$.

Abbildung 2.18: Spektral-Bisektion: a) Elemente-Netz, b) Laplace-Matrix

Durch Berechnung des zweiten Eigenvektors dieser Matrix erhält man die Partitionierung der Elemente in zwei Teilgebiete. Der zweite Eigenvektor wird auch Fiedlervektor genannt [Fiedler 1973], [Fiedler 1975].

Abbildung 2.19: Spektral-Bisektion: a) zwei Teilgebiete, b) vier Teilgebiete, c) acht Teilgebiete

[Simon 1991] zeigt an Beispielen, dass dieses Verfahren das schnellste Verfahren der Klasse der Bisektionsverfahren ist. Die Qualität der Aufteilung ist gut (siehe Abbildung 2.19), wobei die Anzahl der Koppelknoten relativ gering ist [Lämmer 1997].