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

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 ® поддерживает несколько различных изменений порядка:

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

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

The 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));

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

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

Обратный алгоритм Катхилла-Макки

The 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));

Переупорядочивание минимальной степени

The 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));

Вложенное интерсекционное сочетание

The 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;