Симметричная аппроксимированная минимальная перестановка градуса
p = symamd (S)
p = symamd (S, кнопки)
[p, статистика] = 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-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® генерируют допустимые разреженные матрицы, пользователь может создать недопустимую разреженную матрицу с помощью API MATLAB или Фортрана C и передать ее 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), Флоридский университет. Алгоритм был разработан в сотрудничестве с Джоном Гильбертом, Xerox PARC, и Эсмондом Ыном, Окриджской национальной лабораторией. Исследование Алгоритмов Разреженной матрицы во Флоридском университете: https://www.cise.ufl.edu/research/sparse/