| От переводчика | 5 |
| Предисловие | 7 |
| |
| Глава 1. Введение | 9 |
| |
| § 1.0. Об этой книге | 9 |
| § 1.1. Метод Холесского и проблема упорядочения | 10 |
| § 1.2. Положительно определённые и неопределённые матричные задачи | 17 |
| § 1.3. Итерационные и прямые методы | 18 |
| |
| Глава 2. Вводные сведения | 21 |
| |
| § 2.0. Введение | 21 |
 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 |
| Упражнения | 59 |
| § 4.2. Профильный метод | 59 |
| 4.2.1. Матричная формулировка | 59 |
| 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-ENVelope) | 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 |
| FaCTorization) | 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.3. Распределение памяти и подпрограммы FNTENV, FNOFNZ |
| и FNTADJ | 207 |
| § 6.5. Подпрограммы численных этапов TSFCT (Tree Symmetric |
| FaCTorization) и 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. Пример — задача на (m x l)-сетке | 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. Характеризация оболочки блочной диагонали посредством |
| достижимых множеств | 251 |
| 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. Вложенные сечения для произвольных задач | 275 |
| 8.2.1. Эвристический алгоритм | 275 |
| 8.2.2. Машинная реализация | 276 |
| Упражнения | 280 |
| § 8.3. Дополнительные замечания | 280 |
| |
| Глава 9. Численные эксперименты | 282 |
| |
| § 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 |
| |
| § А.1. Примеры скелетных ведущих программ | 302 |
| § А.2. Пример подпрограммы ввода числовых значений | 305 |
| § А.З. Совмещение памяти в Фортране | 307 |
| |
| Приложение В. SPARSPAK: Пакет для разреженных матриц | 310 |
| |
| § В.1. Мотивировка | 310 |
| § В.2. Базисная структура пакета SPARSPAK | 311 |
| § В.З. Головная программа пользователя — пример | 313 |
| § В.4. Краткое описание основных подпрограмм интерфейса | 315 |
| 8.4.1. Модули для ввода структуры матрицы | 315 |
| 8.4.2. Модули для упорядочения и распределения памяти | 317 |
| 8.4.3. Модули для ввода числовых значений A и b | 317 |
| 8.4.4. Модули для разложения и решения | 319 |
| § В.5. Средства для запоминания и возобновления | 319 |
| § В.6. Решение многих систем с одинаковой структурой или одинаковой |
| матрицей коэффициентов | 320 |
| § В.7. Вывод на печать | 322 |
| |
| Литература | 323 |
