Перестановка вложенного рассечения
p = dissect(A,Name,Value)dissect(A,'NumIterations',15) использует 15 итераций уточнения во вложенном алгоритме рассечения вместо 10.
Переупорядочить разреженную матрицу с помощью нескольких методов и сравнить заполнение, вызванное разложением LU переупорядоченных матриц.
Загрузить west0479 матрица, которая является вещественно-значимой 479 на 479 разреженной матрицей с вещественными и комплексными парами сопряженных собственных значений. Просмотрите структуру разреженности.
load west0479.mat
A = west0479;
spy(A)
Вычислите несколько различных перестановок столбцов матрицы, включая порядок вложенных рассечений.
p1 = dissect(A); p2 = amd(A); p3 = symrcm(A);
Сравнение структур разреженности разложения LU A с использованием различных методов упорядочения. dissect функция создает переупорядочение, которое влечет за собой наименьшее количество заполнения.
subplot(1,2,1) spy(A) title('Original Matrix') subplot(1,2,2) spy(lu(A)) title('LU Decomposition')
figure subplot(1,2,1) spy(A(p3,p3)) title('Reverse Cuthill-McKee') subplot(1,2,2) spy(lu(A(p3,p3))) title('LU Decomposition')
figure subplot(1,2,1) spy(A(p2,p2)) title('Approximate Minimum Degree') subplot(1,2,2) spy(lu(A(p2,p2))) title('LU Decomposition')
figure subplot(1,2,1) spy(A(p1,p1)) title('Nested Dissection') subplot(1,2,2) spy(lu(A(p1,p1))) title('LU Decomposition')
Матрица со стрелками - это разреженная матрица, имеющая несколько плотных столбцов. Используйте 'MaxDegreeThreshold' пара имя-значение для фильтрации плотных столбцов до конца переупорядоченной матрицы.
Создайте разреженную матрицу стрелок и просмотрите узор разреженности.
A = speye(100) + diag(ones(1,99),1) + diag(ones(1,98),2); A(1:5,:) = ones(5,100); A = A + A'; spy(A)
Вычислите порядок вложенных рассечений и отфильтровайте столбцы, имеющие более 10 ненулевых элементов.
p = dissect(A,'MaxDegreeThreshold',10);Просмотр шаблона разреженности переупорядоченной матрицы. dissect размещает плотные столбцы в конце переупорядоченной матрицы.
spy(A(p,p))
Алгоритм упорядочения вложенных рассечений, описанный в [1], представляет собой многоуровневый алгоритм разбиения графов, который используется для получения порядка уменьшения заполнения разреженных матриц. Входная матрица рассматривается как матрица смежности графа. Алгоритм укрупняет граф путем сворачивания вершин и рёбер, переупорядочивает меньший граф, а затем использует шаги уточнения, чтобы отменить укрупнение малого графа и произвести переупорядочение исходного графа.
Пары имя-значение для dissect позволяют управлять различными этапами алгоритма:
Огрубление
В этой фазе алгоритм создает последовательно меньшие графы из исходного графа путём сворачивания вместе смежных пар вершин. 'MaxDegreeThreshold' позволяет отфильтровать высоко связанные вершины графа (которые являются плотными столбцами в матрице), упорядочив их последними.
Разделение
После укрупнения графа алгоритм полностью переупорядочивает граф меньшего размера. На каждом шаге разбиения алгоритм пытается разбиить граф на равные части: 'NumSeparators' определяет количество частей для секционирования графика, 'VertexWeights' при необходимости назначает веса вершинам, и 'MaxImbalance' определяет порог для разницы в весе между различными разделами.
Обработка
После того, как наименьший граф переупорядочен, алгоритм делает проекции, чтобы увеличить граф обратно до исходного размера путем расширения вершин, которые были ранее объединены. После каждого шага проекции выполняется шаг уточнения, который перемещает вершины между секциями для улучшения качества решения. 'NumIterations' управляет количеством шагов уточнения, используемых в течение этой фазы выравнивания.
[1] Карыпис, Георгий и Випин Кумар. «Многоуровневая схема быстрого и высокого качества для разбиения нерегулярных графиков». Журнал SIAM по научным вычислениям. Том 20, номер 1, 1999, стр. 359-392.