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