Разреженный обратный заказ Катилла-МакКи
r = symrcm(S)
r = symrcm(S) возвращает симметричный обратный порядок Катилла-МакКи S. Это перестановка r такой, что S(r,r) имеет тенденцию иметь ненулевые элементы ближе к диагонали. Это хороший предварительный порядок для LU или Cholesky факторизации матриц, которые происходят от длинных, тоненьких проблем. Упорядочение работает как для симметричных, так и для несимметричных 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] Джордж, Алан и Джозеф Лю, Компьютерное решение больших разреженных положительных определенных систем, Прентис-Холл, 1981.
[2] Гилберт, Джон Р., Клеве Молер и Роберт Шрайбер, «Разреженные матрицы в MATLAB: дизайн и реализация», SIAM Journal on Matrix Analysis, 1992. Немного расширенная версия также доступна в виде технического отчета исследовательского центра Xerox Palo Alto.