Cuthill-McKee-Algorithmus

Eine gesichtete Version dieser Seite, die am 8. Februar 2012 freigegeben wurde, basiert auf dieser Version.

Dieser Artikel wurde am 8. Februar 2012 auf den Seiten der Qualitätssicherung eingetragen. Bitte hilf mit, ihn zu verbessern, und beteilige dich bitte an der Diskussion!

Folgendes muss noch verbessert werden:

Begründung:Cool. Und wozu ist das nütze? --WB Looking at things 11:45, 8. Feb. 2012 (CET) Eine Frage nach Nützlichkeit ist nicht relevant ;) --WiseWoman 14:17, 8. Feb. 2012 (CET)

Datei:Can 73 orig.pdf

Original Matrix aus der Sammlung von Harwell-Boeing

Unter dem Cuthill-McKee Algorithmus (benannt nach Elizabeth Cuthill und J. McKee) ^[1] (CM) versteht man in der numerischen Mathematik den Algorithmus um eine symetrische dünnbesetzte oder schwachbesetzte Matrix in eine Bandmatrix mit einer geringeren Bandbreite zu transformieren.

Der umgekehrte Cuthill-McKee Algorithmus (RCM) von Alan George ist der selbe Algorithmus mit umgekehrter Indexreihenfolge. Allgemein resultiert der umgekehrte Algorithmus, wenn eine Gaußelimination durchgeführt wird, in einem geringerem Fill-in. Unter "Fill-in" versteht man das Entstehen von Nichtnull-Elementen an Positionen, die mit Null besetzt sind. ^[2]

Der Cuthill-McKee Algorithmus ist eine Variation der Breitensuche für Graphen.

Der Algorithmus wählt einen Startknoten $x\!$ , der die neue Nummer 1 erhält. Dann nummeriert er die Knoten aus der Menge der zum neu nummerierten adjazenten Knoten dem Grad nach neu. Der Unterschied zur Breitensuche besteht nur aus der durch den Grad bestimmten Reihenfolge der Nummerierung.

Algorithmus

Es sei $M\!$ eine $n\times n\!$ Matrix in Adjazenzdarstellung

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.

Man wähle einen Knoten $x\!$ und setze $R:=(\{x\})\!$ .

Für $i=1,2,...\!$ führe, solange $|R|<n\!$ ist, folgende Schritte aus:

Kontruiere die Menge der adjazenten Knoten $A_{i}$ von $R_{i}$ mit $R_{i}\!$ die $i\!$ -te Komponente von $R\!$ und schliesse alle Knoten aus die schon in $R\!$ enthalten sind.

A_{i}:=\operatorname {Adj} (R_{i})\setminus R

Sortiere $A_{i}$ nach steigendem Knotengrad.
Füge $A_{i}$ der Ergebnismenge $R\!$ hinzu.

Anwendung

Der Algorithmus wird angewendet um die Bandbreite und damit den Speicherbedarf von Matrizen zu reduzieren.

Einzelnachweise

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

Weblinks

[cm-1] E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157–172, 1969.

[gl-2] J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981

[1]

[2]