Спросить
Войти
х™™™™ ИНФОРМАЦИОННЫЕ СИСТЕМЫ И ТЕХНОЛОГИИ Х™™™™
УДК 004:656 Р.А. Ешенко,
канд. техн. наук, доцент кафедры информационных технологий и систем Дальневосточного государственного университета путей сообщения
Г.А. Гурвиц,
канд. техн. наук, доцент кафедры информационных технологий и систем Дальневосточного государственного университета путей сообщения
РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ С РЕДКО ЗАПОЛНЕННОЙ МАТРИЦЕЙ КОЭФФИЦИЕНТОВ ПРИ НЕИЗВЕСТНЫХ ДЛЯ ЗАДАЧ ГИС ТРАНСПОРТА
Описана оптимизация комплекса программ для персонального компьютера по решению линейных систем с симметричными, положительно определенными матрицами. Системы предполагаются разряженными. Задействована максимально доступная оперативная память. Максимально используется разреженность матрицы коэффициентов при неизвестных.
Optimization of a complex of programs for a personal computer by solving linear systems with symmetric, positive definite matrices is described. Systems are assumed to be discharged. The maximum available RAM and the maximum of the sparsity of the coefficient matrix at indeterminate are used.
Введение
Современное развитие транспортной инфраструктуры тесно связано с географическими информационными системами. Такие системы содержат около 80 % всей информации о распределенных в пространстве объектах [4]. Благодаря этим системам, их ценность использования на транспорте является неоспоримым преимуществом в конкурентной борьбе среди государственных и коммерческих компаний, осуществляющих грузовые и пассажирские перевозки, за счет того, что удается оперативно решать различные
транспортные задачи, связанные с планированием и оптимизацией маршрута следования. С учетом стремительно нарастающего объема данных в ГИС обработка таких данных требует все больше вычислительных ресурсов и объемов памяти. Не всегда и не у всех компаний имеется возможность бесконечного наращивания вычислительных мощностей.
С учетом перехода многих организаций на работу с мобильными приложениями задача с быстрой обработкой больших данных при работе с ГИС становится часто трудновыполнимой.
Большинство решаемых задач в ГИС характеризуется тем, что число используемых элементов во многих случаях не связано непосредственно друг с другом, из-за чего в матричных уравнениях, описывающих такие задачи, будет большое число нулевых элементов. Учет слабой заполненности матрицы коэффициентов при неизвестных дает возможность значительно сократить время решения и повысить порядок системы уравнений, к которой сводится реальная задача [3].
Постановка задачи
Огромные разрежённые матрицы часто возникают при решении таких задач, как дифференциальное уравнение в частных производных.
При хранении и преобразовании разреженных матриц в компьютере бывает полезно, а часто и необходимо использовать специальные алгоритмы и структуры данных, которые учитывают разреженную структуру матрицы. Операции и алгоритмы, применяемые для работы с обычными, плотными матрицами, применительно к большим разреженным матрицам работают относительно медленно и требуют значительных объемов памяти. Однако разреженные матрицы могут быть легко сжаты путем записи только своих ненулевых элементов, что снижает требования к компьютерной памяти [5].
Многие алгоритмы, тривиальные для случая плотных матриц, в разреженном случае требуют более тщательного подхода. Во многих алгоритмах обработки
разреженных матриц можно выделить два этапа - символический и численный. На символическом этапе формируется портрет результирующей матрицы (то есть определяются места ненулевых элементов в структуре матрицы), на численном этапе определяются значения ненулевых элементов результирующей матрицы. Для обработки разреженных матриц в данной работе будет рассмотрен соответствующий алгоритм.
Решение задачи
Разработанный программный комплекс реализует численный алгоритм, известный как метод Холесского, - симметричный вариант Гауссова исключения. Используются упорядочение минимальной степени [1], компактная схема хранения [2] и символическое разложение.
Среди других методов, используемых для работы с разреженными матрицами, метод Холесского показал свою наибольшую эффективность. Исходная матрица коэффициентов представляется в виде двух массивов, первый содержит списки смежности, второй - указатели начала каждого списка. Такая структура появилась в результате машинного представления графа матрицы коэффициентов при неизвестных. На рисунке 1 показана исходная матрица системы уравнений и ее граф. Символ * обозначает ненулевой элемент матрицы. Пустые клетки - нули.
Для формирования структуры исходных данных (структуры смежности) понадобится таблица связей графа (см. таблицу).
Матрица Л
&-Is ^ > * *
* * -v ^ > *
* & \\ 0) *
* * S. J
Рисунок 1 - Матрица и ее помеченный граф
Таблица - Связи графа
Узел Его соседи
Прочерк в таблице показывает на отсутствие связи между узлами. Окончательный вид исходных данных представлен на рисунке 2.
В процессе разложения по схеме Хо-лесского исходная матрица «А» представляется в виде: Л=ЬЬТ, где: Ь - нижняя треугольная матрица, ЬТ - транспортированная матрица «Ь». Матрица разложения
«L» всегда содержит большее число ненулевых элементов, чем исходная матрица «А». Для того чтобы уменьшить возникающее во время разложения заполнение матрицы «L», применяется алгоритм минимальной степени Rose [1].
Главная идея алгоритма заключается в локальной минимизации заполнения и числа операций на каждом шаге исключения за счет выбора главного элемента в тех строке и столбце, которые обеспечивают внесение наименьшего числа ненулевых элементов в треугольные множители. Результатом работы процедур, реализующих алгоритм минимальной степени, является упорядочение исходного графа, которое хранится отдельным вектором. Для исходных данных из рисунка 1 этот вектор имеет вид:
Хотя алгоритм минимальной степени и дает возможность свести к минимуму заполнение матрицы «Ь», он не позволяет заранее оценить требуемый объем памяти для ее хранения. Чтобы преодолеть эти трудности, в комплекс включена процедура символического разложения, позволяющая получить точную структуру нулевых и ненулевых элементов матрицы «Ь». Результат символического разложения исходной матрицы «А» с учетом вектора перестановок (1) представлен на рисунке 3.
Нетрудно заметить, что в матрице «Ь», балгодаря применению алгоритма минимальной степени, получилось всего на два элемента больше, чем в исходной матрице. В случае обычного рзложения по Холесскому матрица «Ь» получается полностью заполненной.
В процессе работы программного комплекса применяется схема данных Шермана [2] (рисунок 4), предусматривающая хранение только логически ненулевых элементов факторизуемой матрицы.
Рисунок 3 - Исходная матрица и ее разложение
Массив диагональных элементов
после
а11 а22 а33 а44 а55 а66 а77
Массив логически ненулевых элементов
до разложения а21 а41 0 а53 а<о а54 0 а75 а76
после
Массив начала ненулевых элементов каждого столбца
Массив строчных индексов ненулевых элементов
Массив начала строчных индексов ненулевых элементов
Рисунок 4 - Схема хранения данных
Следом за символическим разложением вызываются подпрограммы, выполняющие численное разложение системы линейных уравнений, которая хранится компактной схемой. Используется алгоритм разложения в форме скалярных произведений, адаптированной к способу хранения ненулевых элементов нижнего треугольника матрицы «А» по столбцам. После численного разложения решаются треугольные системы Ly=b и LTx=y. Для прямого хода используется форма внешних произведений. В обратной подстановке корни системы уравнений вычисляются посредством скалярных произведений. Эта схема позволяет использовать разреженность решения «х». Если в начале ;-го шага Ь; оказывается равным нулю, то х; - тоже нуль. В этом случае весь шаг пропускается.
Список использованных источников
