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

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

RCM-упорядочение той же матрицы

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

Ссылки

1. Э. Катхилл и Дж. Макки. Сокращение полосы пропускания разреженных симметричных матриц в Proc. 24th Nat. Conf. ACM , страницы 157–172, 1969.
2. "Ciprian Zavoianu - веблог: Учебное пособие: Сокращение пропускной способности - Алгоритм Кат-Хилла-Макки". 15 января 2009 г.
3. JA George и J. WH. Liu, Компьютерное решение больших разреженных положительно определенных систем, Prentice-Hall, 1981
4. Обратный алгоритм Катхилла-Макки в распределенной памяти [1], слайд 8, 2016

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