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) позволяет дополнительные опции для переупорядочения. opts вход является структурой с этими двумя полями, показанными ниже. Только необходимо установить интересующие области:
плотный — неотрицательное скалярное значение, которое указывает на то, что считается плотным. Если 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')
