symrcm
Разреженное упорядоченное расположение обратного алгоритма Катхилла-Макки
Синтаксис
r = symrcm(S)
Описание
r = symrcm(S) возвращает симметричное упорядоченное расположение обратного алгоритма Катхилла-Макки S. Это - перестановка r, таким образом, что S(r,r) имеет тенденцию иметь свои ненулевые элементы ближе к диагонали. Это - хорошее предварительное упорядоченное расположение для LU или факторизации Холесского матриц, которые прибывают из долгих, тощих проблем. Упорядоченное расположение работает и на симметричный и на несимметричный S.
Для действительной, симметричной разреженной матрицы, S, собственные значения S(r,r) совпадают с теми из S, но eig(S(r,r)), вероятно, занимает меньше времени, чтобы вычислить, чем eig(S).
Примеры
Упорядоченное расположение обратного алгоритма Катхилла-Макки
Оператор
B = bucky;
использует функцию в тулбоксе demos, чтобы сгенерировать график смежности усеченного икосаэдра. Это более известно как футбольный мяч, Бакминстер Фуллер геодезический купол (отсюда имя bucky), или, позже, как углеродная молекула с 60 атомами. Существует 60 вершин. Вершины были упорядочены путем нумерации половины из них от одного полушария, пятиугольника пятиугольником; затем отражаясь в другое полушарие и склеивая эти две половины.
С этой нумерацией матрица не имеет особенно узкой пропускной способности, когда первый график шпиона показывает:
figure();
subplot(1,2,1),spy(B),title('B')
Упорядоченное расположение обратного алгоритма Катхилла-Макки получено с:
p = symrcm(B); R = B(p,p);
График spy показывает намного более узкую пропускную способность.
subplot(1,2,2),spy(R),title('B(p,p)')
Этот пример продолжен на странице с описанием для symamd.
Пропускная способность может также быть вычислена с:
[i,j] = find(B); bw = max(i-j) + 1;
Пропускная способность B и R равняется 35 и 12, соответственно.
Алгоритмы
Алгоритм сначала находит псевдопериферийную вершину графика матрицы. Это затем генерирует структуру уровня поиском в ширину и заказывает вершины путем уменьшения расстояния от псевдопериферийной вершины. Реализация базируется тесно на реализации SPARSPAK, описанной Джорджем и Лю.
Ссылки
[1] Джордж, Алан и Джозеф Лю, компьютерное решение больших разреженных положительных определенных систем, Prentice Hall, 1981.
[2] Гильберт, Джон Р., Клив Молер и Роберт Шрайбер, “Разреженные матрицы в MATLAB: Разработка и реализация”, SIAM Journal на Анализе матрицы, 1992. Немного расширенная версия также доступна как технический отчет от Научно-исследовательского центра Xerox Пало-Альто.