amd
Приблизительное сочетание минимальной степени
Синтаксис
P = amd(A)
P = amd(A,opts)
Описание
P = amd(A) возвращает приблизительный вектор сочетания минимальной степени для разреженной матрицы C = A + A'. Область Факторизации Холесского C(P,P) или A(P,P) имеет тенденцию быть рассеяннее, чем у C или A. amd функция имеет тенденцию быть быстрее, чем symamd, а также имеет тенденцию возвращать лучшие упорядоченные расположения, чем symamd. Матричные A должен быть квадратным. Если A является полной матрицей, тогда amd(A) эквивалентно amd(sparse(A)).
P = amd(A,opts) позволяет дополнительные опции для переупорядочивания. The opts вход - структура с двумя полями, показанными ниже. Вам нужно задать только интересующие вас поля:
dense - неотрицательное скалярное значение, которое указывает на то, что считается плотным. Если A - n-на-n, то строки и столбцы с более чем
max(16,(dense*sqrt(n)))записи вA + A'считаются «плотными» и игнорируются во время упорядоченного расположения. MATLAB® программа помещает эти строки и столбцы в последнюю очередь в выход сочетания. Значение по умолчанию для этого поля равно 10.0, если эта опция отсутствует.агрессивный - скалярное значение, контролирующее агрессивное поглощение. Если это поле установлено на ненулевое значение, то выполняется агрессивное поглощение. Это значение по умолчанию, если эта опция отсутствует.
MATLAB выполняет поступорядоченное расположение дерева сборки, который обычно аналогичен поступорядоченному расположению дерева исключения. Он не всегда идентичен из-за применяемого апдейта приблизительной степени, и потому что «плотные» строки и столбцы не принимают участия в постпорядке. Он хорошо подходит для последующего chol операция, однако, если вам требуется точное дерево исключения после поступорядоченного расположения, вы можете использовать следующий код:
P = amd(S); C = spones(S)+spones(S'); [ignore, Q] = etree(C(P,P)); P = P(Q);
Если S уже симметричен, опускает вторую линию C = spones(S)+spones(S').
Примеры
Эффект предварительного упорядоченного расположения на разреженность факторов Холецкого
Вычислите Фактор Холецкого матрицы до и после того, как она будет упорядочена с помощью amd чтобы изучить эффект на разреженность.
Загрузите разреженную матрицу графика штанги и добавьте к ней разреженную единичную матрицу, чтобы убедиться, что она положительно определена. Вычислите два фактора Холецкого: один из исходной матрицы и один из исходной матрицы, предварительно упорядоченной с amd.
load barbellgraph.mat A = A+speye(size(A)); p = amd(A); L = chol(A,'lower'); Lp = chol(A(p,p),'lower');
Постройте график шаблонов разреженности всех четырех матриц. Фактор Холецкого, полученный из предварительно упорядоченной матрицы, намного более разрежен по сравнению с фактором матрицы в её естественном упорядоченном расположении.
figure subplot(2,2,1) spy(A) title('Original Matrix A') subplot(2,2,2) spy(A(p,p)) title('AMD ordered A') subplot(2,2,3) spy(L) title('Cholesky factor of A') subplot(2,2,4) spy(Lp) title('Cholesky factor of AMD ordered A')
