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

В числовой линейной алгебре алгоритм Катхилла-Макки ( CM ), названный в честь Элизабет Катхилл и Джеймса Макки, ^{[ 1 ]} — это алгоритм преобразования разреженной матрицы с симметричным шаблоном разреженности в форму ленточной матрицы с небольшой полосой пропускания . Обратный алгоритм Катхилла-Макки ( RCM ), предложенный Аланом Джорджем и Джозефом Лю, представляет собой тот же алгоритм, но с обратными результирующими индексными числами. ^{[ 2 ]} На практике это обычно приводит к меньшему заполнению, чем порядок CM, когда применяется метод исключения Гаусса. ^{[ 3 ]}

Алгоритм Катхилла Макки представляет собой вариант стандартного поиска в ширину. Алгоритм, используемый в графовых алгоритмах. Все начинается с периферийного узла, а затем генерирует уровни $R_{i}$ для $i=1,2,..$ пока все узлы исчерпаны. Набор $R_{i+1}$ создается из набора $R_{i}$ перечислив все вершины, смежные со всеми узлами в $R_{i}$ . Эти узлы упорядочены по предшественникам и степени.

Алгоритм

Учитывая симметричный $n\times n$ мы визуализируем матрицу как матрицу смежности графа матрица , . Алгоритм Катхилла – Макки представляет собой перемаркировку вершин графа для уменьшения пропускной способности матрицы смежности.

Алгоритм создает упорядоченный n -кортеж $R$ вершин, что является новым порядком вершин.

Сначала мы выбираем периферийную вершину (вершину с наименьшей степенью ) $x$ и установить $R:=(\{x\})$ .

Тогда для $i=1,2,\dots$ мы повторяем следующие шаги, пока $|R|<n$

Создайте набор смежности $A_{i}$ из $R_{i}$ (с $R_{i}$ й компонент i - $R$ ) и исключим вершины, которые у нас уже есть в $R$

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

Сортировать $A_{i}$ по возрастанию по минимальному предшественнику (уже посещенному соседу с самой ранней позицией в R) и в качестве тай-брейка по возрастанию по степени вершины . ^{[ 4 ]}
Добавить $A_{i}$ в набор результатов $R$ .

Другими словами, нумеруйте вершины в соответствии с определенной структурой уровня (вычисленной поиском в ширину ), где вершины на каждом уровне посещаются в порядке нумерации их предшественников, от низшего к высшему. Если предшественники одинаковы, вершины различаются по степени (опять же в порядке от низшего к высшему).

См. также

Ссылки

^ Э. Катхилл и Дж. Макки. Уменьшение пропускной способности разреженных симметричных матриц. В учеб. 24-й Нац. Конф. ACM , страницы 157–172, 1969.
^ «Чиприан Завояну — блог: Учебное пособие: уменьшение пропускной способности — алгоритм Катхилла-Макки» .
^ JA Джордж и J.WH. Лю, Компьютерное решение больших разреженных положительно определенных систем, Прентис-Холл, 1981 г.
^ Обратный алгоритм Катхилла-Макки в распределенной памяти [1] , слайд 8, 2016 г.

Документация Катхилла-Макки для библиотек Boost C++ .
Подробное описание алгоритма Катхилла–Макки .
symrcm Реализация RCM в MATLAB.
verse_cuthill_mckee RCM-процедура из SciPy, написанная на Cython .

[cm-1] Э. Катхилл и Дж. Макки. Уменьшение пропускной способности разреженных симметричных матриц. В учеб. 24-й Нац. Конф. ACM , страницы 157–172, 1969.

[2] «Чиприан Завояну — блог: Учебное пособие: уменьшение пропускной способности — алгоритм Катхилла-Макки» .

[gl-3] JA Джордж и J.WH. Лю, Компьютерное решение больших разреженных положительно определенных систем, Прентис-Холл, 1981 г.

[4] Обратный алгоритм Катхилла-Макки в распределенной памяти [1] , слайд 8, 2016 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]