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

                                  - 32 -

Для каждой строки значения ненулевых элементов загружаются в полный
вещественный массив, которому предварительно придано начальное нулевое
состояние. Строка массива выводится на печать или дисплей, и алгоритм
переходит к обработки следующей строки матрицы. Очень удобно было бы
различать визуально внутрипортретные нули (т.е. нули, перемещенные в
AN или AD вследствие взаимного сокращения при вычислении) и
внепортретные нули (т.е. нули, о которых заранее известно, что они будут
точными нулями, и которые поэтому не включаются в JA ). В позициях,
соответствующих внепортретным нулям, можно печатать нечисловой
символ, например *.
Разумеется, практически этот метод приложим к тем ситуациям, когда
достаточно исследовать малую часть матрицы или сама матрица достаточна
мала.
   2. Для каждой строки печатается её номер, а затем ненулевые
элементы этой строки и за каждым из них – в скобках – соответствующий
столбцовый индекс. Еще лучше было бы упорядочить ненулевые элементы
перед печатанием. Достоинство этого метода в том, что он сокращает
пространство, занимаемое выводимой строкой; однако он не дает такого
ясного представления о взаимном расположении соседних строк, как первый
метод.
   3. Портрет матрицы можно вывести на устройство с высокой
разрешающей способностью, например, дисплей или матричное
печатающее устройство. Нужно только, чтобы матрица была не слишком
велика или чтобы было достаточно её рассматривать по частям.

  4.4. Выбор порядка исключения в методе Гаусса (упорядочение
       строк и столбцов)
 В процессе гауссова исключения происходит заполнение матрицы, причем
объем и структура этого заполнения весьма существенно зависят от выбора
порядка исключения. Поэтому следует выбирать такую строку, в которой
больше нулей, – чтобы минимизировать число ненулевых элементов, когда
строка «обрушивается» на все другие строки, а также столбец с
максимальным числом нулей, чтобы использовать поменьше строк.
 О п р е д е л е н и е. Для элемента aij произведение числа ненулевых
элементов в      i -ой строке и j -ом столбце называется ценой Марковица
элемента aij .
Ненулевой элемент aij следует выбирать так, чтобы цена Марковица этого
элемента была минимальной или не слишком большой. Эта идея называется
стратегией Марковица. Она позволяет оптимизировать выбор ведущего
элемента.