Вложенная перестановка рассечения
p = dissect(A)p = dissect(A,Name,Value)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] Karypis, Джордж и Випин Кумар. "Быстрая и Высококачественная Многоуровневая Схема Разделения Неправильных Графиков". SIAM Journal на Научных вычислениях. Издание 20, Номер 1, 1999, стр 359–392.