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)

Количество плотных или пустых строк проигнорировано symamd

stats(2)

Количество плотных или пустых столбцов проигнорировано symamd

stats(3)

Количество сборок мусора, выполняемых на внутренней структуре данных, используется symamd (примерно размера   8.4*nnz(tril(S,-1)) + 9n целые числа

stats(4)

0 если матрица допустима, или 1 если недопустимый

stats(5)

Индекс крайнего правого столбца, который не отсортирован или содержит дублирующиеся записи или 0 если никакой такой столбец не существует

stats(6)

В последний раз замеченная дублирующаяся или неисправная строка индексирует в индексе столбца, данном stats(5), или 0 если никакой такой индекс строки не существует

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/

Смотрите также

| | | | |

Представлено до R2006a