Аппроксимируйте минимальную перестановку градуса
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')
colamd | colperm | разделение | symamd | symrcm
