symamd
Симметричное аппроксимированное минимальное сочетание степени
Синтаксис
p = symamd(S)
p = symamd(S,knobs)
[p,stats] = symamd(...)
Описание
p = symamd(S) для симметричного положительного определенного матричного S, возвращает вектор сочетания p таким образом, что S(p,p) имеет тенденцию иметь более разреженный Фактор Холесского, чем S. Найти упорядоченное расположение для Ssymamd создает матричный 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) | 0 |
stats(5) | Индекс крайнего правого столбца, который не отсортирован или содержит дублирующиеся записи или |
stats(6) | В последний раз замеченная дублирующаяся или неисправная строка индексирует в индексе столбца, данном |
stats(7) | Количество дублирующихся и неисправных индексов строки |
Несмотря на то, что, встроенные функции MATLAB® генерируют допустимые разреженные матрицы, пользователь может создать недопустимую разреженную матрицу с помощью API MATLAB C или Фортрана и передать ее symamd. Поэтому symamd проверяет тот S isvalid:
Если индекс строки появляется два или больше раза в том же столбце,
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/