Симметричная аппроксимационная минимальная степень перестановки
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). symamd функция может также хорошо работать для симметричных неопределенных матриц.
S должны быть квадратными; имеется ссылка только на строго нижнюю треугольную часть.
p = symamd(S,knobs) где knobs является скаляром. Если S является nоколо-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 ® генерируют действительные разреженные матрицы, пользователь может создать недопустимую разреженную матрицу, используя API MATLAB C или Fortran, и передать ее 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 производит матрицу с узкой полосой пропускания, которая заполняется почти полностью во время факторизации Cholesky. Минимальная степень создает структуру с большими блоками смежных нулей, которые не заполняются во время факторизации. Следовательно, упорядочение минимальной степени требует меньшего времени и памяти для факторизации.
Авторы кода для symamd Стефан И. Ларимор и Тимоти А. Дэвис (davis@cise.ufl.edu), Флоридский университет. Алгоритм был разработан в сотрудничестве с Джоном Гилбертом, Xerox PARC, и Эсмондом Нгом, Национальной лабораторией Оук-Ридж. Исследования алгоритмов разреженной матрицы в Университете Флориды: https://www.cise.ufl.edu/research/sparse/