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). The 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)`	Количество плотных или пустых строк, проигнорированных `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^® встроенные функции генерируют действительные разреженные матрицы, пользователь может создать недопустимую разреженную матрицу с помощью MATLAB C или Фортран API и передать ее в symamd. По этой причине symamd проверяет, что S действителен:

Если индекс строки появляется в одном столбце два или более раз, symamd игнорирует повторяющиеся записи, продолжает обработку и предоставляет информацию о повторяющихся записях в stats(4:7).
Если индексы строк в столбце находятся вне порядка, symamd сортирует каждый столбец своей внутренней копии матрицы S (но не восстанавливает входную матрицу S), продолжает обработку и предоставляет информацию о неупорядоченных записях в stats(4:7).
Если S является недопустимым любым другим способом, symamd невозможно продолжить. Оно печатает сообщение об ошибке и не возвращает выходных аргументов (p или stats).

За упорядоченное расположение следует симметричное дерево исключения после поступорядоченного расположения.

Примеры

свернуть все

Сравнение обратный алгоритм Катхилла-Макки и минимальной степени

Открыть Live Script

Вот сравнение обратного алгоритма Катхилла-Макки и минимальной степени на примере мяча Баки, упомянутом в 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))')

Figure contains 4 axes. Axes 1 with title B(r,r) contains an object of type line. Axes 2 with title B(s,s) contains an object of type line. Axes 3 with title chol(B(r,r)) contains an object of type line. Axes 4 with title chol(B(s,s)) contains an object of type line.

Несмотря на то, что это очень маленькая проблема, поведение обоих упорядоченных расположений типично. RCM создает матрицу с узкой шириной полосы, которая заполняется почти полностью во время факторизации Холесского. Минимальная степень создает структуру с большими блоками смежных нулей, которые не заполняются во время факторизации. Следовательно, упорядоченное расположение минимальной степени требуется меньше времени и памяти для факторизации.

Ссылки

Авторы кода для symamd Стефан И. Ларимор и Тимоти А. Дэвис (davis@cise.ufl.edu), Флоридский университет. Алгоритм был разработан в сотрудничестве с John Gilbert, Xerox PARC, и Esmond Ng, Oak Ridge National Laboratory. Разреженные матрицы алгоритмов во Флоридском университете: https://www.cise.ufl.edu/research/sparse/

См. также

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

Документация