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')
