5. Технология разреженных матриц

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

Рассмотрим решение линейной САУ

, (5.1)

где А - матрица размера ; x -n- мерный вектор неизвест­ных; b -n-мерный заданный вектор. Как уже упоминалось ранее, мно­гие экономические задачи имеют высокую мерность и слабую заполнен­ность матрицы А . Метод Гаусса требует примерно ячеек памяти ЭВМ и длинных операций (умножения и деления) для однократ­ного решения системы (5.1), что для является уже проблемой даже для современных больших ЭВМ [9]. Выходом является учет разреженности матрицы A . Методы, позволяющие решить систему (5.1) в названной ситуации, называются методами разреженных матриц. Основные требования к этим методам:

1) хранить только ненулевые элементы (ННЭ) матрицы;

2) в процессе решения принимать меры, уменьшающие возможность появления новых ННЭ;

3) вычисления производить только с ННЭ.

Первая и третья проблемы решаются довольно просто: существуют специальные методы хранения и модификации известных методов Гаусса для разреженных матриц. Что касается второй задачи, то ее решение значительно сложнее: для уменьшения числа новых ННЭ нужна перегруппировка (упорядочение) строк и столбцов матрицы A Возможны такие перестановки, когда новые ННЭ в процессе решения; не появляются совсем. Для получения строго оптимального упорядо­чения необходимо вариантов расстановок строк и столбцов, что практически невыполнимо. Существуют квазиоптимальные алгоритмы, но тем не менее эта проблема достаточно сложна и здесь обсуждать­ся не будет.

Опыт работы с разреженными машинами показал, что затраты времени и памяти ЭВМ зависят линейно от числа уравнений n , а количество длинных операций приблизительно равно (10-20)n . От­метим также, что эффект от применения разреженных матриц зависит от степени их разреженности и практически не рекомендуется приме­нять эти методы для n < 50.

Материал, обсуждаемый далее, описан в [9].

5.2. Разреженный строчный формат

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

Значения ненулевых элементов и соответствующие столбцевые ин­дексы хранятся по строкам в двух массивах: NA и JA . Для раз­метки в этих массивах строк используется массив указателей (IA ), отмечающих позиции массивов AN и JA , c которых начинается описание очередной строки. Последняя цифра в массиве IA содержит указатель первой свободной позиции в JA и AN . Рассмотрим пример.

Для этой матрицы общее количество ННЭ =5. Заполненность матрицы оценивается коэффициентом заполнения . A в разреженном строчном формате представляется

Следующим образом

RR(c) 0

Таким образом, в нашем примере:

IA(1)=1, первая-строка начинается с JA(1) и AN(1)

IA(2)=4, вторая-строка начинается с JA(4) и AN(4)

IA(3)=4, третья-строка начинается с JA(4) и AN(4)

Так как это те же позиции, с которых начинается 2-я строка, это значит, что 2-я строка пуста,

IA=6 , это первая свободная позиция в JA и AN .

Данный способ представления называется полным (так как представлена вся матрица А) и упорядоченным (так как элементы каж­дой строки хранятся в соответствии с возрастанием столбцевых ин­дексов), обозначается RR(c)0-wise Representation Complete and Ordered(англ.) .

Массивы IA и JA представляют портрет матрицы A. Если в алгоритме разграничены этапы символической и численной обработки, то массивы IA и JA заполняются на первом этапе, а массив AN - на втором.

Следует заметить, что результаты большинства матричных опера­ций получаются неупорядоченными и (алгоритмы разреженных матриц не требуют, чтобы представление было упорядочено. В связи о этим матрицу А можно представить и в неупорядоченном виде:

RR(c)U (Unordered)

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

СR(c)O (Column-wisl)

Если заданная матрица симметрична, достаточно хранить лишь ее диагональ и верхний треугольник. Например:

RR(DU)O DU-Diagonal and Uper

Если большинство диагональных элементов отличны от нуля, то они могут храниться отдельно в массиве BD , а разреженным форматом представляется только верхний треугольник B:

RR(U)U

Это очень плотное и удобное представление.