Переупорядочение разреженной матрицы

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

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

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

Figure contains an axes. The axes with title A Sparse Symmetric Matrix contains an object of type line.

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

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

Figure contains an axes. The axes contains an object of type graphplot.

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

Вычислите Фактор Холецкого 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));

Figure contains an axes. The axes with title Cholesky Decomposition of S contains an object of type line.

Переупорядочение, чтобы ускорить вычисление

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

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

  • colperm: Количество столбцов

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

  • amd: Минимальная степень

  • dissect: Вложенное рассечение

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

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

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

Figure contains an axes. The axes with title S(q,q) After Column Count Ordering contains an object of type line.

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

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

Figure contains an axes. The axes with title chol(S(q,q)) After Column Count Ordering contains an object of type line.

Переупорядочение обратного алгоритма Катхилла-Макки

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

Figure contains an axes. The axes with title S(d,d) After Cuthill-McKee Ordering contains an object of type line.

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

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

Figure contains an axes. The axes with title chol(S(d,d)) After Cuthill-McKee Ordering contains an object of type line.

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

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

Figure contains an axes. The axes with title S(r,r) After Minimum Degree Ordering contains an object of type line.

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

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

Figure contains an axes. The axes with title chol(S(r,r)) After Minimum Degree Ordering contains an object of type line.

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

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

Figure contains an axes. The axes with title S(p,p) After Nested Dissection Ordering contains an object of type line.

Подобно минимальному упорядоченному расположению степени факторизация Холесского вложенного рассечения, заказывающего в основном, сохраняет ненулевую структуру 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));

Figure contains an axes. The axes with title chol(S(p,p)) After Nested Dissection Ordering contains an object of type line.

Суммирование результатов

Эта столбчатая диаграмма обобщает эффекты переупорядочения матрицы прежде, чем выполнить факторизацию Холесского. В то время как факторизация Холесского исходной матрицы имела приблизительно 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;

Figure contains an axes. The axes with title Nonzeros After Cholesky Factorization contains an object of type bar.

Смотрите также

| | | | |

Для просмотра документации необходимо авторизоваться на сайте