Визуализация разреженной матрицы

A spy график показывает ненулевые элементы в матрице.

Это spy график показывает разреженную симметричную положительную определенную матрицу, полученную из части матрицы штанги. Эта матрица описывает связи в графике, который напоминает штангу.

load barbellgraph.mat
S = A + speye(size(A));
pct = 100 / numel(A);
spy(S)
title('A Sparse Symmetric Matrix')
nz = nnz(S);
xlabel(sprintf('Nonzeros = %d (%.3f%%)',nz,nz*pct));

Вот график графа штанг.

G = graph(S,'omitselfloops');
p = plot(G,'XData',xy(:,1),'YData',xy(:,2),'Marker','.');
axis equal

Вычисление фактора Холеского

Вычислить коэффициент Чолеского L, где S = L*L'. Обратите внимание, что L содержит гораздо больше ненулевых элементов, чем неакторированный S, потому что вычисление факторизации Холеского создает заполнение ненулевых значений. Эти значения заполнения замедляют алгоритм и увеличивают затраты на хранение.

L = chol(S,'lower');
spy(L)
title('Cholesky Decomposition of S')
nc(1) = nnz(L);
xlabel(sprintf('Nonzeros = %d (%.2f%%)',nc(1),nc(1)*pct));

Изменение порядка для ускорения вычислений

Переупорядочивая строки и столбцы матрицы, можно уменьшить объем заполнения, который создает факторизация, тем самым уменьшая время и затраты на хранение последующих вычислений.

Несколько различных переупорядочений, поддерживаемых MATLAB ®:

Проверьте влияние этих разреженных переупорядочений матрицы на матрицу штанги.

Переупорядочивание количества столбцов

colperm команда использует алгоритм переупорядочения количества столбцов для перемещения строк и столбцов с более высоким ненулевым числом к концу матрицы.

q = colperm(S);
spy(S(q,q))
title('S(q,q) After Column Count Ordering')
nz = nnz(S);
xlabel(sprintf('Nonzeros = %d (%.3f%%)',nz,nz*pct));

Для этой матрицы упорядочение количества столбцов едва может сократить время и объем хранения для факторизации Cholesky.

L = chol(S(q,q),'lower');
spy(L)
title('chol(S(q,q)) After Column Count Ordering')
nc(2) = nnz(L);
xlabel(sprintf('Nonzeros = %d (%.2f%%)',nc(2),nc(2)*pct));

Обратное изменение порядка Катилла-МакКи

symrcm команда использует алгоритм обратного переупорядочивания Катилла-Макки для перемещения всех ненулевых элементов ближе к диагонали, уменьшая полосу пропускания исходной матрицы.

d = symrcm(S);
spy(S(d,d))
title('S(d,d) After Cuthill-McKee Ordering')
nz = nnz(S);
xlabel(sprintf('Nonzeros = %d (%.3f%%)',nz,nz*pct));

Заполнение, производимое факторизацией Холеского, ограничивается полосой, поэтому факторизация переупорядоченной матрицы занимает меньше времени и меньше памяти.

L = chol(S(d,d),'lower');
spy(L)
title('chol(S(d,d)) After Cuthill-McKee Ordering')
nc(3) = nnz(L);
xlabel(sprintf('Nonzeros = %d (%.2f%%)', nc(3),nc(3)*pct));

Изменение порядка минимальной степени

amd команда использует алгоритм аппроксимации минимальной степени (мощный графо-теоретический метод) для получения больших блоков нулей в матрице.

r = amd(S);
spy(S(r,r))
title('S(r,r) After Minimum Degree Ordering')
nz = nnz(S);
xlabel(sprintf('Nonzeros = %d (%.3f%%)',nz,nz*pct));

Факторизация Холеского сохраняет блоки нулей, производимые алгоритмом минимальной степени. Эта структура позволяет значительно сократить время и затраты на хранение.

L = chol(S(r,r),'lower');
spy(L)
title('chol(S(r,r)) After Minimum Degree Ordering')
nc(4) = nnz(L);
xlabel(sprintf('Nonzeros = %d (%.2f%%)',nc(4),nc(4)*pct));

Перестановка вложенного рассечения

dissect функция использует теоретические методы построения порядка заполнения. Алгоритм рассматривает матрицу как матрицу смежности графа, укрупняет граф путем сворачивания вершин и рёбер, переупорядочивает меньший граф, а затем использует шаги уточнения, чтобы отменить укрупнение малого графа и произвести переупорядочение исходного графа. В результате получается мощный алгоритм, который часто производит наименьший объем заполнения по сравнению с другими алгоритмами переупорядочивания.

p = dissect(S);
spy(S(p,p))
title('S(p,p) After Nested Dissection Ordering')
nz = nnz(S);
xlabel(sprintf('Nonzeros = %d (%.3f%%)',nz,nz*pct));

Аналогично минимальной степени упорядочения, факторизация Холеского вложенного порядка рассечения в основном сохраняет ненулевую структуру S(d,d) ниже главной диагонали.

L = chol(S(p,p),'lower');
spy(L)
title('chol(S(p,p)) After Nested Dissection Ordering')
nc(5) = nnz(L);
xlabel(sprintf('Nonzeros = %d (%.2f%%)',nc(5),nc(5)*pct));

Подведение итогов

Эта гистограмма суммирует эффекты переупорядочивания матрицы перед выполнением факторизации Холеского. В то время как факторизация Холеского исходной матрицы имела около 8% её элементов как ненулевых, используя dissect или symamd уменьшает эту плотность до менее 1%.

labels = {'Original','Column Count','Cuthill-McKee',...
    'Min Degree','Nested Dissection'};
bar(nc*pct)
title('Nonzeros After Cholesky Factorization')
ylabel('Percent');
ax = gca;
ax.XTickLabel = labels;
ax.XTickLabelRotation = -45;