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

                                    5

      1. Схемы хранения
      Рассмотрим разреженную матрицу А. Ее ненулевые элементы, которых
очень мало в сравнении с числом нулей, рассеяны по всей матрице, образуя
то, что называют портретом матрицы или шаблоном нулей-ненулей. Все
способы хранения разреженных матриц заключаются в том, чтобы хранить
только ненулевые элементы матрицы или, может быть, небольшое
количество нулей вместе с ними.

      1.1 Схема Кнута
      Ненулевые элементы хранятся в компактной форме и произвольном
порядке в одномерном массиве AN. Информация о положении ненулевых
элементов может храниться двумя дополнительными параллельными
одномерными массивами I и J: здесь для каждого ненулевого элемента
содержатся его строчный и столбцовый индексы. Для каждого aij ≠ 0 в
памяти находится тройка (aij, i, j).
   Чтобы можно было легко отыскивать элементы произвольной строки или
столбца матрицы, необходимы еще пара указателей для каждой тройки, а
также указатели входа для строк и столбцов, сообщающие начало каждого
строчного или столбцового списка. Пусть NR – массив, хранящий строчные
указатели («следующий ненулевой элемент той же строки»), а NC – массив
столбцовых указателей («следующий ненулевой элемент того же столбца»).
Пять массивов AN, I, J, NR и NC имеют одинаковую длину, и их
одноименные позиции соответствуют друг другу. Пусть JR и JC – массивы,
содержащие указатели входа для строк и столбцов, расположенные в
соответствии с порядком строк и столбцов матрицы.
    При использовании данной схемы элемент aij можно найти, лишь входя в
список i-й строки и просматривая его до тех пор, пока не будет найден
столбцовый индекс j, либо то же самое с переменой ролей строки и столбца.
Обратная задача имеет очевидное решение: если задан номер позиции k
элемента AN(k), то его строчный и столбцовый индексы – I(k) и J(k).
   Схема Кнута требует пяти ячеек памяти для каждого ненулевого элемента
А плюс к этому указатели входа для строк и столбцов. Вследствие большой
накладной памяти такая схема весьма неэкономна. Достоинства ее в том, что
в любом месте можно включить или исключить элемент, и можно
эффективно сканировать строки и столбцы. Схема идеально приспособлена
для случаев, когда А строится каким-то алгоритмом, где нельзя предсказать
конечное число и позиции ненулевых элементов.

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