Cuthill-McKee-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Datei:Can 73 cm.pdf
Cuthill-McKee-Sortierung derselben Matrix
Datei:Can 73 rcm.pdf
Umgekehrte Cuthill-McKee-Sortierung derselben Matrix

Der Cuthill-McKee-Algorithmus (benannt nach Elizabeth Cuthill und James[1] McKee) ist in der numerischen Mathematik ein Algorithmus, der eine symmetrische dünnbesetzte Matrix in eine Bandmatrix mit einer geringeren Bandbreite transformiert.[2] 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 geringeren 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.[3]

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

Es sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M\!} eine Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -Tupel von Knoten, die die neue Reihenfolge darstellen, wie folgt:

  • Man wähle einen Startknoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x\!} und setze .
  • Für Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle i=1,2,\dots } führe, solange Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |R|<n} ist, folgende Schritte aus:
  • Konstruiere die Menge der adjazenten Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_i} von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R_i} , wobei Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle R_{i}} die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} -te Komponente von ist, und schließe alle Knoten aus, die schon in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} enthalten sind: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_i := \operatorname{Adj}(R_i) \setminus R}
  • Sortiere Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_i} nach steigendem Knotengrad.
  • Hänge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_i} an das Ergebnis-Tupel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} an.

Wahl des Startknotens

Die Qualität der durch den Algorithmus bestimmten neuen Nummerierung bzw. Permutation hängt entscheidend von der Wahl des Startknotens ab. Da das Bandbreitenminimierungsproblem NP-schwer ist[4], fällt auch die Wahl eines optimalen Startknotens in diese Komplexitätsklasse. Stattdessen schlagen Cuthill und McKee vor, immer einen Knoten minimalen Grads zu wählen[2], dies hat sich aber in der Praxis nicht bewährt. Alternativ ist auch die Wahl eines peripheren Knotens, also eines Knotens im Rand des Graphen, als Startknoten naheliegend. Das Bestimmen eines peripheren Knotens ist allerdings nur in quadratischer Laufzeit möglich, was den eigentlichen Algorithmus dominiert. Daher begnügt man sich in der Praxis damit einen pseudo-peripheren Knoten zu wählen, der auf folgende Weise ermittelt werden kann:

  1. Man wähle einen beliebigen Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \in X\!} .
  2. Man erzeuge die Schichtung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{L_0(x),...,L_{\varepsilon(x)}(x)\}\!} mit der Wurzel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x\!} .
  3. Man wähle einen beliebigen Knoten minimalen Grades Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r \in L_{\varepsilon(x)}(x)\!} .
  4. Man erzeuge die Schichtung mit der Wurzel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r\!} . Falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon(r) > \varepsilon(x)\!} , ersetze man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x\!} durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r\!} und gehe nach 3.
  5. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r\!} ist ein pseudo-peripherer Knoten.

Als Exzentrizität Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon(x)\!} eines Knotens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x\!} eines zusammenhängenden Graphen bezeichnet man die Größe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon(x):=\underset{y\in X}{\max} \text{ dist}(x, y) .\!}

Anwendung

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

Weblinks

Einzelnachweise

  1. ↑ Recommendations for ship hull surface representation, page 6
  2. ↑ a b E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157–172, 1969.
  3. ↑ J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981
  4. ↑ Uriel Feige: Coping with the NP-Hardness of the Graph Bandwidth Problem. In: Algorithm Theory - SWAT 2000. Band 1851. Springer Berlin Heidelberg, Berlin, Heidelberg 2000, ISBN 978-3-540-67690-4, S. 10–19, doi:10.1007/3-540-44985-x_2 (springer.com [abgerufen am 23. März 2020]).
Abgerufen von „https://de.wikiup.org/index.php?title=Cuthill-McKee-Algorithmus&oldid=224161610“