En álgebra lineal numérica , el algoritmo de Cuthill-McKee ( CM ), llamado así por Elizabeth Cuthill y James [1] McKee, [2] es un algoritmo para permutar una matriz dispersa que tiene un patrón de dispersión simétrico en una forma de matriz de bandas con una pequeña ancho de banda . El algoritmo inverso de Cuthill-McKee ( RCM ) debido a Alan George y Joseph Liu es el mismo algoritmo pero con los números de índice resultantes invertidos. [3] En la práctica, esto generalmente resulta en menos rellenoque el orden CM cuando se aplica la eliminación gaussiana. [4]
El algoritmo de Cuthill McKee es una variante del algoritmo de búsqueda estándar en amplitud que se utiliza en los algoritmos de gráficos. Comienza con un nodo periférico y luego genera niveles por hasta que se agoten todos los nodos. El conjunto se crea a partir del conjunto enumerando todos los vértices adyacentes a todos los nodos en . Estos nodos están ordenados según predecesores y grado.
Algoritmo
Dado un simétrico matriz visualizamos la matriz como la matriz de adyacencia de un gráfico . El algoritmo de Cuthill-McKee es entonces un reetiquetado de los vértices del gráfico para reducir el ancho de banda de la matriz de adyacencia.
El algoritmo produce una n- tupla ordenada de vértices que es el nuevo orden de los vértices.
Primero elegimos un vértice periférico (el vértice con el grado más bajo ) y establecer .
Entonces para iteramos los siguientes pasos mientras
- Construya el conjunto de adyacencia de (con el i -ésimo componente de) y excluir los vértices que ya tenemos en
- Clasificar ascendente por predecesor mínimo (el vecino ya visitado con la posición más temprana en R), y como desempate ascendente por grado de vértice . [5]
- Adjuntar al conjunto de resultados .
En otras palabras, numere los vértices de acuerdo con una estructura de nivel particular (calculada por búsqueda de amplitud primero ) donde se visitan los vértices en cada nivel en orden de numeración de su predecesor de menor a mayor. Donde los predecesores son los mismos, los vértices se distinguen por grado (nuevamente ordenados de menor a mayor).
Ver también
Referencias
- ^ Recomendaciones para la representación de la superficie del casco del barco , página 6
- ^ E. Cuthill y J. McKee. Reducción del ancho de banda de matrices simétricas dispersas In Proc. 24th Nat. Conf. ACM , páginas 157-172, 1969.
- ^ http://ciprian-zavoianu.blogspot.ch/2009/01/project-bandwidth-reduction.html
- ^ JA George y J. WH. Liu, solución informática de grandes sistemas definidos positivos dispersos, Prentice-Hall, 1981
- ^ El algoritmo inverso de Cuthill-McKee en memoria distribuida [1] , diapositiva 8, 2016
- Documentación de Cuthill – McKee para las bibliotecas Boost C ++ .
- Una descripción detallada del algoritmo de Cuthill-McKee .
- symrcm Implementación de MATLAB de RCM.
- reverse_cuthill_mckee Rutina RCM de SciPy escrita en Cython .