Способы хранения и представления разреженных матриц, операции над ними. Блатов И.А - 26 стр.

                                  - 26 -

  На входе задана матрица A в верхнетреугольном неупорядоченном РСФ:
  массивы AN , JA, IA, AD . На выходе должны получить матрицу в РСФД и
                         ~
  диагональную матрицу D .
  Особенности символического этапа –- мы должны исключить элементы
  ниже главной диагонали, а у нас только верхний треугольник, поэтому сразу
  мы не можем определить позицию тех элементов, которые нужно исключать
  при обработки текущей i -й строки. Оказывается, что столбцовые индексы i -
  й строки, которые нужно обнулить, совпадают со строчными индексами
  элементов i -ого столбца выше главной диагонали той матрицы, которая
  получилась к данному моменту при реализации алгоритма. Таким образом,
  на i -м шаге мы должны пройти по i -ому столбцу, определить все строчные
  индексы ненулевых элементов i -ого столбца –- это и будут те столбцовые
  индексы элементов i -й строки, которые нужно обработать.
  4.1.1. Символический этап
  4.1.1.1. Составление ассоциированного списка i -ого столбца
  Ассоциированный список (АС) i -ого столбца – это список номеров тех
  строк, которые участвуют при обработке i -й строки в методе Гаусса.
  Фактически каждому столбцу ставится в соответствии совокупность строк,
  причем каждая строка относится только к одному столбцу (то есть ни к
  какому другому она уже не приписывается), поэтому к i -ому столбцу
  приписываются только те строки матрицы A , у которых ненулевой элемент
  в i -м столбце является первым ненулевым элементом данной строки справа
  от диагонали.
                               Алгоритм
1. i =2 (так как первую строку обрабатывать не надо).
2. Проходим по (i −1) -й строке справа от диагонали. Предположим, что
   первый ненулевой столбцовый индекс равен j , тогда (i −1) -ую строку
   приписываем j -му столбцу и помещаем номер этой строки в первую
   позицию j -го     АС. Если действовать таким образом, то к моменту
   обработки строки АС будет уже сформирован.
3. i =i +1 и повторяем все действия до тех пор, пока не пройдем все строки.
     АС каждого столбца удобно хранить как кольцевой РЦС, и все эти
  списки можно хранить в целочисленном массиве JP размерности n , а
  массив указателей будет показывать вход в каждый список.

  4.1.1.2. Алгоритм символического этапа
  1. Для i =1 переносим портрет первой строки матрицы A в портрет
  пер-
      вой строки матрицы U без изменений.
  2. i =2 .
3. Заканчиваем формирование i -ого АС.