Алгоритм минимальной степени

редактировать

Алгоритм обработки матрицы

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

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

Для линейной системы

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

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

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

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

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

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

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

Ссылки

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