Симметричная аппроксимация минимальной степени сочетания
p = symamd(S)
p = symamd(S,knobs)
[p,stats] = symamd(...)
p = symamd(S) для симметричной положительно определенной матрицы S, возвращает вектор сочетания p таким образом S(p,p) имеет тенденцию иметь более рассеянный фактор Холецкого, чем S. Чтобы найти упорядоченное расположение для S, symamd создает матрицу M таким образом spones(M'*M) = spones (S), и затем вычисляет p = colamd(M). The symamd функция может также хорошо работать для симметричных неопределенных матриц.
S должны быть квадратными; ссылка только на строго нижнюю треугольную деталь.
p = symamd(S,knobs) где knobs является скаляром. Если S является n-by- n, строки и столбцы с более чем knobs*n записи удаляются до упорядоченного расположения и упорядочиваются последним в выход сочетания p. Если на knobs параметр отсутствует, тогда knobs = spparms('wh_frac').
[p,stats] = symamd(...) создает дополнительный вектор stats который обеспечивает данные о упорядоченном расположении и валидности матрицы S.
stats(1) | Количество плотных или пустых строк, проигнорированных |
stats(2) | Количество плотных или пустых столбцов, проигнорированных |
stats(3) | Количество наборов мусора, выполненных во внутренней структуре данных, используемой |
stats(4) |
|
stats(5) | Самый правый индекс столбца, который не сортирован или содержит повторяющиеся записи или |
stats(6) | Последний просматриваемый повторяющийся или неупорядоченный индекс строки в индексе столбца, заданном |
stats(7) | Количество повторяющихся и неупорядоченных индексов строк |
Хотя, MATLAB® встроенные функции генерируют действительные разреженные матрицы, пользователь может создать недопустимую разреженную матрицу с помощью MATLAB C или Фортран API и передать ее в symamd. По этой причине symamd проверяет, что S действителен:
Если индекс строки появляется в одном столбце два или более раз, symamd игнорирует повторяющиеся записи, продолжает обработку и предоставляет информацию о повторяющихся записях в stats(4:7).
Если индексы строк в столбце находятся вне порядка, symamd сортирует каждый столбец своей внутренней копии матрицы S (но не восстанавливает входную матрицу S), продолжает обработку и предоставляет информацию о неупорядоченных записях в stats(4:7).
Если S является недопустимым любым другим способом, symamd невозможно продолжить. Оно печатает сообщение об ошибке и не возвращает выходных аргументов (p или stats).
За упорядоченное расположение следует симметричное дерево исключения после поступорядоченного расположения.
Вот сравнение обратного алгоритма Катхилла-Макки и минимальной степени на примере мяча Баки, упомянутом в symrcm страница с описанием.
B = bucky+4*speye(60); r = symrcm(B); p = symamd(B); R = B(r,r); S = B(p,p); subplot(2,2,1), spy(R,4), title('B(r,r)') subplot(2,2,2), spy(S,4), title('B(s,s)') subplot(2,2,3), spy(chol(R),4), title('chol(B(r,r))') subplot(2,2,4), spy(chol(S),4), title('chol(B(s,s))')
Несмотря на то, что это очень маленькая проблема, поведение обоих упорядоченных расположений типично. RCM создает матрицу с узкой шириной полосы, которая заполняется почти полностью во время факторизации Холесского. Минимальная степень создает структуру с большими блоками смежных нулей, которые не заполняются во время факторизации. Следовательно, упорядоченное расположение минимальной степени требуется меньше времени и памяти для факторизации.
Авторы кода для symamd Стефан И. Ларимор и Тимоти А. Дэвис (davis@cise.ufl.edu), Флоридский университет. Алгоритм был разработан в сотрудничестве с John Gilbert, Xerox PARC, и Esmond Ng, Oak Ridge National Laboratory. Разреженные матрицы алгоритмов во Флоридском университете: https://www.cise.ufl.edu/research/sparse/