Решение систем линейных алгебраических уравнений с редко заполненной матрицей коэффициентов при неизвестных для задач ГИС транспорта

Современное развитие транспортной инфраструктуры тесно связано с географическими информационными системами. Такие системы содержат около 80 % всей информации о распределенных в пространстве объектах [4]. Благодаря этим системам, их ценность использования на транспорте является неоспоримым преимуществом в конкурентной борьбе среди государственных и коммерческих компаний, осуществляющих грузовые и пассажирские перевозки, за счет того, что удается оперативно решать различные транспортные задачи, связанные с планированием и оптимизацией маршрута следования. С учетом стремительно нарастающего объема данных в ГИС обработка таких данных требует все больше вычислительных ресурсов и объемов памяти. Не всегда и не у всех компаний имеется возможность бесконечного наращивания вычислительных мощностей.

С учетом перехода многих организаций на работу с мобильными приложениями задача с быстрой обработкой больших данных при работе с ГИС становится часто трудновыполнимой.

Большинство решаемых задач в ГИС характеризуется тем, что число используемых элементов во многих случаях не связано непосредственно друг с другом, из-за чего в матричных уравнениях, описывающих такие задачи, будет большое число нулевых элементов. Учет слабой заполненности матрицы коэффициентов при неизвестных дает возможность значительно сократить время решения и повысить порядок системы уравнений, к которой сводится реальная задача [3].

Постановка задачи

Огромные разрежённые матрицы часто возникают при решении таких задач, как дифференциальное уравнение в част ных производных.

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

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

Решение задачи

Разработанный программный комплекс реализует численный алгоритм, известный как метод Холесского, – симметричный вариант Гауссова исключения. Используются упорядочение минимальной степени [1], компактная схема хранения [2] и символическое разложение.

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

Для формирования структуры исходных данных (структуры смежности) понадобится таблица связей графа (см. таблицу).

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

Таблица – Связи графа

Рисунок 2 – Структура смежности

Прочерк в таблице показывает на отсутствие связи между узлами. Окончательный вид исходных данных представлен на рисунке 2.

В процессе разложения по схеме Хо-лесского исходная матрица «А» представляется в виде: A=LLT, где: L – нижняя треугольная матрица, LT – транспортированная матрица «L». Матрица разложения

«L» всегда содержит большее число ненулевых элементов, чем исходная матрица «А». Для того чтобы уменьшить возникающее во время разложения заполнение матрицы «L», применяется алгоритм минимальной степени Rose [1].

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

Хотя алгоритм минимальной степени и дает возможность свести к минимуму заполнение матрицы «L», он не позволяет заранее оценить требуемый объем памяти для ее хранения. Чтобы преодолеть эти трудности, в комплекс включена процедура символического разложения, позволяющая получить точную структуру нулевых и ненулевых элементов матрицы «L». Результат символического разложения исходной матрицы «А» с учетом вектора перестановок (1) представлен на рисунке 3.

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

В процессе работы программного комплекса применяется схема данных Шермана [2] (рисунок 4), предусматривающая хранение только логически ненулевых элементов факторизуемой матрицы.

Рисунок 3 – Исходная матрица и ее разложение

Массив	до разложения	ал	агг	азз	344	азз	Эбб	877
диагональных -
элементов	после	111	I22	hi	I44	hs	Ьб	Ь?
Массив логически
	до разложения	321	341	0	а5з	363	а54	0	375	а76
ненулевых элементов
	после	hi	hi	I42	Ьз		I54	1бЗ	1?5	*76

Массив начала ненулевых элементов каждого столбца

Массив строчных индексов ненулевых элементов

Массив начала строчных индексов ненулевых элементов

Рисунок 4 – Схема хранения данных

Следом за символическим разложением вызываются подпрограммы, выполняющие численное разложение системы линейных уравнений, которая хранится компактной схемой. Используется алгоритм разложения в форме скалярных произведений, адаптированной к способу хранения ненулевых элементов нижнего треугольника матрицы «А» по столбцам. После численного разложения решаются треугольные системы Ly=b и L^Tx=y. Для прямого хода используется форма внешних произведений. В обратной подстановке корни системы уравнений вычисляются посредством скалярных произведений. Эта схема позволяет использовать разреженность решения «х». Если в начале i-го шага b i оказывается равным нулю, то x i – тоже нуль. В этом случае весь шаг пропускается.