dissect

Вложенное сочетание рассечения

Описание

пример

p = dissect(A) возвращает вектор сочетания, вычисленный с помощью вложенного рассечения структуры разреженности A.

пример

p = dissect(A,Name,Value) задает дополнительные опции с помощью одного или нескольких аргументов пары "имя-значение". Например, dissect(A,'NumIterations',15) использование 15 итераций улучшения во вложенном алгоритме рассечения вместо 10.

Примеры

свернуть все

Переупорядочьте разреженную матрицу с несколькими методами и сравните временную замену, понесенную LU-разложением переупорядоченных матриц.

Загрузите west0479 матрица, которая является с действительным знаком 479 479 разреженная матрица и с действительными и с комплексными парами сопряженных собственных значений. Просмотрите структуру разреженности.

load west0479.mat
A = west0479;
spy(A)

Figure contains an axes. The axes contains an object of type line.

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

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 contains 2 axes. Axes 1 with title Original Matrix contains an object of type line. Axes 2 with title LU Decomposition contains an object of type line.

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 contains 2 axes. Axes 1 with title Reverse Cuthill-McKee contains an object of type line. Axes 2 with title LU Decomposition contains an object of type line.

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 contains 2 axes. Axes 1 with title Approximate Minimum Degree contains an object of type line. Axes 2 with title LU Decomposition contains an object of type line.

figure
subplot(1,2,1)
spy(A(p1,p1))
title('Nested Dissection')
subplot(1,2,2)
spy(lu(A(p1,p1)))
title('LU Decomposition')

Figure contains 2 axes. Axes 1 with title Nested Dissection contains an object of type line. Axes 2 with title LU Decomposition contains an object of type line.

Матрица в виде стрелки является разреженной матрицей, которая имеет несколько плотных столбцов. Используйте '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)

Figure contains an axes. The axes contains an object of type line.

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

p = dissect(A,'MaxDegreeThreshold',10);

Просмотрите шаблон разреженности переупорядоченной матрицы. dissect помещает плотные столбцы в конце переупорядоченной матрицы.

spy(A(p,p))

Figure contains an axes. The axes contains an object of type line.

Входные параметры

свернуть все

Введите матрицу в виде квадратной матрицы. A может быть или полным или разреженным. Если A несимметрично, затем dissect симметрирует его.

Типы данных: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64 | logical
Поддержка комплексного числа: Да

Аргументы в виде пар имя-значение

Задайте дополнительные разделенные запятой пары Name,Value аргументы. Name имя аргумента и Value соответствующее значение. Name должен появиться в кавычках. Вы можете задать несколько аргументов в виде пар имен и значений в любом порядке, например: Name1, Value1, ..., NameN, ValueN.

Пример: p = dissect(A,'NumIterations',15,'NumSeparators',2) использование 15 итераций улучшения и 2 диафрагмы во вложенном алгоритме рассечения.

Веса вершины в виде разделенной запятой пары, состоящей из 'VertexWeights' и вектор. Вектор из весов должен иметь длину, равную size(A,1) так, чтобы вес был задан для каждой вершины. Используйте эту опцию, чтобы задать, как вершины графика (столбцы матрицы) взвешиваются, который влияет, как алгоритм вычисляет баланс между разделами.

По умолчанию, вложенные веса алгоритма рассечения все вершины одинаково.

Типы данных: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

Количество диафрагм в виде разделенной запятой пары, состоящей из 'NumSeparators' и положительное целое число. Используйте эту опцию, чтобы задать, в какое количество разделов график разделен во время каждого шага разделения. Увеличение числа диафрагм во вложенном алгоритме рассечения может привести к более высокому качественному сочетанию за счет дополнительного времени выполнения.

Типы данных: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

Количество итераций улучшения в виде разделенной запятой пары, состоящей из 'NumIterations' и положительное целое число. Больше итераций улучшения может привести к более высокому качественному сочетанию за счет увеличенного времени выполнения.

Типы данных: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

Порог для неустойчивости раздела в виде разделенной запятой пары, состоящей из 'MaxImbalance' и скалярное значение, которое является целочисленным кратным 0.001 больше, чем или равный 1.001 и меньше чем или равный 1.999. Большие пороговые значения могут уменьшать время выполнения, позволяя алгоритму принять худшее сочетание.

Типы данных: single | double

Порог для степени вершины в виде разделенной запятой пары, состоящей из 'MaxDegreeThreshold' и неотрицательное целое число. Вложенный алгоритм рассечения игнорирует вершины со степенью, больше, чем threshold*(avg degree)/10 во время упорядоченного расположения. dissect вершины мест, проигнорированные таким образом в конце сочетания. Это эффективно помещает любые вершины со степенью, больше, чем порог в первой, диафрагме верхнего уровня. Отфильтровывание высоко соединенных вершин может иногда улучшать скорость и точность упорядоченного расположения.

Значение по умолчанию 0 средние значения, которые упорядочены все вершины.

Типы данных: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

Выходные аргументы

свернуть все

Вектор сочетания, возвращенный как вектор. Используйте вектор сочетания, чтобы переупорядочить столбцы A использование выражения индексации A(p,p). Например, факторизация Холесского chol(A(p,p)) имеет тенденцию быть более разреженным, чем тот из A.

Алгоритмы

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

Пары "имя-значение" для dissect позвольте вам управлять различными этапами алгоритма:

  • Огрубление

    В этой фазе алгоритм создает последовательно меньшие графики из исходного графика путем сворачивания вместе смежных пар вершин. 'MaxDegreeThreshold' позволяет вам отфильтровать вершины очень связного графа (которые являются плотными столбцами в матрице) путем упорядоченного расположения им в последний раз.

  • Разделение

    После того, как график огрубляется, алгоритм полностью переупорядочивает меньший график. На каждом шаге разделения алгоритм пытается разделить график в равные части: 'NumSeparators' задает сколько частей, чтобы разделить график в, 'VertexWeights' опционально веса присвоений к вершинам и 'MaxImbalance' задает порог для различия в весе между различными разделами.

  • Улучшение

    После того, как наименьший график переупорядочивается, алгоритм делает проекции, чтобы увеличить график назад к первоначальному размеру путем расширения вершин, которые были ранее объединены. После каждого шага проекции шаг улучшения выполняется что вершины перемещений между разделами, чтобы улучшить качество решения. 'NumIterations' средства управления, сколько шагов улучшения используется во время этой фазы неогрубления.

Ссылки

[1] Karypis, Джордж и Випин Кумар. "Быстрая и Высококачественная Многоуровневая Схема Разделения Неправильных Графиков". SIAM Journal на Научных вычислениях. Издание 20, Номер 1, 1999, стр 359–392.

Введенный в R2017b
Для просмотра документации необходимо авторизоваться на сайте