Распараллеливание построения среднеквадратических приближений сплайнами восьмого порядка аппроксимации Полуянов С.В. - презентация

1 Распараллеливание построения среднеквадратических приближений сплайнами восьмого порядка аппроксимации Полуянов С.В.

2 Введение Пусть функция f задана на промежутке [a, b] с погрешностями. Будем строить среднеквадратическое приближение третьей высоты, что позволит сгладить функцию и её производные вплоть до третьей.

3 Введение Приближение ищется из условия На промежутке [a, b] построим равномерную сетку узлов с шагом h: Тогда приближение задаётся по формуле: Коэффициенты находятся из условия

4 Введение Для нахождения коэффициентов необходимо решить систему MC=F, где

5 Построение базисных сплайнов Приближение на промежутке строится по формуле: Предположим, что носитель базисных сплайнов. Базисные сплайны найдём из условия для.

6 Построение базисных сплайнов Получаем систему уравнений.

7 Построение базисных сплайнов Решая систему, находим формулы базисных сплайнов.

8 Графики базисных сплайнов

9 Построение системы линейных алгебраических уравнений Строим среднеквадратическое приближение по формуле Для нахождения коэффициентов приходим к системе MC=F. M – матрица грамма, симметрична и положительно определена.

10 Построение матрицы Матрица M состоит из 16 блоков Каждый блок трёхдиагонален и имеет следующий вид:

11 Построение матрицы Элементы блока вычисляются по формулам: Положив h=1/N, вычислим элементы матрицы.

12 Построение матрицы Схематично матрица M имеет следующий вид: Матрица M[100x100], чёрным цветом обозначены ненулевые элементы

13 Вычисление правой части Правая часть имеет вид Каждый из векторов Его элементы определяются по формулам:

14 Вычисление правой части Для нахождения элементов F вычислим соответствующие интегралы, используя составную формулу Симпсона численного интегрирования. Разбивая отрезок интегрирования [a,b] на N равных частей, обозначим h=1/N и вычислим интегралы по формуле: где Погрешность интегрирования определяется по формуле:

15 Решение системы линейных алгебраических уравнений Для решения системы MC=F будем использовать одношаговый циклический процесс, также известный, как итерационный метод Зейделя. Суть его заключается в том, что в j-ом уравнении в правую часть переносятся все члены, содержащие c[j], j>i:

16 Решение системы линейных алгебраических уравнений Обозначим за D - матрицу, у которой на главной диагонали стоят соответствующие элементы матрицы M, а все остальные нули; матрицы U и L содержат верхнюю и нижнюю треугольные части M:

17 Решение системы линейных алгебраических уравнений После выбора начального приближения, процесс строится по формуле: Формулу можно привести к каноническому виду последовательных приближений : Из этой записи видно, что метод Зейделя является модификацией метода Якоби, в котором каждая итерация имеет вид C=BC+G. Отличие заключается в том, что новые значения используются сразу по мере получения, в отличие от простого итерационного процесса, в котором они используются только на следующей итерации.

18 Решение системы линейных алгебраических уравнений Итак, i-я компонента (k+1)-го приближения строится по формуле: Известно, что метод Зейделя сходится, если исходная матрица M является симметричной и положительно определённой.

19 Реализация и распараллеливание Реализовано в C++ с использованием OpenMP Распараллеливание осуществлено с помощью прагмы #pragma omp parallel for Распараллелен цикл вычисления неграничных элементов блоков вектора F Распараллеливание вычисления каждого интеграла излишне Вследствие вычислительной схемы итерационного процесса Зейделя распараллеливание внешнего цикла невозможно, распараллеливание внутренней операции суммирования ухудшало производительность

20 Реализация и распараллеливание Тесты показали, что при увеличении дробления области интегрирования вплоть до точность возрастает вплоть до 6-9 знака после запятой При дальнейшем разбиении точность уменьшается Условием окончания итерационного процесса является различие элементов текущей и предыдущей итерации менее, чем на заданную точность eps, либо превышение наперёд заданного максимального числа шагов maxN При заданной точности eps порядка 10^-8 норма вектора невязки имеет порядок 10^-12 – 10^-17

21 Реализация и распараллеливание Время вычисления правой части существенно превышает время решения системы линейных алгебраических уравнений При минимальном размере матрицы 12х12 есть в каждом блоке F[i] лишь один неграничный элемент, поэтому распараллеливание не повышает производительность Однако уже при следующем возможном размере 16х16 наблюдается рост производительности При достаточном размере матрицы на системе с двуядерным процессором Core 2 Duo наблюдается практически двукратный прирост производительности распараллеленной программы

22 Реализация и распараллеливание Размер матрицыЧисло потоковВремя вычисления правой части, сек Время решения СЛАУ, сек 12х х х х

23 Итог Был реализован и распараллелен алгоритм для построения среднеквадратического приближения, получен почти двукратный прирост производительности на системе с двуядерным процессором

24