Algoritmo Cuthill-McKee
![Abbozzo matematica](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/45px-Crystal128-kmplot.svg.png)
Questa voce sull'argomento matematica è solo un abbozzo.
Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/03/Can_73_cm.svg/220px-Can_73_cm.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7a/Can_73_rcm.svg/220px-Can_73_rcm.svg.png)
L'algoritmo Cuthill-McKee (CM), ideato da Elizabeth Cuthill e J. McKee[1], permette di permutare una matrice sparsa simmetrica in una matrice a banda più compatta e quindi più facilmente risolvibile. L'algoritmo Cuthill-McKee inverso (RCM), proposto da Alan George, adotta lo stesso procedimento ma sistemando i termini della matrice con i pedici invertiti: in generale ciò consente, rispetto al CM, di mantenere un maggior numero di termini nulli quando l'algoritmo di Gauss viene successivamente impiegato[2].
Note
- ^ 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
Collegamenti esterni
- Cuthill–McKee documentation for the Boost C++ Libraries.
- A detailed description of the Cuthill–McKee algorithm.
- symrcm MATLAB's implementation of RCM.
- reverse_cuthill_mckee RCM routine from SciPy written in Cython.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)