Algoritmo Cuthill-McKee

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].

Ordinamento di una matrice secondo l'algoritmo di Cuthill-McKee.

Ordinamento della stessa matrice secondo RCM.

Note

1. E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157–172, 1969.
2. 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.

Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica