Алгоритм Катхілл — Маккі

Впорядкування матриці алгоритмом Катхілл — Маккі

ЗКМ впорядкування тої ж матриці

Алгоритм Катхілл — Маккі (КМ), названий на честь Елізабет Катхілл і Джеймса Маккі,^[1] це алгоритм переведення розрідженої матриці, яка симетрично розріджена, у смугову матрицю з малою шириною смуги, шляхом переставляння рядків і стовпчиків. Зворотний алгоритм Катхілл Маккі (ЗКМ) запропонований Аланом Джорджем — це той самий алгоритм, але з оберненим порядком індексування вершин.^[2] На практиці це допомагає отримати менше заповнювання нульових позицій порівняння з КМ впорядкуванням при використанні методу Гауса.^[3]

Алгоритм Катхілл — Маккі — це варіант стандартного пошуку в ширину, що використовується для графів. Він стартує з периферійної вершини і генерує рівневу структуру ${\displaystyle R_{i}}$ для ${\displaystyle i=1,2,..}$ допоки не вичерпано всі вершини. Множина ${\displaystyle R_{i+1}}$ утворюється за допомогою множини ${\displaystyle R_{i}}$ збираючи всі вершини суміжні вершинам в ${\displaystyle R_{i}}$. Ці вершини записуються в порядку збільшення степеня вершини. Цей останній момент і є відмінність від алгоритму пошуку в ширину.

Алгоритм

Маючи симетричну ${\displaystyle n\times n}$ матрицю ми візуалізуємо її як матрицю суміжності графу. Тоді алгоритм Катхілл — Маккі перепозначає вершини графу, щоб зменшити ширину смуги матриці суміжності.

Алгоритм формує впорядкований кортеж ${\displaystyle R}$ з n елементів, який містить новий порядок вершин.

Спочатку обираємо периферійну вершину, або псевдопериферійну, бо периферійну зазвичай важко знайти, ${\displaystyle x}$ і встановлюємо ${\displaystyle R:=(\{x\})}$.

Після цього ${\displaystyle i=1,2,\dots }$ ми повторюємо наступні кроки допоки ${\displaystyle |R|<n}$

• Конструюємо множину суміжності ${\displaystyle A_{i}}$ для ${\displaystyle R_{i}}$ (з ${\displaystyle R_{i}}$ — i-й компонент ${\displaystyle R}$) і виключаємо вершини, які вже в ${\displaystyle R}$

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

• Сортуємо ${\displaystyle A_{i}}$ за збільшенням степені вершини.
• Додаємо ${\displaystyle A_{i}}$ до результовної множини ${\displaystyle R}$.

Інакше кажучи, нумеруємо вершини відповідно до спеціального пошуку в ширину де сусідні вершини відвідуються в порядку від найменшого до найбільшого степеня.

Див. також

• Розріджена матриця

Примітки

1. Елізабет Катхілл і Джеймс Маккі. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157—172, 1969.
2. Архівована копія. Архів оригіналу за 18 січня 2017. Процитовано 9 квітня 2017.
3. J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981

• Cuthill–McKee documentation [Архівовано 29 квітня 2017 у Wayback Machine.] для Boost.
• A detailed description of the Cuthill–McKee algorithm [Архівовано 3 листопада 2009 у Wayback Machine.].
• symrcm [Архівовано 7 липня 2016 у Wayback Machine.] MATLAB's реалізація RCM.