Algoritmo Cuthill-McKee

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search
Ordinamento di una matrice secondo l'algoritmo di Cuthill-McKee.
Ordinamento della stessa matrice secondo RCM.

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[modifica | modifica wikitesto]

  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[modifica | modifica wikitesto]

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