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

Рис 2. Матрица после перестановки и ее помеченный граф

ГЛАВА 4. Графовая модель разложения Холецкого

4.1 Разложение Холецкого и соответствующие изменения в графе

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

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

В 1961 году Партер и Роуз установили соответствие между преобразованиями матриц и и преобразованиями в ассоциированных с ними графах. Будем обозначать графы для и как и и , узлы будем обозначать как . Здесь – поменчивание графа, индуцированное исходной матрицей A. Граф матрицы получается из графа матрицы путем следующих манипуляций:

1. Удаление из графа узла и всех инцидентных ему ребер

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

Графы, полученные таким образом, будем называть графами исключения. То есть, как показал Роуз, симметричное гауссово исключение можно рассматривать как итеративное построение последовательности графов исключения

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

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

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

4.2 Универсальные методы

Обозначим как Nonz(A) множество ненулевых элементов матрицы A, F(A) – множество элементов заполнения матрицы L. Здесь L­ – соответствующий множитель Холецкого для матрицы A.

Пусть A – заданная симметричная положительно-определенная матрица, а P­ – произвольная матрица перестановки. Очевидно, что количество ненулевых элементов в матрицах и совпадают, то есть . Тем не менее, тут возникает одно критически важное обстоятельство: различие для и может быть очень велико. Это было показано ранее, когда было продемонстрировано явление заполнения.

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

Для такой задачи не существует эффективного алгоритма решения в случае произвольной симметричной матрицы. Аналогичная задача для несимметричной матрицы очень трудна и принадлежит к классу NP-полных задач[Роуз 1975]. Поэтому для решения подобных задач прибегают к эвристическим алгоритмам, которые бы давали упорядочивание с приемлемо малой, но не обязательно минимальной степенью заполнения множителя Холецкого.

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

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

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

4.4 Основной алгоритм

Опишем алгоритм минимальной степени в терминах упорядочивания графа симметричной матрицы. Пусть – непомеченный граф.

1.  Инициализация, i:=1.

2.  Выбор минимальной степени. В графе исключения выбрать узел , имеющий в минимальную степень.

3.  Преобразование графа. Построить новый граф исключения , исключая из вершину .

4.  Цикл или остановка. . Если – тогда остановка. В противном случае – переход на шаг 2.

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

4.5 Практическая реализация для исследования

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

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