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

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

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

Алгоритм

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

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

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

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

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

A_{i} : = Adj (R_{i}) ∖ R

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

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

Див. також

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

Примітки

Шаблон:Reflist

Cuthill–McKee documentation Шаблон:Webarchive для Boost.
A detailed description of the Cuthill–McKee algorithm Шаблон:Webarchive.
symrcm Шаблон:Webarchive MATLAB's реалізація RCM.

Шаблон:Алгоритми на графах

↑ Елізабет Катхілл і Джеймс Маккі. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157—172, 1969.
↑ Шаблон:Cite web
↑ J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981

[cm-1] Елізабет Катхілл і Джеймс Маккі. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157—172, 1969.

[2] Шаблон:Cite web

[gl-3] J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981

[1]

[2]

[3]

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

Алгоритм

Див. також

Примітки

Навігаційне меню

Пошук