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).
Примеры
Обратное упорядоченное расположение Cuthill-McKee
Оператор
B = bucky;
использует функцию в demos тулбокс, чтобы сгенерировать графиков смежности усеченного икосаэдра. Это больше известно как футбольный мяч, Бакминстер Фуллер геодезический купол (отсюда и название bucky), или, совсем недавно, в виде 60-атомной молекулы углерода. Вершин 60. Вершины были упорядочены нумерацией половины из них из одного полушария, пятиугольник - пятиугольником; затем отражение в другое полушарие и склеивание двух половин вместе.
При такой нумерации матрица не имеет особенно узкой полосы пропускания, как показывает первый шпионский график:
figure();
subplot(1,2,1),spy(B),title('B')
Обратное упорядоченное расположение Cuthill-McKee получено с:
p = symrcm(B); R = B(p,p);
The 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] George, Alan and Joseph Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice Hall, 1981.
[2] Gilbert, John R., Cleve Moler, and Robert Schreiber, «Разреженные матрицы in MATLAB: Design and Implementation», SIAM Journal on Matrix Analysis, 1992. Немного расширенная версия также доступна в виде технического отчета исследовательского центра Xerox Palo Alto Research Center.