Документация

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

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

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

load west0479.mat
A = west0479;
S = A * 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));

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

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

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

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

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

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

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

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

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

Команда 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(3) = nnz(L);
xlabel(sprintf('Nonzeros = %d (%.2f%%)',nc(3),nc(3)*pct));

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

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

r = symamd(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));

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

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

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