Cuthill-McKee-Algorithmus

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