Algoritmo Cuthill-McKee

Ordenamiento de una matriz según Cuthill-McKee

Ordenamiento RCM de la misma matriz

En álgebra lineal numérica , el algoritmo Cuthill–McKee ( CM ), llamado así por Elizabeth Cuthill y James McKee, ^[1] es un algoritmo para permutar una matriz dispersa que tiene un patrón de escasez simétrico en una forma de matriz de bandas con un ancho de banda pequeño . El algoritmo Cuthill–McKee inverso ( RCM ) debido a Alan George y Joseph Liu es el mismo algoritmo pero con los números de índice resultantes invertidos. ^[2] En la práctica, esto generalmente da como resultado menos relleno que el ordenamiento CM cuando se aplica la eliminación gaussiana. ^[3]

El algoritmo Cuthill McKee es una variante del algoritmo estándar de búsqueda en amplitud que se utiliza en algoritmos de grafos. Comienza con un nodo periférico y luego genera niveles hasta que se agotan todos los nodos. El conjunto se crea a partir de un conjunto enumerando todos los vértices adyacentes a todos los nodos en . Estos nodos se ordenan según predecesores y grado. ${\displaystyle R_{i}}$ ${\displaystyle i=1,2,..}$ ${\displaystyle R_{i+1}}$ ${\displaystyle R_{i}}$ ${\displaystyle R_{i}}$

Algoritmo

Dada una matriz simétrica , la visualizamos como la matriz de adyacencia de un grafo . El algoritmo Cuthill-McKee consiste entonces en reetiquetar los vértices del grafo para reducir el ancho de banda de la matriz de adyacencia. ${\displaystyle n\times n}$

El algoritmo produce una n -tupla ordenada de vértices que es el nuevo orden de los vértices. ${\displaystyle R}$

Primero elegimos un vértice periférico (el vértice con el grado más bajo ) y establecemos . ${\displaystyle x}$ ${\displaystyle R:=(\{x\})}$

Luego, iteramos los siguientes pasos mientras ${\displaystyle i=1,2,\dots }$ ${\displaystyle |R|<n}$

• Construya el conjunto de adyacencia de (con el componente i -ésimo de ) y excluya los vértices que ya tenemos en ${\displaystyle A_{i}}$ ${\displaystyle R_{i}}$ ${\displaystyle R_{i}}$ ${\displaystyle R}$ ${\displaystyle R}$

${\displaystyle A_{i}:=\operatorname {Adj} (R_{i})\setminus R}$

• Ordenar de forma ascendente por predecesor mínimo (el vecino ya visitado con la posición más temprana en R), y como desempate de forma ascendente por grado de vértice . ^[4] ${\displaystyle A_{i}}$
• Añadir al conjunto de resultados . ${\displaystyle A_{i}}$ ${\displaystyle R}$

En otras palabras, numere los vértices de acuerdo con una estructura de nivel particular (calculada mediante una búsqueda en amplitud ) donde los vértices en cada nivel se visitan en orden de numeración de sus predecesores, del más bajo al más alto. Cuando los predecesores son los mismos, los vértices se distinguen por grado (nuevamente ordenados del más bajo al más alto).

Véase también

• Ancho de banda del gráfico
• Matriz dispersa

Referencias

1. E. Cuthill y J. McKee. Reducción del ancho de banda de matrices simétricas dispersas. En Proc. 24th Nat. Conf. ACM , páginas 157–172, 1969.
2. "Ciprian Zavoianu - weblog: Tutorial: Reducción del ancho de banda - El algoritmo CutHill-McKee". 15 de enero de 2009.
3. JA George y J. WH. Liu, Solución informática de grandes sistemas definidos positivos dispersos, Prentice-Hall, 1981
4. El algoritmo Cuthill-McKee inverso en memoria distribuida [1], diapositiva 8, 2016

• Documentación de Cuthill–McKee para las bibliotecas Boost C++ .
• Una descripción detallada del algoritmo Cuthill–McKee.
• Implementación de RCM en MATLAB.
• Rutina RCM reverse_cuthill_mckee de SciPy escrita en Cython .