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

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

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

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

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

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

$\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 соединены ребром, когда $a_{ij}\neq 0$, а степень — это степень вершин. Важнейшим аспектом таких алгоритмов является стратегия разрешения конфликтов, когда есть выбор перенумерации, приводящей к одинаковой степени.

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

Ссылки

• Каммингс, Роберт; Фарбах, Мэтью; Фатехпурия, Анимеш (2021). «Быстрый алгоритм минимальной степени и сопоставление нижней границы». Материалы 32-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам : 724–734. arXiv : 1907.12119 . дои : 10.1137/1.9781611976465.45 . ISBN  978-1-61197-646-5 . S2CID   198968052 .
• Джордж, Алан; Лю, Джозеф (1989). «Эволюция алгоритма упорядочивания минимальной степени». Обзор СИАМ . 31 (1): 1–19. дои : 10.1137/1031001 . JSTOR   2030845 . ОСТИ   5686483 .
• Хеггернес, П .; Айзенштат, Южная Каролина; Кумферт, Г.; Потен, А. (2001), Вычислительная сложность алгоритма минимальной степени (PDF) (технический отчет), Институт компьютерных приложений в науке и технике
• Марковиц, HM (1957). «Форма исключения обратной и ее применение к линейному программированию» . Наука управления . 3 (3): 255–269. дои : 10.1287/mnsc.3.3.255 . JSTOR   2627454 . Архивировано из оригинала 24 сентября 2017 года.
• Роуз, диджей (1972). «Теоретико-графовое исследование численного решения разреженных положительно определенных систем линейных уравнений». Теория графов и вычисления . Академическая пресса. стр. 183–217. ISBN  0-12-583850-6 .
• Тинни, ВФ; Уокер, JW (1967). «Прямое решение уравнений разреженной сети путем оптимально упорядоченной треугольной факторизации». Учеб. ИИЭЭ . 55 (11): 1801–1809. дои : 10.1109/PROC.1967.6011 .