Cuthill–McKee algoritm

Cuthill-McKee beställning av en matris

RCM-beställning av samma matris

I numerisk linjär algebra är Cuthill –McKee-algoritmen ( CM ), uppkallad efter Elizabeth Cuthill och James McKee, en algoritm för att permutera en gles matris som har ett symmetriskt sparsitetsmönster till en bandmatrisform med liten bandbredd . Den omvända Cuthill–McKee-algoritmen ( RCM ) på grund av Alan George och Joseph Liu är samma algoritm men med de resulterande indextalen omvända. I praktiken resulterar detta i allmänhet i mindre utfyllnad än CM-ordern när Gaussisk eliminering tillämpas.

Cuthill McKee-algoritmen är en variant av standardsökningsalgoritmen med bredd-först som används i grafalgoritmer. Den börjar med en perifer $i=1,2,..$ och genererar sedan nivåerna $R_{i}$ för tills alla noder är slut. Uppsättningen $R_{i+1}$ skapas från uppsättningen $R_{i}$ genom att lista alla hörn intill alla noder i $R_{i}$ . Dessa noder är ordnade efter föregångare och grad.

Algoritm

Givet en symmetrisk $n\ gånger n$ matris visualiserar vi matrisen som närliggande matris till en graf . Cuthill–McKee-algoritmen är sedan en ommärkning av hörn för att minska bandbredden för närliggande matris.

Algoritmen producerar en ordnad n -tuppel $R$ av hörn som är den nya ordningen för hörnen.

Först väljer vi en perifer vertex (punkten med den lägsta graden ) $x$ och sätter $R:=(\{x\})$ .

Sedan för $i=1,2,\dots$ upprepar vi följande steg medan $|R|<n$

Konstruera angränsande uppsättning $A_{i}$ av $R_{i}$ (med $R_{i}$ den i -te komponenten av $R$ ) och exkludera de hörn vi redan har i $R$

A_{i}:=\operatörsnamn {Adj} (R_{i})\setminus R

Sortera $A_{i}$ stigande efter minsta föregångare (den redan besökta granne med den tidigaste positionen i R), och som ett tiebreak stigande med vertexgrad .
Lägg till $A_{i}$ till resultatuppsättningen $R$ .

Med andra ord, numrera hörnen enligt en viss nivåstruktur (beräknad med bredd-först-sökning ) där hörnen i varje nivå besöks i ordning efter föregångarens numrering från lägsta till högsta. Där föregångarna är desamma, särskiljs hörn efter grad (återigen ordnade från lägsta till högsta).

Se även

^ E. Cuthill och J. McKee. Reducering av bandbredden för glesa symmetriska matriser I Proc. 24:e Nat. Konf. ACM , sidorna 157–172, 1969.
^ "Ciprian Zavoianu - webblogg: Handledning: Bandbreddsminskning - CutHill-McKee Algorithm" .
^ JA George och J. WH. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981
^ The Reverse Cuthill-McKee Algorithm in Distributed-Memory [1] , bild 8, 2016

Cuthill–McKee-dokumentation för Boost C++-biblioteken .
En detaljerad beskrivning av Cuthill–McKee-algoritmen .
symrcm MATLAB:s implementering av RCM.
reverse_cuthill_mckee RCM-rutin från SciPy skriven i Cython .

[cm-1] E. Cuthill och J. McKee. Reducering av bandbredden för glesa symmetriska matriser I Proc. 24:e Nat. Konf. ACM , sidorna 157–172, 1969.

[2] "Ciprian Zavoianu - webblogg: Handledning: Bandbreddsminskning - CutHill-McKee Algorithm" .

[gl-3] JA George och J. WH. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981

[4] The Reverse Cuthill-McKee Algorithm in Distributed-Memory [1] , bild 8, 2016