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

                                   4
      Введение
      По мере того как растут производительность и быстродействие
вычислительных машин, растут размеры матриц. В специальной литературе
имеется несколько определений разреженной матрицы. Суть их состоит в
том, что матрица разрежена, если в ней «много» нулевых элементов.
Разреженную матрицу можно определить как матрицу, для которой
использование алгоритмов, учитывающих наличие нулей, позволяет
добиться экономии машинного времени и памяти по сравнению с
традиционными методами.
   Разреженные матрицы встречаются при решении многих важных
практических задач: дискретизации уравнений математической физики
(разностные схемы и методы конечных элементов), линейного
программирования (теория оптимизации), теории электрических цепей,
структурного анализа, численного решения дифференциальных уравнений,
теории графов, а также генетики, социологии и поведенческих наук.
   Всякую разреженную матрицу можно обрабатывать так, как если бы она
была плотной, также всякую плотную, или заполненную, матрицу можно
обрабатывать алгоритмами для разреженных матриц. В обоих случаях
получатся правильные результаты, но вычислительные затраты возрастут.
Приписывание матрице свойства разреженности эквивалентно утверждению
о существовании алгоритма, использующего ее разреженность и делающего
вычисления с ней дешевле по сравнению со стандартными алгоритмами.
   Матричные алгоритмы должны проектироваться таким образом, чтобы
хранились и обрабатывались только ненулевые элементы и по возможности
сохранялась разреженность. Конечно, не все алгоритмы для разреженных
матриц достигают этих целей. Многие схемы хранения допускают
определенную долю нулей, и алгоритм обрабатывает их, как если бы они не
были нулями. Алгоритм, хранящий и обрабатывающий меньшее число
нулей, более сложен, труднее программируется и целесообразен только для
достаточно больших матриц.
   Существует полный спектр алгоритмов, рассчитанных на различные типы
матриц, от плотных до очень разреженных, с различными необходимыми для
практики степенями эффективности, сложности или простоты. В связи с
развитием современной техники можно ожидать, что и дальше большие
разреженные матрицы будут встречаться во многих прикладных задачах,
включающих большие системы.