Алгоритм минимальной степени - Minimum degree algorithm

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

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

Учитывая линейную систему

${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }$

где А является ${\displaystyle n\times n}$ вещественная симметричная разреженная квадратная матрица фактор Холецкого L обычно страдает "заполнить", то есть иметь больше ненулевых, чем верхний треугольник А. Мы ищем матрица перестановок п, так что матрица${\displaystyle \mathbf {P} ^{T}\mathbf {A} \mathbf {P} }$, который также является симметричным, имеет наименьшее возможное заполнение его фактора Холецкого. Решаем переупорядоченную систему

${\displaystyle \left(\mathbf {P} ^{T}\mathbf {A} \mathbf {P} \right)\left(\mathbf {P} ^{T}\mathbf {x} \right)=\mathbf {P} ^{T}\mathbf {b} .}$

Проблема поиска наилучшего заказа - это НП-полный проблема и поэтому трудноразрешима, поэтому вместо нее используются эвристические методы. Алгоритм минимальной степени получен из метода, впервые предложенного Марковиц в 1959 г. для несимметричных линейное программирование проблемы, которые в общих чертах описываются следующим образом. На каждом этапе Гауссово исключение перестановки строк и столбцов выполняются таким образом, чтобы минимизировать количество недиагональных ненулевых значений в сводной строке и столбце. Симметричная версия метода Марковица была описана Тинни и Уокером в 1967 году, а Роуз позже вывел теоретико-графовую версию алгоритма, в которой факторизация только моделируется, и это было названо алгоритмом минимальной степени. Упомянутый граф - это граф с п вершины, с вершинами я и j связаны ребром, когда ${\displaystyle a_{ij}\neq 0}$, а степень - степень вершин. Важнейшим аспектом таких алгоритмов является стратегия разрешения конфликтов, когда есть выбор перенумерации, приводящей к той же степени.

Версия алгоритма минимальной степени была реализована в MATLAB функция symmmd (где MMD означает несколько минимальных степеней), но теперь заменено симметричной приближенной функцией множественных минимальных степеней симамд, что быстрее. Это подтверждается теоретическим анализом, который показывает, что для графиков на п вершины и м края, MMD имеет плотный верхняя граница из ${\displaystyle O(n^{2}m)}$ по времени работы, тогда как для AMD жесткие границы ${\displaystyle O(nm)}$ держит.

использованная литература

• Марковиц, Х. М. (1957). «Исключительная форма инверсии и ее применение в линейном программировании». Наука управления. 3 (3): 255–269. Дои:10.1287 / mnsc.3.3.255. JSTOR  2627454.
• Джордж, Алан; Лю, Джозеф (1989). «Эволюция алгоритма минимальной степени упорядочения». SIAM Обзор. 31 (1): 1–19. Дои:10.1137/1031001. JSTOR  2030845.
• Tinney, W. F .; Уокер, Дж. У. (1967). «Прямое решение уравнений разреженной сети с помощью оптимально упорядоченной треугольной факторизации». Proc. IEEE. 55 (11): 1801–1809. Дои:10.1109 / PROC.1967.6011.
• Роуз, Д. Дж. (1972). "Теоретико-графическое исследование численного решения разреженных положительно определенных систем линейных уравнений". В Риде, Р. К. (ред.). Теория графов и вычисления. Нью-Йорк: Academic Press. С. 183–217. ISBN  0-12-583850-6.
• Хеггернес, П.; Eisenstat, S.C .; Kumfert, G .; Потен, А. (декабрь 2001 г.), Вычислительная сложность алгоритма минимальной степени. (PDF) (Технический отчет), Институт компьютерных приложений в науке и технике