dissect
Вложенное сочетание рассечения
Описание
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.