Алгоритм Катхилла–Макки
Упорядочение матрицы Катхилла-Макки
RCM-упорядочение той же матрицы

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

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

Алгоритм

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

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

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

Затем мы повторяем следующие шаги, пока я = 1 , 2 , … {\displaystyle i=1,2,\точки} | Р | < н {\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 .
Взято с "https://en.wikipedia.org/w/index.php?title=Катхилл–Макки_алгоритм&oldid=1253349743"