Вложенные сочетания рассечения
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 использование различных методов упорядоченного расположения. The 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], является многоуровневым алгоритмом графика, который используется для создания сокращающих заполнение упорядоченных расположений разреженных матриц. Матрица входа рассматривается как матрица смежности графика. Алгоритм сокращает график путем свертывания вершин и ребер, переупорядочивает меньший график, а затем использует шаги уточнения, чтобы отрегулировать маленький график и произвести переупорядочение исходного графика.
The пар "имя-значение" for dissect позволяет вам управлять различными этапами алгоритма:
Огрубление
На этой фазе алгоритм создает последовательно меньшие графики из исходного графика путем свертывания вместе соседних пар вершин. 'MaxDegreeThreshold' позволяет вам отфильтровать высоко связанные вершины графика (которые являются плотными столбцами в матрице), упорядочив их в последнюю очередь.
Разделение
После того, как график огрублен, алгоритм полностью переупорядочивает меньший график. На каждом шаге разбиения алгоритм пытается разбить график на равные части: 'NumSeparators' задает, на сколько частей разбить график на, 'VertexWeights' опционально присваивает веса вершинам и 'MaxImbalance' задает порог различия в весе между различными разделами.
Обработка
После того, как наименьший график переупорядочен, алгоритм делает проекции, чтобы увеличить график до исходного размера путем расширения вершин, которые были ранее объединены. После каждого шага проекции выполняется шаг уточнения, который перемещает вершины между разделами, чтобы улучшить качество решения. 'NumIterations' управляет тем, сколько шагов уточнения используется во время этой фазы разогрева.
[1] Karypis, George and Vipin Kumar. «Быстрая и высококачественная многоуровневая схема для разбиения неправильных графиков». SIAM Journal on Scientific Computing. Том 20, № 1, 1999, стр. 359-392.