Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений ОНЛАЙН


Оглавление
Предисловие ……………………………………….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



Читать онлайн
скачать бесплатно


Теги:
Методы вычислений, Грималюк, Джордж, Лю, разреженные системы уравнений

Коментарі до Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений ОНЛАЙН