Cuthill-McKee-Algorithmus

Cuthill-McKee-Sortierung derselben Matrix

Umgekehrte Cuthill-McKee-Sortierung derselben Matrix

Der Cuthill-McKee-Algorithmus (benannt nach Elizabeth Cuthill und James<ref name="mckee"><templatestyles src="Webarchiv/styles.css" />{{#if:20210910184613

      | {{#ifeq: 20210910184613 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Recommendations for ship hull surface representation | {{#invoke:WLink|getEscapedTitle|Recommendations for ship hull surface representation}} | {{#invoke:Webarchiv|getdomain|http://calhoun.nps.edu/bitstream/handle/10945/30131/recommendationsf00fran.pdf}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20210910184613}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Recommendations for ship hull surface representation | {{#invoke:WLink|getEscapedTitle|Recommendations for ship hull surface representation}} | {{#invoke:Webarchiv|getdomain|http://calhoun.nps.edu/bitstream/handle/10945/30131/recommendationsf00fran.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2024-11-20 20:18:07 InternetArchiveBot | 2024-11-20 20:18:07 InternetArchiveBot |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20210910184613}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Recommendations for ship hull surface representation | {{#invoke:WLink|getEscapedTitle|Recommendations for ship hull surface representation}} | {{#invoke:Webarchiv|getdomain|http://calhoun.nps.edu/bitstream/handle/10945/30131/recommendationsf00fran.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2024-11-20 20:18:07 InternetArchiveBot | 2024-11-20 20:18:07 InternetArchiveBot |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Recommendations for ship hull surface representation | {{#invoke:WLink|getEscapedTitle|Recommendations for ship hull surface representation}} | {{#invoke:Webarchiv|getdomain|http://calhoun.nps.edu/bitstream/handle/10945/30131/recommendationsf00fran.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2024-11-20 20:18:07 InternetArchiveBot | 2024-11-20 20:18:07 InternetArchiveBot |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Recommendations for ship hull surface representation | {{#invoke:WLink|getEscapedTitle|Recommendations for ship hull surface representation}} | {{#invoke:Webarchiv|getdomain|http://calhoun.nps.edu/bitstream/handle/10945/30131/recommendationsf00fran.pdf}} }} (Memento{{#if: {{#if: 2024-11-20 20:18:07 InternetArchiveBot | 2024-11-20 20:18:07 InternetArchiveBot |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Recommendations for ship hull surface representation | {{#invoke:WLink|getEscapedTitle|Recommendations for ship hull surface representation}} | {{#invoke:Webarchiv|getdomain|http://calhoun.nps.edu/bitstream/handle/10945/30131/recommendationsf00fran.pdf}} }}  
                 }}}}}}}}{{#if:2024-11-20 20:18:07 InternetArchiveBot
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20210910184613|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://calhoun.nps.edu/bitstream/handle/10945/30131/recommendationsf00fran.pdf}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: Recommendations for ship hull surface representation
    | {{#if: {{#invoke:WLink|isBracketedLink|Recommendations for ship hull surface representation}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://calhoun.nps.edu/bitstream/handle/10945/30131/recommendationsf00fran.pdf%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://calhoun.nps.edu/bitstream/handle/10945/30131/recommendationsf00fran.pdf%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://calhoun.nps.edu/bitstream/handle/10945/30131/recommendationsf00fran.pdf }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }}, page 6</ref> McKee) ist in der numerischen Mathematik ein Algorithmus, der eine symmetrische dünnbesetzte Matrix in eine Bandmatrix mit einer geringeren Bandbreite transformiert.<ref name="cm"> E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157–172, 1969.</ref>  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.<ref name="gl"> J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981 </ref>

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 <math>M\!</math> eine <math>n\times n</math> 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 <math>n</math>-Tupel von Knoten, die die neue Reihenfolge darstellen, wie folgt:

Man wähle einen Startknoten <math>x\!</math> und setze <math>R:=(x)\!</math>.

Für <math>i=1,2,\dots</math> führe, solange <math>|R|<n</math> ist, folgende Schritte aus:

Konstruiere die Menge der adjazenten Knoten <math>A_i</math> von <math>R_i</math>, wobei <math>R_i</math> die <math>i</math>-te Komponente von <math>R</math> ist, und schließe alle Knoten aus, die schon in <math>R</math> enthalten sind: <math>A_i := \operatorname{Adj}(R_i) \setminus R</math>
Sortiere <math>A_i</math> nach steigendem Knotengrad.
Hänge <math>A_i</math> an das Ergebnis-Tupel <math>R</math> 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<ref>{{#invoke:Vorlage:Literatur|f}}</ref>, 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<ref name="cm" />, 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:

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

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

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

Dokumentation des Cuthill–McKee-Algorithmus für die Boost C++-Bibliothek (englisch)
Beschreibung des Cuthill–McKee-Algorithmus (englisch)
Ein Vergleich der Qualität und Effizienz verschiedener Algorithmen zur Wahl eines pseudo-peripheren Knotens (englisch)

Einzelnachweise