В числовой линейной алгебре , тот Cuthill-Макка алгоритм ( СМ ), названный в честь Элизабет Cuthill и Джеймс [1] Макка, [2] представляет собой алгоритм , чтобы переставить разреженную матрицу , которая имеет симметричный рисунок разреженности в матричной ленте формы с небольшим пропускная способность . Обратный алгоритм Cuthill-Макки ( RCM ) из - за Алан Джордж и Джозеф Лю тот же алгоритм , но с полученными индексами наоборот. [3] На практике это обычно приводит к меньшей заменечем упорядочение CM при применении исключения Гаусса. [4]
Алгоритм Катхилла МакКи является вариантом стандартного алгоритма поиска в ширину, используемого в алгоритмах на графах. Он начинается с периферийного узла, а затем генерирует уровни для пока не будут исчерпаны все узлы. Набор создается из набора перечислив все вершины, смежные со всеми узлами в . Эти узлы упорядочены по предшественникам и степени.
Алгоритм
Учитывая симметричную матрицы мы представляем матрицу в качестве матрицы смежности в виде графа . Алгоритм Катхилла – Макки затем переименовывает вершины графа, чтобы уменьшить полосу пропускания матрицы смежности.
Алгоритм производит упорядоченный набор из n вершин, что является новым порядком вершин.
Сначала мы выбираем периферийную вершину (вершину с наименьшей степенью ) и установить .
Тогда для мы повторяем следующие шаги, пока
- Построить набор смежности из (с участием я -й компонент) и исключить вершины, которые у нас уже есть в
- Сортировать по возрастанию по минимальному предшественнику (уже посещенному соседу с самой ранней позицией в R) и как тай-брейк по возрастанию по степени вершины . [5]
- Добавить к набору результатов .
Другими словами, нумеруйте вершины в соответствии с конкретной структурой уровня (вычисленной поиском в ширину ), где вершины на каждом уровне посещаются, в порядке нумерации их предшественников от самого низкого до самого высокого. Если предшественники совпадают, вершины различаются по степени (опять же в порядке от низшего к высшему).
Смотрите также
Рекомендации
- ^ Рекомендации по изображению поверхности корпуса судна , стр. 6
- ^ Э. Катхилл и Дж. Макки. Уменьшение пропускной способности разреженных симметричных матриц In Proc. 24-й Нац. Конф. ACM , страницы 157–172, 1969.
- ^ http://ciprian-zavoianu.blogspot.ch/2009/01/project-bandwidth-reduction.html
- ^ JA Джордж и Дж. WH. Лю, Компьютерное решение больших разреженных положительно определенных систем, Прентис-Холл, 1981
- ^ Обратный алгоритм Катхилла-Макки в распределенной памяти [1] , слайд 8, 2016
- Документация Катхилла – Макки для библиотек Boost C ++ .
- Подробное описание алгоритма Катхилла – Макки .
- symrcm Реализация RCM в MATLAB.
- reverse_cuthill_mckee Подпрограмма RCM из SciPy, написанная на Cython .