Cuthill-McKee-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Cuthill-McKee-Sortierung derselben Matrix
Umgekehrte Cuthill-McKee-Sortierung derselben Matrix

Der Cuthill-McKee-Algorithmus (benannt nach Elizabeth Cuthill und J. McKee) ist in der numerischen Mathematik ein Algorithmus, der eine symmetrische dünnbesetzte Matrix in eine Bandmatrix mit einer geringeren Bandbreite transformiert.[1] Für Bandmatrizen existieren sehr effiziente Berechnungsalgorithmen, beispielsweise für die Lösung von sehr großen linearen Gleichungssystemen (siehe BLAS).

Der umgekehrte Cuthill-McKee-Algorithmus von Alan George ist derselbe Algorithmus mit umgekehrter Indexreihenfolge. Im Allgemeinen führt der umgekehrte Algorithmus zu einem geringerem Fill-in, wenn eine Gaußelimination durchgeführt wird. Unter „Fill-in“ versteht man das Entstehen von Nichtnull-Elementen an Positionen, die in der ursprünglichen Matrix mit Null besetzt sind.[2]

Der Cuthill-McKee-Algorithmus unterscheidet sich von der Breitensuche für Graphen durch seine Reihenfolge, die durch Nummerierung adjazenter Knoten anhand ihres Grades ermittelt wird.

Algorithmus[Bearbeiten]

Es sei M\! eine n\times n\! Adjazenzmatrix, also eine symmetrische Matrix, die als Einträge nur Nullen und Einsen besitzt. Der Cuthill-McKee-Algorithmus ist eine Umnummerierung der Knoten des durch die Adjazenzmatrix repräsentierten Graphen, um die Bandbreite der Adjazenzmatrix zu reduzieren. Der Algorithmus errechnet ein n-Tupel von Knoten, die die neue Reihenfolge darstellen, wie folgt:

  • Man wähle einen Knoten x\! und setze R:=(\{x\})\!.
  • Für i=1,2,\dots führe, solange |R|<n ist, folgende Schritte aus:
  • Konstruiere die Menge der adjazenten Knoten A_i von R_i, wobei R_i die i-te Komponente von R ist, und schließe alle Knoten aus, die schon in R enthalten sind: A_i := \operatorname{Adj}(R_i) \setminus R
  • Sortiere A_i nach steigendem Knotengrad.
  • Hänge A_i an das Ergebnis-Tupel R an.

Wahl des Startknotens[Bearbeiten]

Aufgrund der kleineren Adjazenzmenge von peripheren Knoten (Knoten deren Exzentrizität gleich dem Durchmesser des Graphen ist), ist es sinnvoll einen solchen als Startknoten zu wählen. Es ist jedoch sehr aufwändig einen peripheren Knoten zu ermitteln (NP-Vollständiges Problem). Man begnügt sich daher mit einem pseudo-peripheren Knoten, der auf folgende Weise ermittelt wird:

  1. Man wähle einen beliebigen Knoten x \in X\!.
  2. Man erzeuge die Schichtung \{L_0(x),...,L_{\varepsilon(x)}(x)\}\! mit der Wurzel x\!.
  3. Man wähle einen beliebigen Knoten minimalen Grades r \in L_{\varepsilon(x)}(x)\!.
  4. Man erzeuge die Schichtung \{L_0(r),...,L_{\varepsilon(r)}(r)\}\! mit der Wurzel r\!. Falls \varepsilon(r) > \varepsilon(x)\!, ersetze man x\! durch r\! und gehe nach 3..
  5. r\! ist ein pseudo-peripherer Knoten.

Als Exzentrizität \varepsilon(x)\! eines Knotens x\! eines zusammenhängenden Graphen bezeichnet man die Größe \varepsilon(x):=\underset{y\in X}{\max} \text{ dist}(x, y) .\!

Anwendung[Bearbeiten]

Der Algorithmus wird angewendet, um die Bandbreite von Matrizen zu reduzieren und damit den Aufwand der Gauß-Elimination bei der Lösung linearer Gleichungssysteme zu verringern.

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157–172, 1969.
  2. J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981