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 использование различных методов упорядоченного расположения. The 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], является многоуровневым алгоритмом графика, который используется для создания сокращающих заполнение упорядоченных расположений разреженных матриц. Матрица входа рассматривается как матрица смежности графика. Алгоритм сокращает график путем свертывания вершин и ребер, переупорядочивает меньший график, а затем использует шаги уточнения, чтобы отрегулировать маленький график и произвести переупорядочение исходного графика.

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

  • Огрубление

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

  • Разделение

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

  • Обработка

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

Ссылки

[1] Karypis, George and Vipin Kumar. «Быстрая и высококачественная многоуровневая схема для разбиения неправильных графиков». SIAM Journal on Scientific Computing. Том 20, № 1, 1999, стр. 359-392.

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