Введение ........................................................ 4
Глава 1. Разреженные матричные вычисления ....................... 5
1 1 Некоторые сведения из теории разреженных матриц ............ 5
1.2 Решение треугольных систем ................................. 7
1.3 Основные формы алгоритма Холесского ........................ 9
1.4 Некоторые формы хранения разреженных матриц ............... 16
1.4.1 Диагональная форма хранения ленточных матриц ....... 16
1.4.2 Профильная схема хранения разреженных матриц ....... 21
1.5 Некоторые сведения из теории графов ....................... 25
1.6 Машинное представление графа .............................. 28
1.7 Обратный алгоритм Катхилла - Макки (RCM) .................. 29
1.8 Определение начального узла ............................... 32
1.9 Дерево исключения множителя Холесского .................... 38
1.10 Компактная схема хранения разреженных матриц .............. 44
1.11 Сжатие по Шерману ......................................... 46
1.12 Символическое разложение .................................. 48
1.13 Численная факторизация .................................... 51
1.14 Алгоритм минимальной степени .............................. 53
Глава 2 Алгоритм Холесского на мультипроцессорных
архитектурах .......................................... 59
2.1 Мультипроцессорные архитектуры ............................ 59
2.2 Разделяемые (shared - memory) архитектуры ................. 59
2.3 Архитектуры с локальной памятью (или разделенные
архитектуры) (local (or distributed) - memory) ............ 60
2.4 Основные понятия параллелизма: ускорение, зернистость,
степень параллелизма, баланс нагрузки ..................... 63
2.5 Алгоритмы для компьютеров с разделяемой памятью ........... 66
2.5.1 Парадигма саморасписания ........................... 66
2.5.2 Метод Холесского Плотный случай ................... 67
2.5.3 Строка Холесского .................................. 68
2.5.4 Столбец Холесского ................................. 69
2.5.5 Подматрица Холесского .............................. 70
2.5.6 Рабочие профили и использование процессоров ........ 71
2.5.7 Реализация алгоритма Холесского .................... 72
2.5.8 Модифицированная плотная версия алгоритма
Холесского ......................................... 77
2.5.9 Разреженная версия алгоритма Холесского ............ 79
2.5.10 Параллельное решение разреженных треугольных
систем ............................................. 81
2.6 Алгоритмы для компьютеров с разделяемой памятью ........... 84
2.6.1 Введение ........................................... 84
2.6.2 Алгоритм Холесского (плотный случай) ............... 85
2.6.3 Отображение столбцов на процессоры ................. 86
2.6.4 Разреженный алгоритм Холесского Численная
факторизация ....................................... 88
2.6.5 Символическая факторизация ......................... 90
2.7 Роль деревьев исключения в параллельных вычислениях ....... 94
2.7.1 Деревья исключения и параллелизм ................... 94
2.7.2 Деревья исключения и связи ......................... 96
2.7.3 Переупорядочение и балансировка деревьев
исключения ......................................... 97
Литература .................................................... 102
Предметный указатель .......................................... 103
|
