Распараллеливание в OpenMP среднеквадратических приближений неполиномиальными сплайнами
Рассматривается применение неполиномиальных сплайнов минимального дефекта к задаче построения среднеквадратического приближения. Исследуются различные варианты оптимизации для решения методом релаксации возникающей в ходе построения приближения системы.
| Рубрика | Математика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 15.01.2019 |
| Размер файла | 220,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Распараллеливание в OpenMP среднеквадратических приближений неполиномиальными сплайнами
Винник М.П.
mvinnik92@gmail.com
541 учебная группа, математико-механический факультет СПБГУ
профессор Бурова Ирина Герасимовна
burovaig@mail.ru
каф. параллельных алгоритмов, математико-механический факультет СПБГУ
В данной работе рассматривается применение неполиномиальных сплайнов минимального дефекта к задаче построения среднеквадратического приближения. Исследуются различные варианты оптимизации для решения методом релаксации возникающей в ходе построения приближения системы. Проведен сравнительный анализ различных вариантов распараллеливания нескольких вариантов программ.
Практически всегда экспериментально полученные данные представлены в дискретном виде, т.е. в виде набора точек. При решении различного рода задач появляется необходимость оперировать непрерывной функций от одной или нескольких переменных, которая, тем не менее, принимает заданные значения в нужных точках. Интерполяция неполиномиальными сплайнами является быстрым и эффективном способом приближения.
Построение сплайнов
О построении полиномиальных В-сплайнов второй степени
Пусть - натуральное число, на промежутке задана равномерная сетка узлов
с шагом
так что
Базисные сплайны, , удовлетворяющие условиям:
,
будем строить решая систему уравнений с параметрами относительно . На промежутке система имеет вид:
Аналогичные системы уравнений имеем на соседних промежутках.
Параметры подбираем так, чтобы .
Нетрудно получить формулу базисного сплайна:
О построении тригонометрических сплайнов минимального дефекта
Для построения тригонометрических базисных сплайнов, таких, что рассмотрим три системы уравнений с параметрами .
Таким образом, при
на промежутке
и если
---
Объединяя формулы , найденные на трех соседних промежутках с одинаковым номером , получаем:
Вычисление элементов матрицы
Как известно, задача среднеквадратического приближения приводит к задаче решения системы линейных уравнений с матрицей Грама. В частном случае, при , структура матрицы Грама будет иметь следующий вид:
Вычисляя скалярные произведения, в случае полиномиальных B-сплайнов, получаем следующие значения:
Элементы вектора правой части таковы:
Вычисляя скалярные произведения в случае тригонометрических сплайнов минимального дефекта, получаем следующие значения:
Элементы вектора в правой части F таковы:
Распараллеливание вычислений и оптимизация
Хранение данных. При решении задач, требующих хранения информации большого объема, встает вопрос о способе хранения данных. В нашем случае матрица системы уравнений имеет ленточный пятидиагональный вид, и ранее было получено, что различных элементов в ней всего 10.
В данной работе было рассмотрено два подхода к хранению данных.
При первом подходе мы не учитываем тот факт, что матрица имеет пятидиагональный вид с малым числом различных элементов. При таком подходе мы, очевидно, получим выигрыш в скорости обращения к элементам, так как системная функция обращения к элементу динамического массива работает значительно быстрее, чем функция определения элемента для такой задачи. Однако, для работы с матрицами больших размерностей такой подход не годится, так как такие матрицы будут занимать слишком много места.
Второй подход состоит в том, что реализована специально для этой задачи функция, которая по номеру элемента матрицы определяет его значение. Использование такого подхода гарантирует нам очень большой выигрыш в памяти (вместо элементов мы храним только 10 для любых размеров матрицы), но дает также сильный проигрыш в скорости.
Был проведен сравнительный анализ времени выполнения программ, иллюстрирующих оба подхода.
Здесь и далее все измерения проводились при погрешности метода релаксации , равной и при априорном фиксированном количестве итераций (для построения эффективной параллельной программы) равном .
Решение системы методом верхней релаксации
К моменту решения система уже приведена к виду .
Расчетная формула имеет вид:
При вычислении следующего приближения можно оптимизировать формулу: при хранении текущего и следующего приближения в одном векторе можно произвести оба суммирования в одном цикле:
for (i=1;i<=n+2;i++)
{
dtmp2=0;
for (j=1;j<=n+2;j++)
{
dtmp2=dtmp2+get_elem(i,j,n,h,true)*x[j];//x_k+1[i]
}
x[i]=omega*F[i]+omega*dtmp2-x1[i]*(omega-1);
}
Первый подход к оптимизации аналогичен рассмотренному ранее подходу при вычислении параметра степенным методом. Внутри общего цикла помещается цикл for работающий фиксированное число итераций.
do{
k2++;
#pragma omp parallel for shared(x,omega,F,n) private(i,j,dtmp2,x1)
for (int i5=0;i5<iter_size;i5++){
}
}
while(dtemp1>pogr);
Второй подход предполагает распараллеливание только внутреннего цикла с тем же набором общих и разделяемых переменных.
На относительно малых матрицах второй подход показывает даже лучшее время, чем первый.
Сравнительный анализ времени выполнения
|
Обычный цикл |
Параллельный цикл (I) |
Параллельный цикл (II) |
||
|
100 |
172 |
187 |
141 |
|
|
500 |
3338 |
2512 |
2324 |
|
|
1000 |
9937 |
9375 |
9220 |
|
|
2000 |
38517 |
36535 |
38652 |
|
|
5000 |
243298 |
231962 |
249818 |
Целью работы было произвести оптимизацию времени расчетов. Были произведены замеры времени на различных матрицах. Результаты приведены в сводной таблице. Время указано в миллисекундах. Римская цифра I указывает на обычный способ хранения матрицы, а II - на оптимизированный.
|
Обычная программа(I) |
Обычная программа(II) |
Параллельная программа(I) |
Параллельная программа(II) |
||
|
100 |
31 |
156 |
47 |
172 |
|
|
250 |
109 |
827 |
78 |
796 |
|
|
500 |
436 |
4415 |
218 |
2886 |
|
|
750 |
568 |
7878 |
364 |
6147 |
|
|
1000 |
1466 |
12386 |
827 |
10967 |
|
|
2000 |
2824 |
43539 |
2871 |
40544 |
|
|
5000 |
18439 |
264077 |
18081 |
252008 |
Заключение
распараллеливание среднеквадратический неполиномиальный сплайн
За счет особенностей распараллеливания, в оптимизированных программах реализуется выигрыш в точности вычислений (а за счет многопоточности, одновременно и выигрыш во времени). Оптимальная функция доступа к элементу матрицы обеспечит нам еще больший выигрыш в скорости. Точная оценка числа итераций в общем случае является достаточно серьезной проблемой, а выигрыш в точности обеспечен на любой матрице. Программа демонстрирует всю мощь Open MP как средства оптимизации и языка C++, как средства реализации объемных вычислений.
Литература
1. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. 1984
2. Рябенький В.С. Введение в вычислительную математику. 2000
3. Фаддеев Д.К. Фаддеева В.Н., Вычислительные методы линейной алгебры. 2009
4. Бурова И.Г. Евдокимова Т.О., Приближения неполиномиальными сплайнами минимального дефекта. 2007
Размещено на Allbest.ru
...Подобные документы
Диаграмма рассеивания как точки на плоскости, координаты которых соответствуют значениям случайных величин X и Y, порядок ее построения и назначение. Нахождение коэффициентов и построение графика линейного приближения, графика квадратичного приближения.
курсовая работа [1,1 M], добавлен 03.05.2011Сущность и методика определения алгебраического числа, оценка существующего поля. Рациональные приближения алгебраических чисел. Задача построения уравнения с заданными корнями. Приводимые и неприводимые многочлены. Трансцендентные числа Лиувилля.
курсовая работа [219,6 K], добавлен 23.03.2015Аппроксимация и теория приближений, применение метода наименьших квадратов для оценки характера приближения. Квадратичное приближение таблично заданной функции по дискретной норме Гаусса. Интегральное приближение функции, которая задана аналитически.
реферат [82,0 K], добавлен 05.09.2010Обыкновенные и модифицированные жордановы исключения. Последовательность решения задач линейного программирования симплекс-методом применительно к задаче максимизации: составлении опорного плана решения, различные преобразования в симплекс-таблице.
курсовая работа [37,2 K], добавлен 01.05.2011Методы оценки погрешности интерполирования. Интерполирование алгебраическими многочленами. Построение алгебраических многочленов наилучшего среднеквадратичного приближения. Численные методы решения задачи Коши для обыкновенных дифференциальных уравнений.
лабораторная работа [265,6 K], добавлен 14.08.2010Определение матричных игр в чистых стратегиях. Смешанные стратегии и их свойства. Решения игр матричным методом. Метод последовательного приближения цены игры. Отыскание седлового элемента. Антагонистические игры как первый класс математических моделей.
контрольная работа [855,7 K], добавлен 01.06.2014Теорема отсчетов Котельникова-Шеннона и ее обобщения. Постановки задач теории приближения. Сигналы с дискретным временем. Характеристики наилучших приближений. Теорема отсчетов для цифровой обработки случайных сигналов. Дискретизация непрерывной функции.
курсовая работа [2,2 M], добавлен 08.08.2012Алгоритм построения минимального остовного дерева. Последовательность выполнения алгоритма Прима, его содержание и назначение. Процедура рисования графа. Порядок составления и тестирования программы, ее интерфейс, реализация и правила эксплуатации.
курсовая работа [225,0 K], добавлен 30.04.2011Модельная задача уравнения колебаний струны и деформации системы из трех струн. Вариационные методы решения: экстремум функционала, пробные функции, метод Ритца. Подпространства сплайнов и тестирование программы решения системы алгебраических уравнений.
дипломная работа [1,1 M], добавлен 29.06.2012Составление математической модели задачи. Приведение ее к стандартной транспортной задаче с балансом запасов и потребностей. Построение начального опорного плана задачи методом минимального элемента, решение методом потенциалов. Анализ результатов.
задача [58,6 K], добавлен 16.02.2016Описание методов решения системы линейного алгебраического уравнения: обратной матрицы, Якоби, Гаусса-Зейделя. Постановка и решение задачи интерполяции. Подбор полиномиальной зависимости методом наименьших квадратов. Особенности метода релаксации.
лабораторная работа [4,9 M], добавлен 06.12.2011Что такое абсолютные и относительные величины. Применение абсолютной и относительной величины в статистике. Прикладные варианты использования методов математической статистики в различных случаях решения задач. Опыт построения статистических таблиц.
контрольная работа [39,6 K], добавлен 12.12.2009Обзор и характеристика различных методов построения сечений многогранников, определение их сильных и слабых сторон. Метод вспомогательных сечений как универсальный способ построения сечений многогранников. Примеры решения задач по теме исследования.
презентация [364,3 K], добавлен 19.01.2014Элементарная теория сравнений. Диофантовы приближения. Определения и свойства сравнений. Теорема Эйлера, теорема Ферма. Китайская теорема об остатках, ее обобщение Цинь Цзюшао. Применение к решению олимпиадных задач. Применение к открытию сейфа в банке.
курсовая работа [243,5 K], добавлен 29.09.2015Основные виды линейных интегральных уравнений. Метод последовательных приближений, моментов, наименьших квадратов и коллокации. Решение интегральное уравнение методом конечных сумм и методом моментов. Ненулевые решения однородной линейной системы.
контрольная работа [288,4 K], добавлен 23.10.2013Общие аксиомы конструктивной геометрии. Аксиомы математических инструментов. Постановка задачи на построение, методика решения задач. Особенности методик построения: одним циркулем, одной линейкой, двусторонней линейкой, построения с помощью прямого угла.
курс лекций [4,0 M], добавлен 18.12.2009Сравнение методов простой итерации и Ньютона для решения систем нелинейных уравнений по числу итераций, времени сходимости в зависимости от выбора начального приближения к решению и допустимой ошибки. Описание программного обеспечения и тестовых задач.
курсовая работа [3,1 M], добавлен 26.02.2011Методика решения задач высшей математики с помощью теории графов, ее сущность и порядок разрешения. Основная идея метода ветвей и границ, ее практическое применение к задаче. Разбиение множества маршрутов на подмножества и его графическое представление.
задача [53,0 K], добавлен 24.07.2009Вычислительные методы линейной алгебры. Интерполяция функций. Интерполяционный многочлен Ньютона. Узлы интерполяции. Интерполяционный многочлен Лагранжа. Интерполяция сплайнами. Коэффициенты кубических сплайнов.
лабораторная работа [70,5 K], добавлен 06.02.2004Итерационные методы (методы последовательных приближений) для решения уравнений. Одношаговые итерационные формулы. Метод последовательных приближений Пикара. Возникновение хаоса в детерминированных системах. Методы решения систем алгебраических уравнений.
контрольная работа [166,2 K], добавлен 04.09.2010
