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

Можно показать[Лю], что

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

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

2.4 Применение метода Холецкого к решению разреженных систем

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

Ее множитель Холецкого имеет вид

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

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

В исходной системе заменим переменные по правилу . Матрица такой перестановки имеет вид

Новая матрица системы приобретает вид

Множитель Холецкого для такой матрицы равен (с точностью до трех значащих цифр)

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

2.5 Задача перестановки

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

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

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

Следует отметить, что для матриц определенных структур, например, для матриц ленточного вида, существует оптимальный алгоритм поиска перестановки, минимизирующей заполнение множителя Холецкого. Однако, такого алгоритма для произвольной разреженной положительно-определенной симметричной матрицы не существует[Лю].

ГЛАВА 3. Теория графов и связь с матрицами

3.1 Некоторые сведения из теории графов

Для текущего исследования будет можно ограничиться рассмотрением неориентированных связных графов без петель.

Неориентированным графом называется упорядоченная пара , для которой выполняются следующие условия:

1. V – непустое множество. Элементы этого множества называют вершинами или узлами графа.

2. E – множество, элементами которого являются неупорядочены пары элементов множества V. Элементы множества E принято называть ребрами графа.

Говоря менее строго, граф – это математический объект, который представляет собой набор вершин (узлов) и ребер, соединяющими некоторые пары вершин. Будем говорить исключительно о конечных графах, то есть о таких, у которых множества вершин и ребер – счетные и конечные.

Две вершины графа называются соседними, если существует ребро, соединяющее их.

Два ребра называются смежными, если у них есть общая вершина.

3.2 Способы представления графа

Рассмотрим способы представления графа. Первый из них – естественный, изображение в виде чертежа. В случае такого изображения вершины графа представляются точками на плоскости. Если две некоторые вершины соединяет ребро, то на чертеже соответствующие точки соединяются линией. Чертеж графа позволяет наглядно показать его структуру.

Остальные способы – это способы представления графа в памяти компьютера.

Матрица смежности графа G c конечным числом вершин N­ – это квадратная матрица размера . В ней значение элемента равно числу ребер из вершины i в вершину j. Матрица смежности является одной из наиболее распространенных структур данных для хранения графов. Данная структура наиболее эффективна, когда в графе достаточно большое количество ребер, в противном же случае значительная часть памяти будет тратиться на хранение незначащих нулей для поддержания структуры матрицы.

Матрица инцидентности графа G c N вершинами и M ребрами – это матрица размером . В соответствие ребрам графа ставятся столбцы матрицы, вершинам – строки. В такой матрице элемент , когда вершина i является концевой вершиной ребра j. Если в графе количество ребер больше количества вершин (а такое встречается достаточно часто), то такой способ хранения является более ресурсоемким по сравнению с хранение графа в виде его матрицы смежности.

Последний способ хранения – хранение в виде списка смежности. Такая структура хорошо подходит для разреженных графов, но в некоторых случаях требует более трудозатратной обработки. Данную структуру данных можно представить в виде ассоциативного массива, то есть объекта, позволяющего хранить пары «ключ-значение». Ключом в таком массиве является имя вершины, значением – список вершин, соседних с данной.

3.3 Ассоциирование графов и матриц

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

Пусть A­ – квадратная матрица размера . Упорядоченный, или помеченный граф матрицы A – граф , у которого N вершин пронумерованы числами от 1 до N и тогда и только тогда, когда .

Рис 1. Матрица и ее помеченный граф

Если – произвольная матрица перестановки, то непомеченные графы матриц A и совпадают. Разница будет лишь в помечивании графов.[ Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. . — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4]. Таким образом, непомеченный граф матрицы представляет лишь ее структуру, без упоминания о каком-либо упорядочивании. То есть можно говорить, что задача отыскания необходимой перестановки матрицы A сводится к отысканию некоторого помечивания ее непомеченного графа.