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

Матеріал з Вікіпедії — вільної енциклопедії.
Jump to navigation Jump to search
Впорядкування матриці алгоритмом Катхілл—Маккі
ЗКМ впорядкування тої ж матриці

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

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

Алгоритм[ред.ред. код]

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

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

Спочатку обираємо периферійну вершину, або псевдопериферійну, бо периферійну зазвичай важко знайти, і встановлюємо .

Після цього ми повторюємо наступні кроки допоки

  • Конструюємо множину суміжності для  — i-й компонент ) і виключаємо вершини, які вже в
  • Сортуємо за збільшенням степені вершини.
  • Додаємо до результовної множини .

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

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. Елізабет Катхілл і Джеймс Маккі. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157–172, 1969.
  2. http://ciprian-zavoianu.blogspot.ch/2009/01/project-bandwidth-reduction.html
  3. J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981