Введение
Глава 1. Полиномиальные алгоритмы 17
1.1. Основные алгоритмы над полиномами 17
1.1.1. Алгоритм сложения полиномов 17
1.1.2. Стандартный нерекурсивный алгоритм умножения полиномов 17
1.1.3. Стандартный рекурсивный алгоритм умножения полиномов 18
1.1.4. Алгоритм Карацубы умножения полиномов 19
1.1.5. Алгоритм точного деления полиномов 23
1.1.6. Алгоритмы возведения полиномов в степень 27
1.2. Оценки сложности для алгоритмов умножения полиномов . 28
1.3. Векторный формат хранения полиномов 34
1.3.1. Алгоритм сравнения мономов 35
1.3.2. Алгоритм сложения полиномов 35
1.3.3. Стандартный нерекурсивный алгоритм умножения полипомов 37
1.3.4. Алгоритм Карацубы умножения полиномов 39
1.3.5. Алгоритм точного деления полиномов 41
1.3.6. Алгоритмы возведения полиномов в степень 41
1.3.7. Достоинства и недостатки векторного формата хранения полиномов 44
1.4. Формат хранения полиномов в виде бидеревьев 44
1.4.1. Алгоритмы движения по бидереву 47
1.4.2. Алгоритмы получения левого и правого бидерева . 49
1.4.3. Алгоритмы объединения бидеревьев 50
1.4.4. Алгоритм сложения полиномов 51
1.4.5. Алгоритм стандартного умножения полиномов 53
1.4.6. Алгоритм Карацубы умножения полиномов 55
1.4.7. Достоинства и недостатки хранения полиномов в виде бидерева 56
1.5. Экспериментальное сравнение алгоритмов 56
1.6. Экспериментальное сравнение процедуры умножения полиномов с процедурой из системы КА Mathematica 57
Глава 2. LLP-распараллеливание рекурсивных алгоритмов 59
2.1. Принципы построения и функционирования LLP 59
2.1.1. Граф алгоритма 59
2.1.2. Динамическое распределение заданий 69
2.1.3. Начальный режим Л 71
2.1.4. Наблюдатель. Список СНУ. Список свободных КМ 73
2.1.5. Наблюдательный режим 75
2.2. Реализация LLP 80
2.2.1. Компьютерные модули 80
2.2.2. Основные структуры LLP 80
2.2.3. Прием и отправка заданий 90
2.2.4. Движение по дереву задания 94
2.2.5. Начальный режим 96
2.2.6. Наблюдатель 100
2.2.7. Наблюдательный режим 104
2.3. Реализация задания в LLP на примере умножения матриц 110
Глава 3. LLP-распараллеливание алгоритмов для операций над матрицами 111
3.1. Распараллеливание стандартного алгоритма умножения полиномов с помощью схемы LLP Ill
3.2. Реализация блочного стандартного алгоритма умножения матриц в LLP 114
3.3. Реализация алгоритма обращения матрицы в LLP 124
Заключение
