Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений: Пер. с англ. - М., 1984, 336 с.
В книге известных американских математиков-вычислителей описаны все основные методы решения разреженных положительно определенных линейных систем. Впервые в монографической литературе излагаются алгоритмы параллельных и вложенных сечений, разработанные А. Джорджем и предназначенные для систем метода конечных элементов Включены тексты фортранных программ, реализующие описанные методы.
Для математиков-прикладников, для всех, кто связан с решением разреженных линейных систем, для студентов и аспирантов факультетов прикладной математики.
Оглавление
Предисловие ..............................................5
Глава I. Введение......................................................7
§ 1.0. Об этой книге........................................9
§ 1.1. Метод Холесского и проблема упорядочения.......-
§ 1.2. Положительно определенные и неопределенные матричные задачи 17
§ 1.З. Итерационные и прямые методы.............18
Глава 2. Вводные сведения......................21
§ 2.0. Введение .....................
2.0.1. Обозначения .................21
Упражнения....................23
§ 2.1. Алгоритм разложения................23
2.1.1 Существование и единственность разложения......23
2.1.2. Вычисление разложения.............25
2.1.3 Разложение разреженных матриц . . . ......29
Упражнения....................32
§ 2.2. Решение треугольных систем..............33
2.2.1 Вычисление решения...............33
2.2.2. Число операций ................35
Упражнения....................36
§ 2.3. Некоторые практические замечания . . .........38
2.3.1. Запросы к памяти . ..............39
2.3.2. Время исполнения................42
Упражнения....................43
Глава 3. Некоторые сведения из теории графов и ее применение к исследованию разреженных симметричных матриц..... ........44
§ 3.0. Введение .....................44
§ 3.1. Основная терминология и некоторые определения......44
Упражнения....................49
§ 3.2. Машинное представление графов............49
§ 3.3. Некоторые общие сведения о подпрограммах, оперирующих с графами .....................52
Упражнения....................54
Глава 4. Ленточные и профильные методы...............56
§ 4.0. Введение .....................56
§ 4.1. Ленточный метод.................56
Упражнения.............. . . . . 69
§ 4.2. Профильный метод..................59
4.2.1 Матричная формулировка............
4.2.2 Интерпретация на языке графов..........63
Упражнения....................64
§ 4.3. Профильные упорядочения ..............65
4.3 1 Обратный алгоритм Катхилла — Макки........65
4.3.2 Определение начальною узла............69
4.3.3. Подпрограммы поиска начального узла........72
4.3.4. Подпрограммы обратного алгоритма Катхилла — Макки. 76
Упражнения....................83
§ 4.4. Реализация профильного метода.............85
4.4.1. Профильная схема хранения ............85
4.4.2. Подпрограмма распределения памяти FNENV (FiNd-EN-Velope).....................86
§ 4.5. Подпрограммы численного решения ESFCT, ELSLV и EUSLV 88
4.5.1. Подпрограммы для решения треугольных систем ELSLV и EUSLV.......... ... . ...88
4.5.2 Подпрограмма разложения ESFCT..........92
Упражнения....................96
§ 4.6. Дополнительные замечания..............96
Глава 5. Универсальные разреженные методы.............98
§ 5.0. Введение .....................98
§ 5.1. Симметричное разложение............ . . . 98
5.1.1. Модель графов исключения............99
5.1.2. Моделирование исключения посредством достижимых множеств ......................102
Упражнения....................107
§ 5.2. Машинное представление графов исключения........107
5.2.1. Явные и неявные представления..........108
5.2.2. Модель фактор-графов..............109
5.2.3. Реализация фактор-модели............114
Упражнения....................119
§ 5.3. Алгоритм минимальной степени.............119
5.3.1. Основной алгоритм...............121
5.3.2 Описание алгоритма минимальной степени посредством достижимых множеств.................121
5.3.3. Ускорение алгоритма ..............124
5.3.4. Реализация алгоритма минимальной степени......129
Упражнения....................141
§ 5.4. Схемы хранения разреженных матриц..........143
5.4.1. Обычная схема.................143
5.4.2. Компактная схема................145
5.4.3. О символическом разложении...........148
5.4.4. Распределение памяти для компактной схемы и подпрограмма SMBFCT..................152
Упражнения....................157
§ 5.5. Подпрограммы численного разложения и решения......157
5.5.1. Подпрограмма GSFCT (General sparse Symmetric FaCTo-rization) .....................158
5.5.2. Подпрограмма GSSLV (General sparse Symmetric SoLVe) 162 § 5.6. Дополнительные замечания.....163
Глава 6. Методы фактор-деревьев для конечноэлементных и конечноразностных задач...........................164
§ 6.0. Введение .....................164
§ 6.1. Решение блочных систем уравнений........... 165
6.1.1. Разложение матрицы блочного порядка два.....165
6.1.2. Решение треугольной системы блочного порядка два . .170
Упражнения....................171
§ 6.2. Фактор-графы, деревья и древовидные разбиения......172
6.2.1. Блочные матрицы и фактор-графы..........172
6.2.2. Деревья, фактор-деревья и древовидные разбиения . . .175
6.2.3. Асимметричное блочное разложение и неявное блочное решение систем с древовидным разбиением.........178
Упражнения...................................179
§ 6.3. Алгоритм вычисления древовидного разбиений 182
6.3.1. Эвристический алгоритм.............182
6.3.2. Подпрограммы для вычисления древовидного разбиения . 185
Упражнение ... . ...............- 198
§ 6.4. Схема хранения и процедура распределения памяти .... 199
6.4.1. Схема хранения ........... .... 199
6.4.2. Внутреннее переупорядочение блоков.........202
6.4.13. Распределение памяти и подпрограммы FNTENV, FNOFNZ и FNTADJ................. 207
§ 6.5. Подпрограммы численных этапов TSFCT (Tree Symmetric FaC-Torization) и TSSLV (Tree Symmetric SoLVe).....214
6.5.1. Вычисление матричной поправки......... 214
6.5.2. Подпрограмма TSFCT (Tree Symmetric FaCTorization) . . 217
6.5.3 Подпрограмма TSSLV (Tree Symmetric SoLVe).....222
Упражнение......................... . . 230
§ 6.6. Дополнительные замечания..... .........230
Глава 7. Методы параллельных сечений для конечноэлементных задач 232
§ 7.0. Введение .....................232
§ 7.1. Пример — задача на mxl-сетке............232
7.1.1. Упорядочение посредством параллельных сечений....232
7.1.2. Требования к памяти...............235
7.1.3. Число операций при разложении..........237
7.1.4. Число операций при решении............240
Упражнения..............................240
§ 7.2. Алгоритм построения параллельных сечений для задач на нерегулярных сетках.......242
7.2.1. Алгоритм...................242
7.2.2. Подпрограммы для вычисления разбиения методом параллельных сечений . . ........244
§ 7.3. Об определении структуры оболочки диагональных блоков ................ 250
7.3.1. Постановка задачи...............250
7.3.2. Характеризация оболочки блочной диагонали посредством достижимых множеств................261
7.3.3. Алгоритм и подпрограммы вычисления оболочки диагональных блоков.......... ... . . 254
7.3.4. Анализ временной сложности алгоритма.......260
Упражнения...................260
§ 7.4. Дополнительные замечания..............261
Глава 8. Методы вложенных сечений.................263
§ 8.0. Введение...................263
§ 8.1. Вложенные сечения регулярной сетки...........263
8.1.1. Упорядочение . ................263
8.1.2. Требования к памяти...............266
8.1.3. Число операций.................270
8.1.4. Оптимальность упорядочения .........272
Упражнения....................274
§ 8.2. Вложенные сечения для произвольных задач........^7^
8.2.1. Эвристический алгоритм .............275
8.2.2. Машинная реализация..............276
Упражнения....................280
§ 8.3. Дополнительные замечания..............280
Глава 9. Численные эксперименты.......................202
§ 9.0. Введение .....................282
§ 9.1. Описание тестовых задач ...............284
§ 9.2. Что означают приведенные числа............286
§ 9.3. Сравнение методов ......................293
9.3.1. Критерии сравнения методов............293
9.3.2. Сравнение методов для тестовых задач набора #1 . . . 294
9.3.3. Сравнение методов для тестовых задач набора #2 . . . 296
§ 9.4. Зависимость от структуры данных............297
9.4.1. Запросы к памяти................298
9.4.2 Время исполнения................299
Приложение А. Некоторые указания к использованию подпрограмм . . 302
Приложение В. SPARSPAK: Пакет для разреженных матриц.....310
Литература..............................323
