symamd
Симметричная аппроксимированная минимальная перестановка степени
Синтаксис
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-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/