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

                                                                    3


                                                       Содержание
Введение .............................................................................................................................4
1. Схемы хранения .......................................................................................................5
   1.1 Схема Кнута .............................................................................................................5
   1.2 Разреженный строчный формат .......................................................................5
   1.3 Разреженный столбцовый формат ..................................................................6
   1.4 Сжатие по Шерману..............................................................................................6
   1.5 Гиперматричная схема .........................................................................................7
   1.6 О вычислительных затратах ..............................................................................7
2. Методы решения разреженных систем алгебраических
уравнений. Гауссово исключение .....................................................................9
   2.1 Гауссово исключение. Постановка задачи ................................................ 10
   2.2 Гауссово исключение по столбцам ............................................................... 13
   2.3 Гауссово исключение по строкам ................................................................. 14
   2.4 Исключение Гаусса – Жордана ...................................................................... 14
   2.5 Ошибки округления в методе Гаусса .......................................................... 15
   2.6 Численная устойчивость и выбор главных элементов ......................... 20
3. Теория графов для разреженных матриц .............................................. 23
   3.1 Сильные компоненты орграфа ....................................................................... 25
   3.2 Исследование стратегий для несимметричных разреженных
   матриц .............................................................................................................................. 27
      3.2.1 Поиск в глубину на орграфе................................................................ 27
      3.2.2 Поиск в ширину на орграфе и структуры уровней ориентированной
      смежности ..................................................................................................... 30
      3.2.3 Отыскание максимального множества путей с различными
      вершинами в ациклическом орграфе........................................................... 31
      3.2.4 Алгоритм Холла................................................................................... 32
      3.2.5 Алгоритм Хопкрофта – Карпа ............................................................ 34
      3.2.6 Алгоритм Сарджента – Уэстерберга .................................................. 36
      3.2.7 Алгоритм Тарьяна................................................................................ 37
   Список литературы ..................................................................................................... 43