разделение

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

Синтаксис

p = dissect(A)
p = dissect(A,Name,Value)

Описание

пример

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)

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

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))

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

свернуть все

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

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

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

Укажите необязательные аргументы в виде пар ""имя, значение"", разделенных запятыми. Имя (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

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