Алгоритм Катхилла – Макки - Cuthill–McKee algorithm

Упорядочение матрицы Катхилла-Макки

Заказ одной и той же матрицы в RCM

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

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

Алгоритм

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

Алгоритм производит упорядоченный ппара ${\displaystyle R}$ вершин, который является новым порядком вершин.

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

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

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

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

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

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

Смотрите также

• Пропускная способность графика
• Разреженная матрица

использованная литература

1. Рекомендации по изображению поверхности корпуса судна, стр. 6
2. Э. Катхилл и Дж. Макки. Уменьшение пропускной способности разреженных симметричных матриц В Proc. 24-й Нац. Конф. ACM, страницы 157–172, 1969.
3. http://ciprian-zavoianu.blogspot.ch/2009/01/project-bandwidth-reduction.html
4. Дж. А. Джордж и Дж. В-Х. Лю, Компьютерное решение больших разреженных положительно определенных систем, Прентис-Холл, 1981
5. Обратный алгоритм Катхилла-Макки в распределенной памяти [1], слайд 8, 2016

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