Методы работы с разреженными матрицами произвольного вида. Глушакова Т.Н - 7 стр.

                                    7
   Чтобы избежать повторной записи одинаковых        последовательностей
столбцовых индексов, Шерман предложил компактную схему хранения этих
индексов, требующую дополнительного массива указателей. Диагональные
элементы U хранятся в массиве UD, а внедиагональные элементы по строкам
– в массиве UN. Массив IU содержит указатели для UN, определяемые
обычным образом. Столбцовые индексы, отвечающие находящимся в UN
ненулевым элементам, хранятся в JU в компактной форме. Теперь между UN
и JU нет прямого соответствия. Столбцовые индексы выбираются из JU с
помощью дополнительного массива указателей IJ. Несколько строк
описываются в JU одним и тем же набором столбцовых индексов. Численные
значения элементов i-ой строки находятся в UN в позициях от IU(i) до IU(i
+ 1) – 1, столбцовые индексы находятся в JU, начиная с позиции IJ(i).
Алгоритм исключения систематически порождает наборы строк, имеющих
одинаковую структуру справа от некоторого столбца, тем самым,
предоставляя непосредственно информацию, необходимую для построения
компактной схемы.

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

      1.6 О вычислительных затратах
     Занимаясь технологией разреженных матриц, важно знать объем
памяти, требуемой алгоритмом, и число операций, производимых при его
выполнении. При подсчете операций число делений включается в число
умножений, а число вычитаний – в число сложений. Сложения с нулями
также учитываются при подсчете сложений, а возможные взаимные
уничтожения ненулевых элементов не принимаются во внимание.
Результаты, получающиеся в некоторых случаях, приведены в таблицах 1 и
2.