Универсальные разреженные методы (стр. 5 )

2. Построение графа. Матрица рассматривается как ассоциированная с некоторым графом.

3. Для построенного графа строиться последовательность графов исключения. Это позволяет проанализировать заполнение множителя Холецкого для исходной матрицы.

4. Далее, для той же исходной матрицы последовательность графов исключения строится c использование алгоритма минимальной степени. На основании порядка удаления вершин, строится матрица перестановки P.

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

4.6 Пример исследования заполнения матрицы

В качестве примера для исследования была выбрана матрица со следующей структурой

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

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

Для такой матрицы структура множителя Холецкого будет иметь вид

Как можно отметить, явления заполнения не произошло. Однако, такое бывает нечасто. В приложении к данной работе можно найти еще несколько примеров матриц, для которых был произведен подобный анализ.

Стоит сказать, что такой графовый подход позволяет легко и просто спрогнозировать поведение явления заполнения для некоторых графов специального вида.

4.7 Явление заполнения в матрицах с графами - деревьями

Дерево – это неориетированный связный граф без петель, не содержащий циклических ребер.[ Теория графов. — 2-е изд. — М.: Наука, 1980. — 336 с.]. Дерево всегда имеет вершины, степень которых равна 1. Более того, граф исключения, полученных из дерева путем удаления подобной вершины вместе с инцидентным ему ребром так же является деревом. Это свойство позволяет сформулировать следующее предложение.

Предложение. Если неразмеченный граф G, ассоциированный с некой симметричной положительно-определенной матрицей A является деревом, тогда существует как минимум одна разметка такого графа, при котором в множителе Холецкого для матрицы A множество элементов заполнения будет пустым. То есть явление заполнения не проявится.

Доказательство. Доказательство естественным образом вытекает из алгоритма минимальной степени. Действительно, в дереве всегда есть вершина, степень которой равна 1. Такая вершина называется листом дерева. То есть, при использовании алгоритма минимальной степени получится, что всегда будет выбираться именно такая вершина. Следовательно, так как ее степень равна 1, то с ней смежна тоже только одна вершина. Значит, в графе исключения не будет происходить добавление новых ребер.

4.8 Явление заполнения в матрицах с графами специального вида

Допустим, имеется граф, у которого выполняются следующие условия

1.  У графа есть как минимум одна вершина, смежная с остальными

2.  Степень остальных вершин равна 2

Пример такого графа изображен на иллюстрации.

Рис 3. Пример графа, удовлетворяющий рассматриваемым условиям. Случай с двумя вершинами

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

Рис 4. Структура матрицы, ассоциированная с графом

Предложение. Для матрицы, ассоциированной с графом, у которого

1.  Есть вершина как минимум одна вершина, смежная с остальными

2.  Степень остальных вершин равна 2

может быть найдена перестановка, которая нейтрализует явление заполнения

Доказательство. Не теряя общности, будем рассматривать случай, когда есть всего одна вершина, смежная со всеми остальными. Обозначим такую вершину v.

Доказательство будем производить на основании применения алгоритма минимальной степени. В самом деле, для такого графа очевидно, что степень вершины v будет максимальной. Таким образом, кандидатами для удаления в алгоритме минимальной степени будут все остальные вершины, а потом уж и v.

Допустим, на определенном шаге алгоритма удаляется вершина , которая, по предположению, смежна с v и какой-либо . В таком случае, исходя из правила построения графов исключения, необходимо добавить ребро, чтобы вершины, смежные с удаляемой, стали смежными между собой. Однако такое ребро уже есть, так как v смежна со всеми остальными вершинами графа. Таким образом, получается, что в процессе работы алгоритма будут удалены все вершины, причем при удалении каждой не будет происходить добавления новых ребер.

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

4.9 Экспериментальный анализ

Предложения, доказанные ранее, показывают, что в случае произвольных матриц можно избежать явление заполнения. Однако в достаточно большом количестве частных случаев для решения системы с разреженной матрицей специального вида можно подобрать другие методы решения, нежели метод декомпозиции Холецкого. В другом классе задач, структура матрицы если и будет известна, то может не иметь очевидного закона распределения нулевых и ненулевых элементов. Для таких случаев естественно возникает вопрос: насколько оправдано применение алгоритма минимальной степени? В самом деле, если экономия памяти будет незначительная, то тогда нет смысла искать перестановку P, которая должна уменьшить эффект заполнения. Чтобы ответить на это вопрос, был поставлен численный эксперимент.

Коэффициентом заполнения матрицы будем называть отношение количества ненулевых элементов матрицы к общему количеству элементов. Обозначать коэффициент заполнения будем буквой . В эксперименте генерировались матрицы разного размера с разным коэффициентом заполнения. Далее, для таких матриц вычислялись следующие величины:

1. Отношение количества элементов множества заполнения к количеству изначально нулевых элементов множителя Холецкого.

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

Обозначим их как и соответственно. Эти величины можно трактовать как процентное выражение «экономии» нулевых элементов во время явления заполнения в множителе Холецкого. Если оно равно 1, то можно говорить, что произошло полное заполнение нулевых элементов множителя Холецкого ненулевыми. Если оно равно нулю, то явление заполнения не наблюдается. Эксперимент проводился при помощи программы, которая упоминалась ранее и которая была предназначена для анализа эффекта заполнения в случае матрицы, заданной собственной структурой.

4.10 Численный эксперимент

Результатом численного эксперимента будет график зависимости и , а так же в виде отдельного графика – разница между этими двумя функциями, которая позволит наглядно увидеть степень «экономии» нулевых элементов. Здесь . Параметры для численного эксперимента, которые применялись при моделировании:

1.  N – размер матрицы

2.  – размер интервала разбиения

3.  k – количество повторений эксперимента для каждого значения коэффициента заполнения матрицы

Рис 5. Результаты для N=50, = 0.025, k=10

Рис 6. Результаты для N=200, = 0.025, k=10

Рис 6. Результаты для N=500, = 0.025, k=10

ЗАКЛЮЧЕНИЕ

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

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